原文鏈接：http://cschf.spaces.live.com/blog/cns!E113B8D05D833E2B!140.entry
寫幾點不熟悉的
12. 判斷點是否在多邊形中
13. 判斷線段是否在多邊形內
25. 計算線段或直線與線段的交點
27. 求線段或直線與圓的交點

判斷點是否在多邊形中：

判斷點P是否在多邊形中是計算幾何中一個非常基本但是十分重要的算法。以點P為端點，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無窮遠處開始自左向右移動，遇到和多邊形的第一個交點的時候，進入到了多邊形的內部，遇到第二個交點的時候，離開了多邊形，……所以很容易看出當L和多邊形的交點數目C是奇數的時候，P在多邊形內，是偶數的話P在多邊形外。

但是有些特殊情況要加以考慮。如圖下圖(a)(b)(c)(d)所示。在圖(a)中，L和多邊形的頂點相交，這時候交點只能計算一個；在圖(b)中，L和多邊形頂點的交點不應被計算；在圖(c)和(d) 中，L和多邊形的一條邊重合，這條邊應該被忽略不計。如果L和多邊形的一條邊重合，這條邊應該被忽略不計。

為了統一起見，我們在計算射線L和多邊形的交點的時候，1。對于多邊形的水平邊不作考慮；2。對于多邊形的頂點和L相交的情況，如果該頂點是其所屬的邊上縱坐標較大的頂點，則計數，否則忽略；3。對于P在多邊形邊上的情形，直接可判斷P屬于多邊行。由此得出算法的偽代碼如下：
    count ← 0;
    以P為端點，作從右向左的射線L; 
    for 多邊形的每條邊s
     do if P在邊s上 
          then return true;
        if s不是水平的
          then if s的一個端點在L上
                 if 該端點是s兩端點中縱坐標較大的端點
                   then count ← count+1
               else if s和L相交
                 then count ← count+1;
    if count mod 2 = 1 
      then return true;
    else return false;
其中做射線L的方法是：設P'的縱坐標和P相同，橫坐標為正無窮大（很大的一個正數），則P和P'就確定了射線L。

判斷點是否在多邊形中的這個算法的時間復雜度為O(n)。

另外還有一種算法是用帶符號的三角形面積之和與多邊形面積進行比較，這種算法由于使用浮點數運算所以會帶來一定誤差，不推薦大家使用。

判斷線段是否在多邊形內：

線段在多邊形內的一個必要條件是線段的兩個端點都在多邊形內，但由于多邊形可能為凹，所以這不能成為判斷的充分條件。如果線段和多邊形的某條邊內交（兩線段內交是指兩線段相交且交點不在兩線段的端點），因為多邊形的邊的左右兩側分屬多邊形內外不同部分，所以線段一定會有一部分在多邊形外(見圖a)。于是我們得到線段在多邊形內的第二個必要條件：線段和多邊形的所有邊都不內交。

線段和多邊形交于線段的兩端點并不會影響線段是否在多邊形內；但是如果多邊形的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含于多邊形內部（反例見圖b)。

 

因此我們可以先求出所有和線段相交的多邊形的頂點，然后按照X-Y坐標排序(X坐標小的排在前面，對于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的中點也在多邊形內。
在實際編程中，沒有必要計算所有的交點，首先應判斷線段和多邊形的邊是否內交，倘若線段和多邊形的某條邊內交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只要判斷點是否在線段上就可以了。
至此我們得出算法如下：
    if 線端PQ的端點不都在多邊形內 
      then return false;
    點集pointSet初始化為空;
    for 多邊形的每條邊s
      do if 線段的某個端點在s上
           then 將該端點加入pointSet;
         else if s的某個端點在線段PQ上
           then 將該端點加入pointSet;
         else if s和線段PQ相交 // 這時候已經可以肯定是內交了
           then return false;
    將pointSet中的點按照X-Y坐標排序;
    for pointSet中每兩個相鄰點 pointSet[i] , pointSet[ i+1]
      do if pointSet[i] , pointSet[ i+1] 的中點不在多邊形中
           then return false;
    return true;
這個過程中的排序因為交點數目肯定遠小于多邊形的頂點數目n，所以最多是常數級的復雜度，幾乎可以忽略不計。因此算法的時間復雜度也是O(n)。

計算線段或直線與線段的交點:

設一條線段為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) 聯立兩直線的方程組可以解出交點來
這個算法并不復雜，但是要分情況討論清楚，尤其是當兩條線段共線的情況需要單獨考慮，所以在前文將求兩條共線線段的算法單獨寫出來。另外，一開始就先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結果是相交，那么在后面就可以將線段全部看作直線來考慮。需要注意的是，我們可以將直線或線段方程改寫為ax+by+c=0的形式，這樣一來上述過程的部分步驟可以合并，縮短了代碼長度，但是由于先要求出參數，這種算法將花費更多的時間。

求線段或直線與圓的交點:

設圓心為O，圓半徑為r，直線（或線段）L上的兩點為P1,P2。

1. 如果L是線段且P1，P2都包含在圓O內，則沒有交點；否則進行下一步。

2. 如果L平行于Y軸，

a) 計算圓心到L的距離dis；
b) 如果dis > r 則L和圓沒有交點；
c) 利用勾股定理，可以求出兩交點坐標，但要注意考慮L和圓的相切情況。
3. 如果L平行于X軸，做法與L平行于Y軸的情況類似；

4. 如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然后列出L的點斜式方程，和圓方程聯立即可求解出L和圓的兩個交點；

5. 如果L是線段，對于2，3，4中求出的交點還要分別判斷是否屬于該線段的范圍內。