[轉貼]計算幾何常用算法介紹

[轉貼]計算幾何常用算法介紹
http://www.blogjava.net/sishuiweilan/archive/2007/09/07/143474.html

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.判斷矩形是否包含點

只要判斷該點的橫坐標和縱坐標是否夾在矩形的左右邊和上下邊之間。

6.判斷線段、折線、多邊形是否在矩形中

因為矩形是個凸集，所以只要判斷所有端點是否都在矩形中就可以了。

7.判斷矩形是否在矩形中

只要比較左右邊界和上下邊界就可以了。

8.判斷圓是否在矩形中

圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小於等於圓心到矩形四邊的距離的最小值。

9.判斷點是否在多邊形中

以點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)。

10.判斷線段是否在多邊形內

線段在多邊形內的一個必要條件是線段的兩個端點都在多邊形內；如果線段和多邊形的某條邊內交（兩線段內交是指兩線段相交且交點不在兩線段的端點），因為多邊形的邊的左右兩側分屬多邊形內外不同部分，所以線段一定會有一部分在多邊形外。於是我們得到線段在多邊形內的第二個必要條件：線段和多邊形的所有邊都不內交；

線段和多邊形交於線段的兩端點並不會影響線段是否在多邊形內；但是如果多邊形的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含與多邊形內部。因此我們可以先求出所有和線段相交的多邊形的頂點，然後按照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;

這個算法的複雜度也是O(n)。其中的排序因為交點數目肯定遠小於多邊形的頂點數目n，所以最多是常數級的複雜度，幾乎可以忽略不計。

11.判斷折線在多邊形內只要判斷折線的每條線段是否都在多邊形內即可。設折線有m條線段，多邊形有n個頂點，則複雜度為O(m*n)。

12.判斷多邊形是否在多邊形內只要判斷多邊形的每條邊是否都在多邊形內即可。判斷一個有m個頂點的多邊形是否在一個有n個頂點的多邊形內複雜度為O(m*n)。

13.判斷矩形是否在多邊形內將矩形轉化為多邊形，然後再判斷是否在多邊形內。

14.判斷圓是否在多邊形內只要計算圓心到多邊形的每條邊的最短距離，如果該距離大於等於圓半徑則該圓在多邊形內。計算圓心到多邊形每條邊最短距離的算法在後文闡述。

15.判斷點是否在圓內計算圓心到該點的距離，如果小於等於半徑則該點在圓內。

16.判斷線段、折線、矩形、多邊形是否在圓內因為圓是凸集，所以只要判斷是否每個頂點都在圓內即可。

17.判斷圓是否在圓內

設兩圓為O1,O2，半徑分別為r1, r2，要判斷O2是否在O1內。先比較r1，r2的大小，如果r1<r2則O2不可能在O1內；否則如果兩圓心的距離大於r1 - r2 ，則O2不在O1內；否則O2在O1內。

18.計算點到線段的最近點

如果該線段平行於X軸（Y軸），則過點point作該線段所在直線的垂線，垂足很容易求得，然後計算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端點；

如果該線段不平行於X軸也不平行於Y軸，則斜率存在且不為0。設線段的兩端點為pt1和pt2，斜率為：
k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );
該直線方程為：
y = k* ( x - pt1.x) + pt1.y
其垂線的斜率為 - 1 / k，
垂線方程為：
y = (-1/k) * (x - point.x) + point.y
聯立兩直線方程解得：
x  =  ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1)
y  =  k * ( x - pt1.x) + pt1.y;

然後再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計算兩端點到垂足的距離，選擇距離垂足較近的端點返回。

19.計算點到折線、矩形、多邊形的最近點只要分別計算點到每條線段的最近點，記錄最近距離，取其中最近距離最小的點即可。

20.計算點到圓的最近距離

如果該點在圓心，則返回UNDEFINED
連接點P和圓心O，如果PO平行於X軸，則根據P在O的左邊還是右邊計算出最近點的橫坐標為centerPoint.x - radius 或 centerPoint.x + radius， 如圖4 (a)所示；如果PO平行於Y軸，則根據P在O的上邊還是下邊計算出最近點的縱坐標為centerPoint.y + radius 或 centerPoint.y - radius， 如圖4 (b)所示。

如果PO不平行於X軸和Y軸，則PO的斜率存在且不為0，如圖4(c)所示。這時直線PO斜率為
k = （ P.y - O.y ）/  ( P.x - O.x )
直線PO的方程為：
y = k * ( x - P.x) + P.y
設圓方程為:
(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，
聯立兩方程組可以解出直線PO和圓的交點，取其中離P點較近的交點即可。

21.計算兩條共線的線段的交點

對於兩條共線的線段，它們之間的位置關係有圖5所示的幾種情況。圖5(a)中兩條線段沒有交點；圖5 (b) 和 (d) 中兩條線段有無窮焦點；圖5 (c)中兩條線段有一個交點。設line1是兩條線段中較長的一條，line2是較短的一條，如果line1包含了line2的兩個端點，則是圖5(d)的情況，兩線段有無窮交點；如果line1只包含line2的一個端點，那麼如果line1的某個端點等於被line1包含的line2的那個端點，則是圖5(c)的情況，這時兩線段只有一個交點，否則就是圖5(c)的情況，兩線段也是有無窮的交點；如果line1不包含line2的任何端點，則是圖5(a)的情況，這時兩線段沒有交點。

22.計算線段或直線與線段的交點

設一條線段為L0 = P1P2，另一條線段或直線為L1 = Q1Q2 ，要計算的就是L0和L1的交點。

1.首先判斷L0和L1是否相交（方法已在前文討論過），如果不相交則沒有交點，否則說明L0和L1一定有交點，下面就將L0和L1都看作直線來考慮。

2.如果P1和P2橫坐標相同，即L0平行於Y軸
  a)若L1也平行於Y軸，
      i.若P1的縱坐標和Q1的縱坐標相同，說明L0和L1共線，假如L1是直線的話他們有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）；
      ii.否則說明L0和L1平行，他們沒有交點；
  b)若L1不平行於Y軸，則交點橫坐標為P1的橫坐標，代入到L1的直線方程中可以計算出交點縱坐標；
3.如果P1和P2橫坐標不同，但是Q1和Q2橫坐標相同，即L1平行於Y軸，則交點橫坐標為Q1的橫坐標，代入到L0的直線方程中可以計算出交點縱坐標；
4.如果P1和P2縱坐標相同，即L0平行於X軸
  a)若L1也平行於X軸，
      i.若P1的橫坐標和Q1的橫坐標相同，說明L0和L1共線，假如L1是直線的話他們有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）；
     ii.否則說明L0和L1平行，他們沒有交點；

   b)若L1不平行於X軸，則交點縱坐標為P1的縱坐標，代入到L1的直線方程中可以計算出交點橫坐標；
5.如果P1和P2縱坐標不同，但是Q1和Q2縱坐標相同，即L1平行於X軸，則交點縱坐標為Q1的縱坐標，代入到L0的直線方程中可以計算出交點橫坐標；
6.剩下的情況就是L1和L0的斜率均存在且不為0的情況
   a)計算出L0的斜率K0，L1的斜率K1 ；
   b)如果K1 = K2
      i.如果Q1在L0上，則說明L0和L1共線，假如L1是直線的話有無窮交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）；
     ii.如果Q1不在L0上，則說明L0和L1平行，他們沒有交點。
   c)聯立兩直線的方程組可以解出交點來

說明：這個算法並不複雜，但是要分情況討論清楚，尤其是當兩條線段共線的情況需要單獨考慮，所以在前文將求兩條共線線段的算法單獨寫出來。另外，一開始就先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結果是相交，那麼在後面就可以將線段全部看作直線來考慮。

23.求線段或直線與折線、矩形、多邊形的交點分別求與每條邊的交點即可。

24.求線段或直線與圓的交點

 

設圓心為O，圓半徑為r，直線（或線段）L上的兩點為P1,P2。
1.如果L是線段且P1，P2都包含在圓O內，則沒有交點；否則進行下一步
2.如果L平行於Y軸，
  a)計算圓心到L的距離dis
  b)如果dis > r 則L和圓沒有交點；
  c)利用勾股定理，可以求出兩交點坐標，如圖6(a)所示；但要注意考慮L和圓的相切情況
3.如果L平行於X軸，做法與L平行於Y軸的情況類似；
4.如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然後列出L的點斜式方程，和圓方程聯立即可求解出L和圓的兩個交點；
5.如果L是線段，對於2，3，4中求出的交點還要分別判斷是否屬於該線段的範圍內。