《计算几何算法概览》由会员分享，可在线阅读，更多相关《计算几何算法概览（16页珍藏版）》请在金锄头文库上搜索。
1、计算几何算法概览计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观 看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科 学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何 在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在 本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几 何的知识解决问题起到帮助。二、目录本文整理的计算几何基本概念和常用算法包括如下内容：三、算法介绍矢量的概念：如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段 (dir
2、ected segment)。如果有向线段plp2的起点pl在坐标原点，我们可以把它称为矢量(vector)p2。矢量加减法：设二维矢量 P = ( xl, yl )， Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( xl + x2 , yl + y2 )，同样的，矢量减法定义为： P - Q = ( xl - x2 , yl - y2 )。显然有性 质 P + Q = Q + P， P - Q = - ( Q - P ) 。矢量叉积：计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P= (xl, yl )，Q= (x2, y2 )，则矢量叉积定义为由(0,0)、p
3、l、p2和p1+p2所组成的平行四边形的带符号的面积， 即：P X Q = x1*y2 - x2*y1其结果是一个标量。显然有性质P X Q = - ( QX P )和 P X ( - Q ) = - (P X Q)。一般在不加说明的情况下，本文下述算法中所有的点都看 作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：若P X Q 0 ,则P在Q的顺时针方向。若 P X Q 0,则p0p1在pl点拐向右侧后得到p1p2。若(p2 -p0)X(pl-p0)0,则pOpl在pl点拐向左侧后得到p1p2。若(p2
4、-p0)X(pl-p0)=0,则p0、pl、p2 三点共线。具体情况可参照下图:判断点是否在线段上:设点为Q,线段为PlP2，判断点Q在该线段上的依据是：(Q - Pl ) X ( P2 - Pl )=0且Q在以Pl, P2为对角顶点的矩形内。前者保证Q点在直线PlP2上，后者是保证Q 点不在线段P1P2的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实现：ON-SEGMENT(pi,pj,pk)if min(xi,xj) = xk = max(xi,xj) and min(yi,yj) = yk = max(yi,yj)then return true;else return fal
5、se;特别要注意的是， 由于需要考虑水平线段和垂直线段两种特殊情况， min(xi,xj)二xk二max(xi,xj)和 min(yi,yj)二yk二max(yi,yj)两个条件必须同时满足才能 返回真值。判断两线段是否相交：我们分两步确定两条线段是否相交：(1) 快速排斥试验设以线段P1P2为对角线的矩形为R，设以线段Q1Q2为对角线的矩形为T，如果 R和T不相交，显然两线段不会相交。(2) 跨立试验如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2，则矢量(P1 -Q1 )和(P2 - Q1 位于矢量(Q2 - Q1 )的两侧，即(P1 - Q1 ) X ( Q2 - Q1
6、) * ( P2 -Q1 ) X ( Q2 - Q1 ) 0。当 ( P1 - Q1 ) X ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以P1 一定在线段Q1Q2上；同理，(Q2 - Q1 ) X (P2 - Q1 )= 0说明P2 一定在线段Q1Q2上。所以判断P1P2跨立Q1Q2的依据是： (P1 - Q1 ) X ( Q2 - Q1 ) * ( Q2 - Q1 ) X ( P2 - Q1 ) = 0。同理判断 Q1Q2 跨立 P1P2 的依据是： ( Q1 - P1 ) X ( P2 - P1 ) *
7、 ( P2 - P1 ) X ( Q2 - P1 ) = 0。具 体情况如下图所示：通过快速排斥实醐通跨实 过立验 未过立验通跨实未通过快速排斥实骗在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除了这种过程外， 大家也可以参考算法导论上的实现。判断线段和直线是否相交：有了上面的基础，这个算法就很容易了。如果线段P1P2和直线Q1Q2相交，则P1P2跨 立 Q1Q2，即：(P1 Q1 ) X ( Q2 Q1 ) * ( Q2 Q1 ) X ( P2 Q1 ) = 0。判断矩形是否包含点：只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。判断线段、折线、多边形是否在矩形中
8、：因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。 判断矩形是否在矩形中：只要比较左右边界和上下边界就可以了。判断圆是否在矩形中：很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形 四边的距离的最小值。判断点是否在多边形中：判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端 点，向左方作射线L,由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着 L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内 部,遇到第二个交点的时候，离开了多边形，所以很容易看出当L和多边形的交点数目 C是奇数的时候，
9、P在多边形内，是偶数的话P在多边形外。但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中，L和多边形 的顶点相交，这时候交点只能计算一个；在图(b)中，L和多边形顶点的交点不应被计算； 在图(c)和(d)中，L和多边形的一条边重合，这条边应该被忽略不计。如果L和多边形的 一条边重合，这条边应该被忽略不计。图a图b为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。此得出算法的伪I代码如下：对于P在多边形边上的情形，直接可判断P属于多边行
10、。由图dcount j 0;以P为端点，作从右向左的射线L;for多边形的每条边sdo if P在边s上then return true;if s不是水平的 then if s的一个端点在L上if该端点是s两端点中纵坐标较大的端点t hen cou nt - cou nt+1else辻s和L相交then count - count+1;if count mod 2 = 1then return true;else return false;其中做射线L的方法是：设P的纵坐标和P相同，横坐标为正无穷大（很大的一个正 数），则P和P就确定了射线L。判断点是否在多边形中的这个算法的时间复杂度为0（n
11、）。另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于 使用浮点数运算所以会带来一定误差，不推荐大家使用。判断线段是否在多边形内：线段在多边形内的一个必要条件是线段的两个端点都在多边形内，但由于多边形可能为 凹，所以这不能成为判断的充分条件。如果线段和多边形的某条边内交（两线段内交是指两 线段相交且交点不在两线段的端点），因为多边形的边的左右两侧分属多边形内外不同部分 所以线段一定会有一部分在多边形外（见图a）。于是我们得到线段在多边形内的第二个必要 条件：线段和多边形的所有边都不内交。线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某 个顶
12、点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部（反例见图 b）。因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序（X坐标 小的排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水 平和垂直情况的判断正确），这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻 两点的中点也在多边形内，则该线段一定在多边形内。证明如下：命题 1：如果线段和多边形的两相邻交点P1，P2的中点P也在多边形内，则Pl, P2之 间的所有点都在多边形内。证明：假设P1,P2之间含有不在多边形内的点，不妨设该点为Q,在Pl, P之间，因为多 边形是闭合曲线，
13、所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，P 属于多边性内部，P1-Q-P完全连续，所以P1Q和QP一定跨越多边形的边界，因此在P1,P 之间至少还有两个该线段和多边形的交点，这和P1P2是相邻两交点矛盾，故命题成立。证 毕。由命题 l 直接可得出推论：推论2：设多边形和线段PQ的交点依次为P1,P2,Pn,其中Pi和Pi+1是相邻两交点， 线段PQ在多边形内的充要条件是：P，Q在多边形内且对于i =1, 2,n-1，Pi ,Pi+1 的中点也在多边形内。在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘 若线段和多边形的某条边内交则线段一定在多边
14、形外；如果线段和多边形的每一条边都不内 交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上 就可以了。至此我们得出算法如下：if 线端 PQ 的端点不都在多边形内then return false;点集 pointSet 初始化为空;for 多边形的每条边 sdo if 线段的某个端点在 s 上then 将该端点加入 pointSet;else if s 的某个端点在线段 PQ 上then 将该端点加入 pointSet;else if s 和线段 PQ 相交 / 这时候已经可以肯定是内交了then return false;将 pointSet 中的点按照 X-Y 坐标排序;for pointSet 中每两个相邻点 pointSeti , pointSet i+1do if pointSeti , pointSet i+1 的中点不在多边形中then return false;return true;这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n,所以最多是常数级的 复杂度，几乎可以忽略不计。因此算法的时间复杂度也是0(n)。判断折线是否在多边形内：只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶 点，则该算法的时间复杂度为O(m*n)。判断
