计算几何常用算法概览

计算几何常用算法概览计算几何常用算法概览 本站原创：怒火之袍 一、引言一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化， 但是也有 一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方 案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决 几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技 术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本 文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了 解并应用计算几何的知识解决问题起到帮助。 二、目录二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 三、算法介绍三、算法介绍 矢量的概念：矢量的概念： 1 / 22 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段 (directed segment)。如果有向线段 p1p2 的起点 p1 在坐标原点，我们可以把 它称为矢量(vector)p2。 矢量加减法：矢量加减法： 设二维矢量 P = ( x1,y1 ) ，Q = ( x2 , y2 ) ，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )， 同样的， 矢量减法定义为：P - Q = ( x1 - x2 , y1 - y2 )。 显然有性质 P + Q = Q + P , P - Q = - ( Q - P )。 矢量叉积：矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量 P = （x1,y1） ，Q = (x2,y2)，则矢量叉积定义为由(0,0)、p1、p2 和 p1+p2 所 组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果 是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两 点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。 叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的 顺逆时针关系： 若 P × Q 0 , 则 P 在 Q 的顺时针方向。 若 P × Q 0,则 p0p1 在 p1 点拐向右侧后得到 p1p2。 若(p2 - p0) × (p1 - p0) = 0。同理判断 Q1Q2 跨立 P1P2 的 依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) = 0。具体情 况如下图所示： 在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除 了这种过程外，大家也可以参考《算法导论》上的实现。 判断线段和直线是否相交：判断线段和直线是否相交： 有了上面的基础，这个算法就很容易了。如果线段 P1P2 和直线 Q1Q2 相交，则 P1P2 跨立 Q1Q2，即：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) = 0。 判断矩形是否包含点：判断矩形是否包含点： 6 / 22 只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。 判断线段、折线、多边形是否在矩形中：判断线段、折线、多边形是否在矩形中： 因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。 判断矩形是否在矩形中：判断矩形是否在矩形中： 只要比较左右边界和上下边界就可以了。 判断圆是否在矩形中：判断圆是否在矩形中： 很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于 等于圆心到矩形四边的距离的最小值。 判断点是否在多边形中：判断点是否在多边形中： 判断点 P 是否在多边形中是计算几何中一个非常基本但是十分重要的 算法。以点 P 为端点，向左方作射线 L，由于多边形是有界的，所以射线 L 的左端一定在多边形外，考虑沿着 L 从无穷远处开始自左向右移动，遇 到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交 点的时候，离开了多边形，……所以很容易看出当 L 和多边形的交点数目 C 是奇数的时候，P 在多边形内，是偶数的话 P 在多边形外。 但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中， L 和多边形的顶点相交，这时候交点只能计算一个；在图(b)中，L 和多边 7 / 22 形顶点的交点不应被计算；在图(c)和(d) 中，L 和多边形的一条边重合， 这条边应该被忽略不计。如果 L 和多边形的一条边重合，这条边应该被忽 略不计。 为了统一起见，我们在计算射线 L 和多边形的交点的时候，1。对于多 边形的水平边不作考虑；2。对于多边形的顶点和 L 相交的情况，如果该顶 点是其所属的边上纵坐标较大的顶点，则计数，否则忽略； 3。对于P 在多 边形边上的情形， 直接可判断 P 属于多边行。 由此得出算法的伪代码如下： 8 / 22 count ← 0; 以 P 为端点，作从右向左的射线 L; for 多边形的每条边 s do if P 在边 s 上 then return true; if s 不是水平的 then if s 的一个端点在 L 上 if 该端点是 s 两端点中纵坐标较大的端点 then count ← count+1 else if s 和 L 相交 then count ← count+1; if count mod 2 = 1 then return true; else return false; 其中做射线 L 的方法是：设 P 的纵坐标和 P 相同，横坐标为正无穷大 （很大的一个正数），则 P 和 P 就确定了射线 L。 判断点是否在多边形中的这个算法的时间复杂度为 O(n)。 9 / 22 另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比 较，这种算法由于使用浮点数运算所以会带来一定误差，不推荐大家使用。 判断线段是否在多边形内： 线段在多边形内的一个必要条件是线段的两个端点都在多边形内， 但由 于多边形可能为凹，所以这不能成为判断的充分条件。如果线段和多边形 的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点）， 因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有 一部分在多边形外(见图 a)。 于是我们得到线段在多边形内的第二个必要条 件：线段和多边形的所有边都不内交。 线段和多边形交于线段的两端点并不会影响线段是否在多边形内； 但是 如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是 否包含于多边形内部（反例见图 b)。 10 / 22 因此我们可以先求出所有和线段相交的多边形的顶点，然后按照 X-Y 坐标排序(X 坐标小的排在前面，对于 X 坐标相同的点，Y 坐标小的排在前 面，这种排序准则也是为了保证水平和垂直情况的判断正确)，这样相邻的 两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形 内，则该线段一定在多边形内。 证明如下： 命题 1： 如果线段和多边形的两相邻交点 P1 ，P2 的中点 P 也在多边形内，则 P1, P2 之间的所有点都在