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

判斷點是否在多邊形中：

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

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

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

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

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

判斷線段是否在多邊形內(nèi)：

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

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

 

因此我們可以先求出所有和線段相交的多邊形的頂點，然后按照X-Y坐標(biāo)排序(X坐標(biāo)小的排在前面，對于X坐標(biāo)相同的點，Y坐標(biāo)小的排在前面，這種排序準(zhǔn)則也是為了保證水平和垂直情況的判斷正確)，這樣相鄰的兩個點就是在線段上相鄰的兩交點，如果任意相鄰兩點的中點也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。

證明如下：

命題1：
如果線段和多邊形的兩相鄰交點P1 ，P2的中點P' 也在多邊形內(nèi)，則P1, P2之間的所有點都在多邊形內(nèi)。

證明：
假設(shè)P1,P2之間含有不在多邊形內(nèi)的點，不妨設(shè)該點為Q，在P1, P'之間，因為多邊形是閉合曲線，所以其內(nèi)外部之間有界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P'屬于多邊性內(nèi)部，P1-Q-P'完全連續(xù)，所以P1Q和QP'一定跨越多邊形的邊界，因此在P1,P'之間至少還有兩個該線段和多邊形的交點，這和P1P2是相鄰兩交點矛盾，故命題成立。證畢。

由命題1直接可得出推論：
推論2：
設(shè)多邊形和線段PQ的交點依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點，線段PQ在多邊形內(nèi)的充要條件是：P，Q在多邊形內(nèi)且對于i =1, 2,……, n-1，Pi ,Pi+1的中點也在多邊形內(nèi)。
在實際編程中，沒有必要計算所有的交點，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只要判斷點是否在線段上就可以了。
至此我們得出算法如下：
    if 線端PQ的端點不都在多邊形內(nèi) 
      then return false;
    點集pointSet初始化為空;
    for 多邊形的每條邊s
      do if 線段的某個端點在s上
           then 將該端點加入pointSet;
         else if s的某個端點在線段PQ上
           then 將該端點加入pointSet;
         else if s和線段PQ相交 // 這時候已經(jīng)可以肯定是內(nèi)交了
           then return false;
    將pointSet中的點按照X-Y坐標(biāo)排序;
    for pointSet中每兩個相鄰點 pointSet[i] , pointSet[ i+1]
      do if pointSet[i] , pointSet[ i+1] 的中點不在多邊形中
           then return false;
    return true;
這個過程中的排序因為交點數(shù)目肯定遠(yuǎn)小于多邊形的頂點數(shù)目n，所以最多是常數(shù)級的復(fù)雜度，幾乎可以忽略不計。因此算法的時間復(fù)雜度也是O(n)。

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

設(shè)一條線段為L0 = P1P2，另一條線段或直線為L1 = Q1Q2 ，要計算的就是L0和L1的交點。
1． 首先判斷L0和L1是否相交（方法已在前文討論過），如果不相交則沒有交點，否則說明L0和L1一定有交點，下面就將L0和L1都看作直線來考慮。

2． 如果P1和P2橫坐標(biāo)相同，即L0平行于Y軸

a) 若L1也平行于Y軸，

i. 若P1的縱坐標(biāo)和Q1的縱坐標(biāo)相同，說明L0和L1共線，假如L1是直線的話他們有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）；
ii. 否則說明L0和L1平行，他們沒有交點；

b) 若L1不平行于Y軸，則交點橫坐標(biāo)為P1的橫坐標(biāo)，代入到L1的直線方程中可以計算出交點縱坐標(biāo)；

3． 如果P1和P2橫坐標(biāo)不同，但是Q1和Q2橫坐標(biāo)相同，即L1平行于Y軸，則交點橫坐標(biāo)為Q1的橫坐標(biāo)，代入到L0的直線方程中可以計算出交點縱坐標(biāo)；

4． 如果P1和P2縱坐標(biāo)相同，即L0平行于X軸

a) 若L1也平行于X軸，

i. 若P1的橫坐標(biāo)和Q1的橫坐標(biāo)相同，說明L0和L1共線，假如L1是直線的話他們有無窮的交點，假如L1是線段的話可用"計算兩條共線線段的交點"的算法求他們的交點（該方法在前文已討論過）；
ii. 否則說明L0和L1平行，他們沒有交點；

b) 若L1不平行于X軸，則交點縱坐標(biāo)為P1的縱坐標(biāo)，代入到L1的直線方程中可以計算出交點橫坐標(biāo)；

5． 如果P1和P2縱坐標(biāo)不同，但是Q1和Q2縱坐標(biāo)相同，即L1平行于X軸，則交點縱坐標(biāo)為Q1的縱坐標(biāo)，代入到L0的直線方程中可以計算出交點橫坐標(biāo)；

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

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

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

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

2. 如果L平行于Y軸，

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

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

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