如何判斷一個(gè)點(diǎn)是否在一個(gè)多邊形內(nèi)？

假設(shè)多邊形的坐標(biāo)存放在一個(gè)數(shù)組里，首先我們需要取得該數(shù)組在橫坐標(biāo)和縱坐標(biāo)的最大值和最小值，根據(jù)這四個(gè)點(diǎn)算出一個(gè)四邊型，首先判斷目標(biāo)坐標(biāo)點(diǎn)是否在這個(gè)四邊型之內(nèi)，如果在這個(gè)四邊型之外，那可以跳過(guò)后面較為復(fù)雜的計(jì)算，直接返回false。

if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) { // 這個(gè)測(cè)試都過(guò)不了。。。直接返回false；

接下來(lái)是核心算法部分：

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;}

首先，參數(shù)nvert 代表多邊形有幾個(gè)點(diǎn)。浮點(diǎn)數(shù)testx, testy代表待測(cè)試點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，*vertx,*verty分別指向儲(chǔ)存多邊形橫縱坐標(biāo)數(shù)組的首地址。

我們注意到，每次計(jì)算都涉及到相鄰的兩個(gè)點(diǎn)和待測(cè)試點(diǎn)，然后考慮兩個(gè)問(wèn)題：

被測(cè)試點(diǎn)的縱坐標(biāo)testy是否在本次循環(huán)所測(cè)試的兩個(gè)相鄰點(diǎn)縱坐標(biāo)范圍之內(nèi)？即verty[i]<testy < verty[j] 或者verty[j] <testy < verty[i]

2. 待測(cè)點(diǎn)test是否在i,j兩點(diǎn)之間的連線之下？看不懂后半短if statement的朋友請(qǐng)自行在紙上寫下i,j兩點(diǎn)間的斜率公式，要用到一點(diǎn)初中解析幾何和不等式的知識(shí)范疇，對(duì)廣大碼農(nóng)來(lái)說(shuō)小菜一碟。