IS CS-2019S2-01

题目来源：Problem 1 日期：2024-08-03 题目主题：CS-计算几何-多边形属性与变换

Solution

1. Determining Orientation of the Vertex Sequence

To determine the orientation (clockwise or counterclockwise) of the vertex sequence, we can use the cross product of the vectors formed by the edges of the polygon. Specifically, we compute the sum of the signed areas of the triangles formed by each pair of adjacent vertices and the origin. The formula for the signed area contribution of the edge from ${\mathbf{v}}^i$ to ${\mathbf{v}}^{i+1}$ is given by:

$$A_i=\frac{1}{2}\left(v_{xi}^i{v}_{yi}^{i+1}-v_{xi}^{i+1}{v}_{yi}^i\right)$$

Summing up all these contributions, the total signed area $A$ is:

$$A=\sum _{i=1}^{n-1}\left(v_{xi}^i{v}_{yi}^{i+1}-v_{xi}^{i+1}{v}_{yi}^i\right)+\left(v_{xn}^n{v}_{y1}^1-v_{x1}^1{v}_{yn}^n\right)$$

If $A>0$, the sequence is counterclockwise, and if $A<0$, the sequence is clockwise.

2. Area of the Polygon

The area of the polygon $\mathbf{M}$ can be calculated using the Shoelace theorem (also known as Gauss’s area formula). The formula for the area $A$ is:

$$A=\frac{1}{2}\left|\sum _{i=1}^{n-1}(v_{xi}^i{v}_{yi+1}^{i+1}-v_{xi+1}^{i+1}{v}_{yi}^i)+(v_{xn}^n{v}_{y1}^1-v_{x1}^1{v}_{yn}^n)\right|$$

3. Point-in-Polygon Test

To determine whether a point $\mathbf{p}=(p_x,p_y)$ is inside the polygon $\mathbf{M}$, we can use the ray-casting algorithm. The idea is to draw a ray from the point $\mathbf{p}$ in any direction and count the number of intersections it makes with the edges of the polygon. If the number of intersections is odd, the point is inside; if even, it is outside.

Steps:

1. Choose a direction (commonly the positive x-direction).
2. For each edge of the polygon, determine if the ray intersects the edge.
3. Count the number of intersections.

4. Triangulation of the Polygon

We will use mathematical induction to prove that for a simple polygon with n vertices, the number of triangles $T$ formed after triangulation is always $T=n-2$.

Base Case

Let’s start with the base case: $n=3.$

For a triangle (the simplest polygon), we have:

• Number of vertices: $n=3$
• Number of triangles after triangulation: $T=1$

We can see that the statement holds for the base case.

Inductive Hypothesis

Assume the statement is true for any polygon with $k$ vertices, where $k\ge 3$. That is:

For a polygon with $k$ vertices, the number of triangles $T_k$ after triangulation is:

$$T_k=k-2$$

Inductive Step

Now, let’s prove that the statement is true for a polygon with $k+1$ vertices.

Consider a simple polygon with $k+1$ vertices. We can triangulate this polygon by following these steps:

1. Choose any diagonal of the polygon that lies entirely inside the polygon.
2. This diagonal will split the polygon into two parts: a triangle and a polygon with k vertices.

Now, let’s count the triangles:

• The diagonal creates $1$ new triangle
• The remaining polygon with $k$ vertices will be triangulated into $T_k=k-2$ triangles (by our inductive hypothesis)

Therefore, the total number of triangles $T_{k+1}$ for the polygon with $k+1$ vertices is:

$$\begin{array}{rl}{T}_{k+1}& =1+T_k\\ & =1+(k-2)\\ & =k-1\\ & =(k+1)-2\end{array}$$

This shows that the statement is true for a polygon with $k+1$ vertices.

Conclusion

By the principle of mathematical induction, we have proven that for any simple polygon with $n$ vertices ($n\ge 3$), the number of triangles $T$ formed after triangulation is always:

$$T=n-2$$

This completes the proof.

5. Optimal Linear Transformation

We need to find the optimal linear transformation matrix $\mathbf{A}$ that minimizes the distance between $\tilde{\mathbf{V}}$ and $\mathbf{U}$, where:

• $\mathbf{V}$ is the set of original points
• $\mathbf{U}$ is the set of target points
• $\tilde{\mathbf{V}}=\mathbf{AV}$ is the set of transformed points

The transformation is represented as:

$$\left[\begin{array}{c}{\tilde{\mathbf{v}}}_{xi}^i\\ {\tilde{\mathbf{v}}}_{yi}^i\end{array}\right]=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\left[\begin{array}{c}{v}_{xi}^i\\ v_{yi}^i\end{array}\right]$$

We need to minimize:

$$E=\sum _{i=1}^n\left(({\tilde{\mathbf{v}}}_{xi}^i-{\mathbf{u}}_{xi}^i{)}^2+({\tilde{\mathbf{v}}}_{yi}^i-{\mathbf{u}}_{yi}^i{)}^2\right)$$

Solution Approach

We can solve this problem using the method of least squares. Here’s the step-by-step approach:

Step 1: Set up the System of Equations

We can rewrite our problem in matrix form:

$$\mathbf{U}=\mathbf{AV}$$

Where:

• $\mathbf{U}$ is a $2\times n$ matrix of target points
• $\mathbf{V}$ is a $2\times n$ matrix of original points
• $\mathbf{A}$ is our $2\times 2$ transformation matrix

Step 2: Formulate the Least Squares Problem

This sum can be interpreted as the sum of squares of all elements in the matrix $(\mathbf{AV}-\mathbf{U})$:

$$E=\sum _{i=1}^n\sum _{j=1}^2((\mathbf{AV}-\mathbf{U}{)}_{ij}{)}^2$$

The Frobenius norm of a matrix $\mathbf{M}$ is defined as the square root of the sum of the squares of its elements:

$$\Vert \mathbf{M}{\Vert }_F=\sqrt{\sum _{i,j}|{\mathbf{M}}_{ij}{|}^2}$$

Therefore, we can express $E$ in terms of the Frobenius norm:

$$E=\Vert \mathbf{AV}-\mathbf{U}{\Vert }_F^2$$

Minimizing $E$ is equivalent to minimizing $\Vert \mathbf{AV}-\mathbf{U}{\Vert }_F^2$, which is the same as minimizing $\Vert \mathbf{U}-\mathbf{AV}{\Vert }_F^2$ (since the norm is non-negative).

Thus, our goal is to minimize $\Vert \mathbf{U}-\mathbf{AV}{\Vert }_F^2$.

Note: While we will proceed with solving the normal equations, it’s worth noting that this problem can also be solved using the Moore-Penrose pseudoinverse of $\mathbf{V}$. The solution in that case would be $\mathbf{A}=\mathbf{U}{\mathbf{V}}^{+}$, where ${\mathbf{V}}^{+}$ is the pseudoinverse of $\mathbf{V}$. Both methods yield the same result, only from two different perspectives.

Step 3: Solve the Normal Equations

Let’s derive and solve the normal equations step by step:

1. Recall the definition of Frobenius norm:

   For a matrix $\mathbf{M}$, $\Vert \mathbf{M}{\Vert }_F^2={\sum }_{i,j}|{\mathbf{M}}_{ij}{|}^2$

2. This sum of squares can be expressed as the trace of ${\mathbf{M}}^T\mathbf{M}$:

   $\Vert \mathbf{M}{\Vert }_F^2=\mathrm{tr}({\mathbf{M}}^T\mathbf{M})$

   This is because the diagonal elements of ${\mathbf{M}}^T\mathbf{M}$ are the sum of squares of each row of $\mathbf{M}$.

3. In our case, $\mathbf{M}=\mathbf{U}-\mathbf{AV}$. So:

   $\Vert \mathbf{U}-\mathbf{AV}{\Vert }_F^2=\mathrm{tr}((\mathbf{U}-\mathbf{AV}{)}^T(\mathbf{U}-\mathbf{AV}))$

4. Expanding this:

   $E=\mathrm{tr}({\mathbf{U}}^T\mathbf{U}-{\mathbf{U}}^T\mathbf{AV}-{\mathbf{V}}^T{\mathbf{A}}^T\mathbf{U}+{\mathbf{V}}^T{\mathbf{A}}^T\mathbf{AV})$

Now, let’s derive the partial derivative:

5. Using the properties of trace and its derivative:

   • $\frac{\partial }{\partial \mathbf{A}}\mathrm{tr}(\mathbf{AX})={\mathbf{X}}^T$
   • $\frac{\partial }{\partial \mathbf{A}}\mathrm{tr}(\mathbf{X}{\mathbf{A}}^T)=\mathbf{X}$
   • $\frac{\partial }{\partial \mathbf{A}}\mathrm{tr}(\mathbf{AX}{\mathbf{A}}^T)=\mathbf{A}(\mathbf{X}+{\mathbf{X}}^T)$

   We can derive:

   $\frac{\partial E}{\partial \mathbf{A}}=-\mathbf{U}{\mathbf{V}}^T-({\mathbf{V}}^T\mathbf{U}{)}^T+2\mathbf{AV}{\mathbf{V}}^T$

6. Simplifying and setting to zero:

   $-2\mathbf{U}{\mathbf{V}}^T+2\mathbf{AV}{\mathbf{V}}^T=0$

7. This gives us the normal equations:

   $\mathbf{U}{\mathbf{V}}^T=\mathbf{AV}{\mathbf{V}}^T$

This solution minimizes the sum of squared differences between $\mathbf{U}$ and $\mathbf{AV}$.

Note: The invertibility of $\mathbf{V}{\mathbf{V}}^T$ is guaranteed if $\mathbf{V}$ has full row rank. If $\mathbf{V}{\mathbf{V}}^T$ is not invertible, we would need to use the pseudoinverse or other regularization techniques.

Step 4: Solve for $\mathbf{A}$

Multiply both sides by $(\mathbf{V}{\mathbf{V}}^T{)}^{-1}$:

$$\mathbf{A}=\mathbf{U}{\mathbf{V}}^T(\mathbf{V}{\mathbf{V}}^T{)}^{-1}$$

This gives us the optimal transformation matrix $\mathbf{A}$.

Conclusion

This method provides the optimal linear transformation matrix $\mathbf{A}$ that minimizes the sum of squared distances between the transformed points and the target points. It’s worth noting that this solution assumes no translation component. If a translation is needed, you would need to augment the transformation to include a translation vector, which would require a slightly different approach.

知识点

计算几何多边形线性代数最小二乘法正规方程矩阵范数外积广义逆矩阵投影矩阵矩阵求导

• 射线法 (Ray Casting Algorithm) 判定点是否在多边形内

难点思路

1. 多边形三角剖分的证明:

   • 使用数学归纳法时,关键在于如何将 $k+1$ 个顶点的多边形分解为一个三角形和一个 $k$ 个顶点的多边形。
   • 理解这种分解方法对于证明的完整性至关重要。

2. 最优线性变换的推导:

   • 将问题转化为矩阵形式是求解的关键。
   • 理解如何从最小化欧几里得距离平方和转化为最小化 Frobenius 范数。

解题技巧和信息

1. 多边形相关问题:

   • 总是考虑多边形的边界情况,如三角形。
   • 利用向量和叉积来简化计算和判断。

2. 最优化问题:

   • 尝试将问题转化为矩阵形式,这通常可以简化计算。
   • 熟悉常见的优化方法,如最小二乘法。

3. 证明题:

   • 对于涉及几何图形数量的证明,考虑使用数学归纳法。
   • 在归纳步骤中,寻找一种将大问题分解为小问题的方法。

重点词汇

• polygon 多边形
• vertex/vertices 顶点
• orientation 方向
• clockwise/counterclockwise 顺时针/逆时针
• cross product 叉积
• signed area 有向面积
• Shoelace theorem/Gauss’s area formula 鞋带定理/高斯面积公式
• ray-casting algorithm 射线投射算法
• triangulation 三角剖分
• linear transformation 线性变换
• least squares method 最小二乘法
• normal equations 正规方程
• Frobenius norm Frobenius 范数

参考资料

1. Computational Geometry: Algorithms and Applications - de Berg et al., Chapter 3 (Polygons)
2. Introduction to Linear Algebra - Gilbert Strang, Chapter 4 (Orthogonality)
3. Numerical Linear Algebra - Trefethen and Bau III, Lecture 18 (Least Squares Problems)