译 by zhougu

学习该内容的基础

*图论问题

*最短路径问题

 工具

这个模块论述了一些具有几何特性的多方面做计划的算法，而这些算法大多都建立在以 下的两个概念的基础上：向量乘积和反正切。

向量的乘积：

向量u和v的乘积被记做 u x v。而对于计算机程序来说，两个三维空间内的向量u和的 积是决定于下面的这个矩阵。（i，j，k是单位向量，而x，y，z分别是它们的方向）

| i j k |

 | ux uy uz |

 | vx vy vz | 可以通过这个方程计算出：(uyvz-vyu z)i + (uzvx-u xvz)j + (uxvy-uvx)k

 这个方法完全可以被用在二维的空间内，那时我们认为z=0，自然结果向量中的z也为0。

 向量的乘法有三个性质：

 *两个向量的积在空间范围内同时垂直于这两个向量。

 *向量u和v的积的长度等于向量u的长度、向量v的长度和两向量夹角的正弦值的乘积。

*在两个可能出现的方向中，向量u和向量v的积的方向取决于u和v的位置关系。

 向量的数量积：

向量u和向量v的数量积记做u?v，用与刚才类似的方程表示为：u xvx + u yvy + u zvz

而事实上我们可以用标量u的长度、v标量的长度和两向量夹角的余弦值的乘积来表示向 量u和向量v的数量积。 如果向量u和向量v的夹角大于90度，而u和v都是非0的，那么它们的数量积是负数。如 果它们的数量积等于0，那么它们是互相垂直的。如果u?v的结果是正数，那么它们夹的是一 个锐角。

反正切： 反正切作为函数通常可以通过正切值计算出一个处在-Pi/2到Pi/2之间的角的度数。C语 言中额外的atan2函数带有两个引数：DELTA y的值和DELTA x的值。它会测定所给向量与x轴 的夹角并返回一个处在-Pi/2到Pi/2之间的角度。它的好处就在于消去了涉及到0做被除数和 为处理多种角度情况时所写的代码。大多时候，函数atan2要比只带有一个引数的函数atan 简单。

特殊的调试问题：

解决几何问题时最主要是问题是它们往往有很多特殊情况，所以要确认你的程序可以应 付所有的特殊情况。

浮点数据的计算总会产生一系列的问题。浮点数据的计算很少是100%精确的，因为电脑 本身也只能维持一定位数的准确度。尤其是判断两个值是否相等时，电脑只是看它们的差是 否在一个很小的容差值的范围内。

几何算法：

以下是几个可以帮助我们解决几何问题的资料。

三角形区域：

计算一个顶点为(a,b,c)的三角形所在的区域，要先选择一个顶点(比如顶点a)，并创建 两个与另外三角形的三边有如下关系的向量：使向量u = b - a，向量v = c - a。三角形a 、b、c的区域就是向量u和向量v的乘积的1.5倍。

还有一个求三角形区域可以选择的方法是用hero定理。如果三角形三边的长度分别为a 、b、c，设s=(a+b+c)/2，这个三角形的区域就等于： sqrt(s* (s-a)*(s-b)*(s-c)) 两条线段是否平行：

检验两条线段是否平行，可以沿着两条线段的方向创建两个向量，然后看它们的乘积是 否为0。

多边形区域：

一个顶点为(x 1, y 1), ..., (x n, y n)的多边形的区域等于下面这个行列式。

1 | x1 x2 ... xn |

--- |            |

2 | y1 y2 ... yn |

这个行列阵的算法类似于2 X 2的行列阵：x1 y2 + x2y3 + ... + xn y1 - y1 x2 - y2x3 - ... - yn x1。

点到直线的距离：

值得注意的是点P到直线AB的距离往往是由向量乘积量得出的：d(P,AB) = |(P - A) x (B - A)| / | B - A|。 要决定点P到A、B、C三点所在的平面的距离，需先设n = (B - A) x (C - A)，然后用这个公式来计算：d(P,ABC) = (P-A) ? n / |n|。

在直线上的点：

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

在直线同侧的点：

这个想法只对二维的空间有意义。要检验点C和点D是否在直线AB同侧，只需计算(B - A) x (C - A)和(B - A) x (D - A)的值。如果它们同号，C和D就在直线AB的同侧。

三角形内的点：

检验点A是否在三角形内部，我们可以先在三角形内部找一个点B(三个顶点的平均值即 可)。然后检验A相对三边是否都在B的同侧。

凸多边形内的点：

这和三角形是同样的做法。

多个(四个以上)点共面：

要判断一系列点是否共面，我们可以先选择三个点A、B、C，它们必然是共面的，在任 意挑选一点D，如果(B - A) x (C - A)) ? (D - A) = 0，则这个点与点A、B、C在一个平面 内。

两线段相交：

在二维空间内，两条线段AB和CD相交，如果A、B分别在线段CD的两侧而且C、D分别在线 段AB的两侧。

把这两个核对全记录下来往往是不必要的，如果其中一个的核对证明AB和CD是不相交的 就返回false并结束核对。在三维空间内，利用以下的等式(i,j不是已知的)：

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)，且i、j在0和1之间，那么两线段相交于(Ax + (Bx - Ax)i, Ay + (By - Ay)i, Az + (Bz - Az) i 。

两条直线交点：

要计算二维空间内的两直线AB、CD的交点，最容易想到的方法就是构造两直线方程：

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)

检验二维多边形的凹凸：

要检验二维多边形的凹凸，可以按顺时针方向遍历整个多边形。对于每一个连续的3个 顶点(A，B，C)，计算(B-A) x (C-A)的乘积。如果所有结果都是正的，那么这个多边形就是 凸多边形。

凹多边形内的点：

要计算一个点是否在凹多边形内部，可以从该点做一条不定方向的射线，然后看它与这 个凹多边形的交点的数目。如果它经过凹多边形的一个顶点或者平行于一条边，就换个方向重做射线。如果射线与凹多边形的交点数为奇数，那么该点在凹多边形内。

这个判定方法在三维(或者多维)，只是对交点的限制由顶点和边变成了平面。

几何方法论：

几何问题会引进很多减小程序运行时间或近似解决问题的技巧。

蒙特卡洛模拟法：

第一个几何技巧是建立在随机基础之上的。就是依照概率随机模拟一个事件产生的值来 替代计算事件可能产生的值。如果模拟的事件足够多的话，那么这两个值之间的差就会变得很小。

这对于确定一些有考虑范围的问题有帮助。因为它不必求出准确的范围，只要先确定一 个大致的范围，然后估计可能出现的结果，再在已有范围里做调整。如果这个范围足够精确 ，你就可以偷着高兴了。 这个方法的问题是会产生一个相对的误差，所以考虑的可能的事件数越多越好。如果你 对可能的事件考虑得太少，用这个方法是不会有好结果的。

分割法：

分割法是一种改进几何算法速度的方法。这种方法把平面拆分成很多部分(常常按格划 分，有时也辐射状地划分或者用其他方式)，适当地把对象存入各部分中。然后只需处理那 些存有对象的部分。从而大大减小了算法的花费。这个方法对那些求点的距离(整体是圆)或 者交叉点(整体是线)的问题有帮助。

图的问题：

有时图的问题往往会被误认为是几何问题。几何问题是不能仅仅通过输入的是平面上的 点来确定的。

例题：

点的移动：

给你一些平面内的线段和两个点A、B，问是否可能从A点到达B点而且不穿越任何线段。 换种说法就是线段把整个平面分割成多个封闭的区域，问A和B是否在同一个区域内。

骑车路线： 在起点与终点之间，给你一些不交叉的建筑物，求在不穿越建筑物的前提下，起点到终 点的最短距离。

算法：这确实是一个图的问题，节点是起点和终点。如果与建筑物不交叉，在每两个建 筑物的节点之间都可以生成一条线段，距离的增加量就是线段的长度；如果与建筑物交叉， 就向终点的方向转。这样走一遍，得出来的就是要求的最短距离。

最少交点：

给你一些平面内的线段，尽可能少的做直线，使所给的线段全部被做出的直线穿过，求 最少需要做直线的条数。

算法：考虑一下，思路应该很清楚。直线一定经过所有线段的端点中的两个，这样就可 以玫举所有线段的两个端点，再计算每种情况下交点的个数。如果能把此算法和分割法一起 使用，会大大提高算法的性能。

多边形种类：

给你一些平面内的线段来定义一个多边形，判断它是简单的（没有两条不连续的线段有 交点）并判断它是否是凸多边形。