这是几乎全部机翻的版本。几乎可以肯定的是,这个翻译需要改进。

先决条件

  • 图论
  • 最短路

工具

本节讨论了几种用于计算各类几何属性的算法,主要基于下面描述的两种操作:叉积和反正切。

叉积

u和v的叉积写作u x v。在计算中,两个三维向量u和v的叉积是下列矩阵的矢量行列式(其中i、j和k分别是x、y和z方向的单位向量):

1
2
3
| i  j  k  |
| ux uy uz |
| vx vy vz |

这个式子的值为:

(uyvz-vyuz)i + (uzvx-uxvz)j + (uxvy-uyvx)k

通过将三维向量的z分量置为0,这一定义可用于二维向量。得到的向量只有z分量有值。

叉积有三条性质:

  • 两个向量的叉积垂直于这两个向量。
  • 叉积的长度等于以下几项的乘积:
    • u的长度
    • v的长度
    • u和v夹角的正弦值

在与u和v垂直的两个不同方向中,叉积指向的方向取决于u是在v的“右边”还是“左边”。

这就是右手定则吧。

点积

两个向量u和v的点积是写作u·v的标量。在计算中,它在三维向量中定义为: uxvx + uyvy + uzvz

点积实际上等于以下几项的乘积:

  • u的长度
  • v的长度
  • u和v之间夹角的余弦值。

假定u和v不为零,如果点积为负,则u和v的夹角大于90度。如果它为零,则u和v垂直。如果点积为正,则两个向量的夹角为锐角。

反正切

反正切函数计算其正切值等于它的参数的角度,通常返回-pi/2和pi/2之间的一个实数。C中的函数atan2接收两个参数:y轴的差值和x轴的差值(按此顺序!)。它确定给定向量和x轴正半轴之间的角度,并返回一个-pi和pi之间的值。这可以解决除零或需要撰写代码处理x轴负半轴的问题。该atan2函数几乎总是比简单的只有一个参数的反正切函数容易使用。

显然如果只接收一个参数,无法处理向量和x轴垂直的情况(因为会发生除0问题),而且只有正负也无法说明是和正半轴还是负半轴的夹角。

调试中的特殊问题

计算几何题的主要问题是它们会产生许多特殊情况。请留意这些特殊情况,并确保你的程序适用于所有这些情况

浮点数计算也会产生很多新问题。浮点计算很少是精确的,因为计算机只准确保留了若干比特(位):要注意这一点。特别注意,在检查两个值是否相等时,不要检查它们是否精确相等,而是检查它们之间的差值是否小于某个范围。

计算几何算法

下面是一些可以帮助你解决计算几何问题的代码片段。

三角形面积

要计算顶点为(a,b,c)的三角形的面积,选择一个顶点(比如说a),并创建从a指向另外两个顶的向量(令u = b - a,v = c - a)。则三角形(a,b,c)的面积是u和v叉积长度的一半。

另一种计算三角形面积的方法是海伦公式。如果三角形的三条边长度分别为a,b,c,令s = s = (a+b+c)/2,则三角形的面积为

sqrt(s*(s-a)*(s-b)*(s-c))

两条线段是否平行?

为了检查两条线段是否平行,请沿每条线段创建向量,并检查它们的叉积是否(几乎)为零。

多边形面积

顶点为(x1, y1), ...,(xn, yn)的多边形的面积等于行列式:

1
2
3
 1   | x1 x2 ... xn |
--- | |
2 | y1 y2 ... yn |

其中行列式的定义类似于2*2的行列式:x1y2 + x2y3 + ... + xny1 - y1x2 - y2x3 - ... - ynx1

不过我觉得我一般只会把多边形分成若干个三角形来算……

点到直线的距离

从点P到线段AB的距离等于叉积的大小,即d(P,AB) = |(P-A)x (B-A)| / | B - A | 。

为了确定从点P到由点A、B和C定义的平面的距离,令n =(B-A) × (C-A)。下列等式即给出距离:d(P,ABC) = (P - A) · n / |n|。

点在直线上

点在直线上当且仅当点到直线的距离为0。

在直线同一侧的点

这个概念只对二维平面有意义。要检查C点和D点是否在直线AB的同一侧,计算(B - A) x (C - A)和(B - A) x (D - A)的z分量。如果z分量具有相同的符号(即它们的乘积是正的),则C和D位于直线AB的同一侧。

点在线段上

为了计算点C是否在线段AB上,检查C是否在直线AB上。如果是,则检查AB的长度是否等于AC和CB的长度之和。

点在三角形中

为了检查点A是否在三角形中,找到三角形内的另一个点B(三个顶点的平均值就可以)。然后,检查点A是否和点B在由三角形的边定义的三条直线的同一侧。

点在凸多边形中

同样的技巧适用于凸多边形:

四(或更多)点共面

为了确定点集是否是共面的,选择三个点,A、B和C。如果对于任何其他点D,((B - A) x (C - A)) · (D - A) ≈ 0,则该点集共面。

先算出三个点对应的平面的法向量……

两条直线相交

在二维平面中,两条线相交当且仅当它们不平行。

在三维中,当直线AB和CD不平行且A、B、C、D共面时,AB和CD相交。

两条线段相交

在二维平面中,线段AB和CD相交,当且仅当A和B位于直线CD的不同侧且C和D位于直线AB的不同侧时。

请注意,两个检查都是必要的,因为在上图中最后一种情况中,一个检查返回true,而另一个检查才能证明AB和CD不相交。在三维情况中,求解下面的方程组,其中i和j是未知数:

1
2
3
Ax + (Bx - Ax) i = Cx + (Dx - Cx) j
Ay + (By - Ay) i = Cy + (Dy - Cy) j
Az + (Bz - Az) i = Cz + (Dz - Cz) j

如果该方程组具有解(i,j),其中0 <= i <= 1且0 <= j <= 1,则线段相交于点(Ax + (Bx - Ax)i, Ay + (By - Ay)i, Az + (Bz - Az) i。

两条直线的交点

对于二维平面中的直线AB和CD,计算它们交点的最直接方法是求解以下两方程两未知数的方程组:

1
2
Ax + (Bx - Ax)i = Cx + (Dx - Cx) j
Ay + (By - Ay)i = Cy + (Dy - Cy) j

交点坐标为:
(Ax + (Bx - Ax) i, Ay + (By - Ay) i)

在三维情况下,求解与检查线段交叉时相同的方程组,则交点坐标为:
(Ax + (Bx - Ax)i, Ay + (By - Ay)i, Az + (Bz - Az)i)

检查二维多边形的凸性

为了检查二维多边形的凸性,按顺时针顺序遍历多边形的顶点。对于所有的连续三个顶点(A,B,C),计算叉积(B - A) x (C - A)。如果 得到的所有向量的z分量都是正的,则多边形是凸的。

点在非凸多边形中

为了计算某点是否在非凸多边形内,从该点沿随机方向发出一条射线,并计算它与多边形相交的次数。如果射线在顶点或沿边缘与多边形相交,则选择一个新方向。否则,当且仅当射线与多边形相交奇数次时,该点才在多边形内。

此方法也适用于三维(和更高维度),但对相交的限制是只在面上相交,而不是在顶点或边上。

计算几何方法

计算几何题引入了几种不同的技巧,可用于减少运行时间或估计解。

蒙特卡洛方法

第一种计算几何技巧基于随机性。我们不是计算某事发生的概率,而是模拟随机事件并计算它发生的次数。如果模拟了足够多的事件,则这两个值之间的差异将变得非常小。

这有助于确定图形面积大小之类内容。我们不是直接计算区域,而是确定一个边界框,然后向框中抛出“飞镖”,并估计击中图形的概率是多少。如果计算得足够准确,这可以很好地估计实际面积。

这种方法的问题是,获得良好的相对误差(误差除以实际值)需要大量成功的事件。如果事件发生的概率非常小,则该方法不会产生很好的结果。

分区

分区是一种提高计算几何算法速度的方法。这需要将平面分成多个部分(通常通过网格,但有时也会按辐射切开或其他方法),并将对象分到对应的区域中。当在某个图形中查找对象时,只需要检查与该图图形具有非零交点的那些部分,从而大大降低了算法的成本。这有助于确定到给定点的距离在某个范围内的对象集和(图形是圆)或检查交叉点(图形是一条直线)。

图论问题

有时看起来像计算几何问题的问题实际上是图论问题。仅仅因为输入是平面中的点并不意味着需要计算几何算法。

例题

移动点

给定平面中的一组线段,以及两个点A和B,能否在不跨越任何线段的情况下从A移动到B?

分析:线段将平面划分为区域。确定这些区域,并检查A和B是否位于同一区域。

问题是怎么确定这些区域,感觉有些麻烦……

自行车路线

给定一系列互不交叉建筑的以及它们的起点和终点位置,找到从A到B的不经过任何建筑物的最短路径。

分析:这实际上是一个图论问题。结点是起始位置和结束位置,以及建筑物的顶点。如果两个结点之间的线段不与任何建筑物相交,则它们之间有边,其权重等于线段的长度。构造完该图后,问题就变成了最短路。

最大化交叉点数量

给定平面中的一组线段,找到可以与一条直线相交的线段的最大数量。

分析:经过一些思考,很显然直线必须通过线段集合中的两个顶点。因此,尝试所有顶点对,并计算每条直线的交叉点数量。将其与分区相结合,可以提供一种运行速度相当快的算法。

或者说,一种最优解可以通过旋转变换成另一个一定至少通过两个顶点的最优解……

多边形分类

给定定义多边形的一组线段,确定它是否是简单多边形(没有两个非连续线段相交)和凸多边形。

Q:凸多边形一定是简单的吗?