计算机几何常用算法.docx

: .
12月22日计算几何的常用算法(记载下，怕丢了)矢量减法设二维矢量P=(x1,y1)，Q=(x2,的第二个必要条件：线段和多边形的所有边都不内交；线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含与多边形内部。
因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序，这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，则该线段一定在多边形内。证明如下：
命题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是相邻两交点，线段PQ在多边形内的充要条件是:P，Q在多边形内且对于i=1,2,……，n-1，Pi,Pi+1的中点也在多边形内。
在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。
至此我们得出算法如下：
1. if线端PQ的端点不都在多边形内thenreturnfalse;点集pointSet初始化为空；for多边形的每条边sdoif线段的某个端点在s上then将该端点加入pointSet;elseifs的某个端点在线段PQ上then将该端点加入pointSet;elseifs和线段PQ相交//这时候可以肯定是内交thenreturnfalse;将pointSet中的点按照X-Y坐标排序，X坐标小的排在前面，
对于X坐标相同的点，Y坐标小的排在前面；forpointSet中每两个相邻点pointSet[i],pointSet[i+1]doifpointSet[i],pointSet[i+1]的中点不在多边形中thenreturnfalse;returntrue;这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。
判断折线在多边形内只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶点，则复杂度为O(m*n)。
判断多边形是否在多边形内只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。
判断矩形是否在多边形内将矩形转化为多边形，然后再判断是否在多边形内。
判断圆是否在多边形内只要计算圆心到多