在gmap（地理信息管理系統）中，判斷一個坐標是否在多邊形內部是個經常要遇到的問題。乍聽起來還挺復雜。根據W. Randolph Franklin 提出的PNPoly算法，只需區區幾行代碼就解決了這個問題。

假設多邊形的坐標存放在一個數組里，首先我們需要取得該數組在橫坐標和縱坐標的最大值和最小值，根據這四個點算出一個四邊型，首先判斷目標坐標點是否在這個四邊型之內，如果在這個四邊型之外，那可以跳過后面較為復雜的計算，直接返回false。

if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {

     // 如果這個測試都過不了。。。直接返回false；

}

接下來是核心算法部分：

int pnpoly (int nvert, float *vertx, float *verty, float testx, float testy) {

    int i, j, c = 0;

    for (i = 0, j = nvert-1; i < nvert; j = i++) {

        if ( ( (verty[i]>testy) != (verty[j]>testy) ) &&

(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )

            c = !c;

    }

    return c;

}

額，代碼就這么簡單，但到底啥意思呢：

首先，參數nvert 代表多邊形有幾個點。浮點數testx, testy代表待測試點的橫坐標和縱坐標，*vertx,*verty分別指向儲存多邊形橫縱坐標數組的首地址。

我們注意到，每次計算都涉及到相鄰的兩個點和待測試點，然后考慮兩個問題：

1. 被測試點的縱坐標testy是否在本次循環所測試的兩個相鄰點縱坐標范圍之內？即

verty[i] <testy < verty[j]

或者

verty[j] <testy < verty[i]

2. 待測點test是否在i,j兩點之間的連線之下？看不懂后半短if statement的朋友請自行在紙上寫下i,j兩點間的斜率公式，要用到一點初中解析幾何和不等式的知識范疇，對廣大碼農來說小菜一碟。

然后每次這兩個條件同時滿足的時候我們把返回的布爾量取反。

可這到底是啥意思啊？

這個表達式的意思是說，隨便畫個多邊形，隨便定一個點，然后通過這個點水平劃一條線，先數數看這條橫線和多邊形的邊相交幾次，（或者說先排除那些不相交的邊，第一個判斷條件），然后再數這條橫線穿越多邊形的次數是否為奇數，如果是奇數，那么該點在多邊形內，如果是偶數，則在多邊形外。詳細的數學證明這里就不做了，不過讀者可以自行畫多邊形進行驗證。

^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^

歡迎來我的淘寶店【老李飛充】，話費充值優惠靠譜，http://chinatrust.taobao.com

^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^