几何算法概览

《几何算法概览》由会员分享，可在线阅读，更多相关《几何算法概览（15页珍藏版）》请在金锄头文库上搜索。

1、计算几何算法概览一、引言计算机的出现使得很多原本十分繁琐的工作得以大幅度简化， 但是也有一些在人们直观看来 很容易的问题却需要拿出一套并不简单的通用解决方案， 比如几何问题。作为计算机科学的一个 分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、 机 器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。 在本文中，我们将对 计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到 帮助。二、目录本文整理的计算几何基本概念和常用算法包括如下内容：矢量的概念矢量加减法矢量叉积折线段的拐向判断判断点是否在线段上判断两线段是否相

2、交判断线段和直线是否相交判断矩形是否包含点判断线段、折线、多边形是否在矩形中判断矩形是否在矩形中判断圆是否在矩形中判断点是否在多边形中判断线段是否在多边形内判断折线是否在多边形内判断多边形是否在多边形内判断矩形是否在多边形内判断圆是否在多边形内判断点是否在圆内判断线段、折线、矩形、多边形是否在圆内判断圆是否在圆内计算点到线段的最近点计算点到折线、矩形、多边形的最近点计算点到圆的最近距离及交点坐标计算两条共线的线段的交点计算线段或直线与线段的交点求线段或直线与折线、矩形、多边形的交点求线段或直线与圆的交点凸包的概念凸包的求法三、算法介绍矢量的概念：如果一条线段的端点是有次序之分的，我们把这种线段

3、成为有向线段 (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,

4、y2 )， 则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P X Q =x1 *y2 - x2*y1,其结果是一个标量。显然有性质P X Q = - ( Q X P )和P X ( - Q )=- ( P X Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就 是矢量相加减，而点的乘法则看作矢量叉积。叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：若P X Q 0 ,则P在Q的顺时针方向。若P X Q 0,则pOpl在pl点拐向右侧后得到p1p2。若(p2 - pO)X(p1- pO)0,则pO

5、pl在pl点拐向左侧后得到p1p2。若(p2 - pO)X(p1- pO)=O,则 pO、pl、p2三点共线。具体情况可参照下图：判断点是否在线段上：设点为Q,线段为P1P2，判断点Q在该线段上的依据是：(Q - P1 ) X ( P2 - P1 ) = 0且 Q在以P1, P2为对角顶点的矩形内。前者保证Q点在直线P1P2上，后者是保证Q点不在线 段 P1P2 的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实现：ON-SEGMENT(pi,pj,pk)if min(xi,xj) = xk = max(xi,xj) and min(yi,yj) = yk = max(yi,yj)th

6、en return true;else return false;特别要注意的是，由于需要考虑水平线段和垂直线段两种特殊情况， 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 )

7、位于矢量(Q2 - Q1 )的两侧，即(P1 - Q1 ) X ( Q2 - Q1 ) * ( 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

8、跨立 P1P2 的依据是：(Q1 - P1 ) X ( P2 - P1 ) * ( P2 - P1 ) X ( Q2 - P1 ) = 0。具体情况如下图所示：通过快速排斥实验未通过快速排斥丈骗通跨实 过立验 未过立验通跨实在相同的原理下，对此算法的具体的实现细节可能会与此有所不同， 除了这种过程外，大家 也可以参考算法导论上的实现。判断线段和直线是否相交：有了上面的基础，这个算法就很容易了。如果线段P1P2和直线Q1Q2相交，则P1P2跨立 Q1Q2，即：(P1 - Q1 ) X ( Q2 - Q1 ) * ( Q2 - Q1 ) X ( P2 - Q1 ) = 0。判断矩形是否包含点：只要

9、判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。判断线段、折线、多边形是否在矩形中：因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。判断矩形是否在矩形中：只要比较左右边界和上下边界就可以了。判断圆是否在矩形中：很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边 的距离的最小值。判断点是否在多边形中：判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点， 向左方作射线L,由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷 远处开始自左向右移动，遇到和多边形的第一个交点的时候， 进入到了多边形的内部，

10、 遇到第二 个交点的时候，离开了多边形，所以很容易看出当L和多边形的交点数目C是奇数的时候， P 在多边形内，是偶数的话 P 在多边形外。但是有些特殊情况要加以考虑。如图下图 (b)(c)(d)所示。在图中，L和多边形的顶点 相交，这时候交点只能计算一个；在图(b)中，L和多边形顶点的交点不应被计算；在图(c)和(d) 中，L和多边形的一条边重合，这条边应该被忽略不计。如果L和多边形的一条边重合，这条边 应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考 虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则 计数，否

11、则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的 伪代码如下：count 0;以 P 为端点，作从右向左的射线 L;for 多边形的每条边 sdo if P 在边 s 上then return true;if s 不是水平的then if s 的一个端点在 L 上if 该端点是 s 两端点中纵坐标较大的端点then count count+1else if s 和 L 相交then count count+1;if count mod 2 = 1then return true;else return false;其中做射线L的方法是：设P的纵坐标和P相同，横坐标为

12、正无穷大（很大的一个正数）， 则P和P就确定了射线L。判断点是否在多边形中的这个算法的时间复杂度为 O（n）。另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较， 这种算法由于使用 浮点数运算所以会带来一定误差，不推荐大家使用。判断线段是否在多边形内：线段在多边形内的一个必要条件是线段的两个端点都在多边形内，但由于多边形可能为凹， 所以这不能成为判断的充分条件。如果线段和多边形的某条边内交（两线段内交是指两线段相交 且交点不在两线段的端点），因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一 定会有一部分在多边形外（见图a）。于是我们得到线段在多边形内的第二个必要条件：线段

13、和多 边形的所有边都不内交。线段和多边形交于线段的两端点并不会影响线段是否在多边形内； 但是如果多边形的某个顶 点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部（反例见图 b）。因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序（X坐标小的 排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水平和垂直 情况的判断正确），这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也 在多边形内，则该线段一定在多边形内。证明如下：命题 1：如果线段和多边形的两相邻交点P1 , P2的中点P也在多边形内，则P1, P2之间的所 有点都

14、在多边形内。证明：假设P1,P2之间含有不在多边形内的点，不妨设该点为Q,在P1, P之间，因为多边形 是闭合曲线，所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，P属于多边 性内部，P1-Q-P完全连续，所以P1Q和QP一定跨越多边形的边界，因此在P1,P之间至少还有 两个该线段和多边形的交点，这和P1P2是相邻两交点矛盾，故命题成立。证毕。由命题 1 直接可得出推论：推论 2：设多边形和线段PQ的交点依次为P1,P2,Pn,其中Pi和Pi+1是相邻两交点，线段 PQ在多边形内的充要条件是：P，Q在多边形内且对于i =1, 2,，n-1，Pi ,Pi+1的中点也在 多边形内。在实际编程中，没有必要计算所有的交点， 首先应判断线段和多边形的边是否内交， 倘若线 段和多边形的某条边内交则线段一定在多边形外； 如果线段和多边形的每一条边都不内交，则线 段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。至此我们得出算法如下：f线端PQ的端点不都在多边形内then return false;点集pointSet初始化为空；for 多边形的每条边 sdo if 线段的某个端点在 s 上then 将该端点加入 pointSet；else f s的某个端点在线段PQ上then 将该端点加