计算几何的常用算法

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

1、计算几何的常用算法计算几何的常用算法计算几何的常用算法1. 矢量减法设二维矢量 P = （x1,y1） ，Q = (x2,y2)则矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )显然有性质 P - Q = - ( Q - P )如不加说明，下面所有的点都看作矢量，两点的减法就是矢量相减；2.矢量叉积设矢量 P = （x1,y1） ，Q = (x2,y2)则矢量叉积定义为： P Q = x1*y2 - x2*y1 得到的是一个标量显然有性质 P Q = - ( Q P ) P ( - Q ) = - ( P Q )如不加说明，下面所有的点都看作矢量，点的乘法看作矢量叉

2、积；叉乘的重要性质： 若 P Q 0 , 则 P 在 Q 的顺时针方向 若 P Q 若 P Q = 0 , 则 P 与 Q 共线，但可能同向也可能反向3.判断点在线段上设点为 Q，线段为 P1P2 ，判断点 Q 在该线段上的依据是：( Q - P1 ) ( P2 - P1 ) = 0 且 Q 在以 P1，P2 为对角顶点的矩形内4.判断两线段是否相交我们分两步确定两条线段是否相交：(1) 快速排斥试验设以线段 P1P2 为对角线的矩形为 R， 设以线段 Q1Q2 为对角线的矩形为 T，如果R 和 T 不相交，显然两线段不会相交；(2) 跨立试验如果两线段相交，则两线段必然相互跨立对方，如图 1

3、 所示。在图1 中，P1P2 跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) ( Q2 - Q1 ) * ( P2 - Q1 ) ( Q2 - Q1 ) 0当( P1 - Q1 ) ( Q2 - Q1 ) = 0 时，说明( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2 上；同理，( Q2 - Q1 ) ( P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2 上。所以判断 P1P2 跨立 Q1Q2 的依据是：( P1 - Q1

4、 ) ( Q2 - Q1 ) * ( Q2 - Q1 ) ( P2 - Q1 ) 0同理判断 Q1Q2 跨立 P1P2 的依据是：( Q1 - P1 ) ( P2 - P1 ) * ( P2 - P1 ) ( Q2 - P1 ) 0至此已经完全解决判断线段是否相交的问题。5.判断线段和直线是否相交如果线段 P1P2 和直线 Q1Q2 相交，则 P1P2 跨立 Q1Q2，即：( P1 - Q1 ) ( Q2 - Q1 ) * ( Q2 - Q1 ) ( P2 - Q1 ) 06.判断矩形是否包含点只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。6.判断线段、折线、多边形是否在矩形中

5、因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。7.判断矩形是否在矩形中只要比较左右边界和上下边界就可以了。8.判断圆是否在矩形中圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。9.判断点是否在多边形中以点 P 为端点，向左方作射线 L，由于多边形是有界的，所以射线L 的左端一定在多边形外，考虑沿着 L 从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，所以很容易看出当 L 和多边形的交点数目 C 是奇数的时候，P 在多边形内，是偶数的话P 在多边形外。但是有些特殊情况要加以考

6、虑。如果 L 和多边形的顶点相交，有些情况下交点只能计算一个，有些情况下交点不应被计算（自己画个图就明白了） ；如果 L 和多边形的一条边重合，这条边应该被忽略不计。为了统一起见，我们在计算射线 L 和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和 L 相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于 P 在多边形边上的情形，直接可判断 P 属于多边行。由此得出算法的伪代码如下：1. count 0;2. 以 P 为端点，作从右向左的射线 L;3. for 多边形的每条边 s4. do if P 在边 s 上5. then retur

7、n true;6. if s 不是水平的7. then if s 的一个端点在 L 上且该端点是 s 两端点中纵坐标较大的端点9. then count count+110. else if s 和 L 相交11. then count count+1;12. if count mod 2 = 113. then return true14. else return false;其中做射线 L 的方法是：设 P的纵坐标和 P 相同，横坐标为正无穷大（很大的一个正数） ，则 P 和 P就确定了射线 L。这个算法的复杂度为 O(n)。10.判断线段是否在多边形内线段在多边形内的一个必要条件是线段的

8、两个端点都在多边形内；如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点） ，因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有一部分在多边形外。于是我们得到线段在多边形内的第二个必要条件：线段和多边形的所有边都不内交；线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可以先求出所有和线段相交的多边形的顶点，然后按照 X-Y 坐标排序，这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，则该线段一定在多边形内。证明如下：命题

9、1：如果线段和多边形的两相邻交点 P1 ，P2 的中点 P 也在多边形内，则 P1, P2 之间的所有点都在多边形内。证明：假设 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是

10、相邻两交点，线段PQ 在多边形内的充要条件是：P，Q 在多边形内且对于 i =1, 2, n-1，Pi ,Pi+1的中点也在多边形内。在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。至此我们得出算法如下：1. if 线端 PQ 的端点不都在多边形内2. then return false;3. 点集 pointSet 初始化为空;4. for 多边形的每条边 s5. do if 线段的某个端点在 s

11、 上6. then 将该端点加入 pointSet;7. else if s 的某个端点在线段 PQ 上8. then 将该端点加入 pointSet;9. else if s 和线段 PQ 相交 / 这时候可以肯定是内交10. then return false;11. 将 pointSet 中的点按照 X-Y 坐标排序，X 坐标小的排在前面，对于 X 坐标相同的点，Y 坐标小的排在前面；12. for pointSet 中每两个相邻点 pointSeti , pointSet i+113. do if pointSeti , pointSet i+1 的中点不在多边形中14. then r

12、eturn false;15. return true;这个算法的复杂度也是 O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目 n，所以最多是常数级的复杂度，几乎可以忽略不计。11.判断折线在多边形内只要判断折线的每条线段是否都在多边形内即可。设折线有 m 条线段，多边形有 n 个顶点，则复杂度为 O(m*n)。12.判断多边形是否在多边形内只要判断多边形的每条边是否都在多边形内即可。判断一个有 m 个顶点的多边形是否在一个有 n 个顶点的多边形内复杂度为 O(m*n)。13.判断矩形是否在多边形内将矩形转化为多边形，然后再判断是否在多边形内。14.判断圆是否在多边形内只要计算圆心到

13、多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。15.判断点是否在圆内计算圆心到该点的距离，如果小于等于半径则该点在圆内。16.判断线段、折线、矩形、多边形是否在圆内因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。17.判断圆是否在圆内设两圆为 O1,O2，半径分别为 r1, r2，要判断 O2 是否在 O1 内。先比较 r1，r2 的大小，如果 r1 r 则 L 和圆没有交点；c)利用勾股定理，可以求出两交点坐标，如图 6(a)所示；但要注意考虑 L 和圆的相切情况3.如果 L 平行于 X 轴，做法与 L 平行于 Y 轴的情况类似；4.如果 L 既不平行 X 轴也不平行 Y 轴，可以求出 L 的斜率 K，然后列出 L 的点斜式方程，和圆方程联立即可求解出 L 和圆的两个交点；5.如果 L 是线段，对于 2，3，4 中求出的交点还要分别判断是否属于该线段的范围内。