我認(rèn)為下面的代碼是最好的解決方案(摘自這里):
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;}論點(diǎn)
內(nèi)涵
多邊形中的頂點(diǎn)數(shù)。是否在結(jié)尾重復(fù)第一個(gè)頂點(diǎn)，已經(jīng)在上面提到的文章中討論過了。vertx，verty
數(shù)組包含多邊形頂點(diǎn)的x坐標(biāo)和y坐標(biāo)。遺囑
*測試點(diǎn)的x和y坐標(biāo)。
它既短又有效，同時(shí)適用于凸多邊形和凹多邊形。正如前面所建議的，您應(yīng)該首先檢查包圍矩形并分別處理多邊形孔。
這背后的想法很簡單。作者將其描述如下：
我從測試點(diǎn)水平地運(yùn)行一條半無限射線(增加x，固定y)，并計(jì)算它穿過多少個(gè)邊。在每個(gè)十字路口，光線在內(nèi)部和外部之間切換。這叫做Jordan曲線定理。
每次水平射線穿過任何邊緣時(shí)，變量c都從0切換到1和1到0?；旧?，它是跟蹤交叉邊的數(shù)目是偶數(shù)還是奇數(shù)。0表示偶數(shù)，1表示奇數(shù)。
