用途6：

判斷點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)。