algorithm.txt

几何算法

几何算法 

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 )
如不加说明，下面所有的点都看作矢量，点的乘法看作矢量叉积； 

叉乘的重要性质：
        > 若 P × Q  > 0 ,  则P 在Q的顺时针方向
        > 若 P × Q  < 0 ,  则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所示。在图1中，P1P2跨立
Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( 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 - P1 ) × ( Q2 - P1 )  ≥  0 

至此已经完全解决判断线段是否相交的问题。 


5.判断线段和直线是否相交 

如果线段 P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即： 

( P1 - Q1 ) × ( Q2 - Q1 )  *  ( Q2 - Q1 ) × ( P2 - Q1 )  ≥  0 


6.判断矩形是否包含点 

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。 


7.判断线段、折线、多边形是否在矩形中 

因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。 


8.判断矩形是否在矩形中 

只要比较左右边界和上下边界就可以了。 


9.判断圆是否在矩形中 

圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距
离的最小值。 


10.判断点是否在多边形中 

以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多
边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的
时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所
以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话
P在多边形外。 

但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能
计算一个，有些情况下交点不应被计算（自己画个图就明白了）；如果L和多边形
的一条边重合，这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边
形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相
交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；
3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码
如下： 


1. count ← 0;
2. 以P为端点，作从右向左的射线L;
3. for 多边形的每条边s
4.   do if P在边s上
5.          then return true;
6.      if s不是水平的
7.          then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
9.                  then count ← count+1
10.              else if s和L相交
11.                 then count ← count+1;
12. if count mod 2 = 1
13.   then return true
14.   else return false; 

其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正
数），则P和P'就确定了射线L。这个算法的复杂度为O(n)。 

  

11.判断线段是否在多边形内 

线段在多边形内的一个必要条件是线段的两个端点都在多边形内； 

如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的
端点），因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有
一部分在多边形外。于是我们得到线段在多边形内的第二个必要条件：线段和多边
形的所有边都不内交； 

线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形
的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含与多边形内部。
因此我们可以先求出所有和线段相交的多边形的顶点，然后按照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的端点不都在多边形内
2.   then return false;
3. 点集pointSet初始化为空;
4. for 多边形的每条边s
5.   do if 线段的某个端点在s上
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中每两个相邻点 pointSet[i] , pointSet[ i+1]
13.    do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
14.         then return false;
15. return true;