《计算几何算法概览》word版

《《计算几何算法概览》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、为有向线段(directedsegment)。如果有向线段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，其结果是一

3、个标量。显然有性质P×Q=-(Q×P)和P×(-Q)=-(P×Q)。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：若P×Q0,则P在Q的顺时针方向。若P×Q0,则P在Q的逆时针方向。若P×Q=0,则P与Q共线，但可能同向也可能反向。折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2-p0)×(p1-p0)的符号便可以确定折线段的拐向：若(p2-p0)×(p1-p0)0,

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

5、j)=yk=max(yi,yj)thenreturntrue；elsereturnfalse；特别要注意的是，由于需要考虑水平线段和垂直线段两种特殊情况，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)位于

6、矢量(Q2-Q1)的两侧，即(P1-Q1)×(Q2-Q1)*(P2-Q1)×(Q2-Q1)0。上式可改写成(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)0。当(P1-Q1)×(Q2-Q1)=0时，说明(P1-Q1)和(Q2-Q1)共线，但是因为已经通过快速排斥试验，所以P1一定在线段Q1Q2上；同理，(Q2-Q1)×(P2-Q1)=0说明P2一定在线段Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)=0。同理判断Q1Q2跨立P1P2的依据是：(Q1-P1)×(P2-P1)*(P2-

7、P1)×(Q2-P1)=0。具体情况如下图所示：在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除了这种过程外，大家也可以参考《算法导论》上的实现。有了上面的基础，这个算法就很容易了。如果线段P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即：(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)=0。只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。只要比较左右边界和上下边界就可以了。很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四

8、边的距离的最小值。判断点P是否在多边形