最近研究了下測試點(diǎn)是否在多邊形內(nèi)痛阻，以下代碼在網(wǎng)上流傳很廣阱当，作者都不知道是誰”滋恚看別人的分析油坝，還是不太明白刨裆，還是要自己畫圖就研究下帆啃。這主要是利用射線與多邊形相交的奇偶次數(shù)判斷是否在多邊形內(nè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 是頂點(diǎn)數(shù)量，vertx卖子、verty分別為x洋闽，y頂點(diǎn)數(shù)組，testx诫舅、testy分別為測試點(diǎn)x，y頂點(diǎn)这弧。
i = 0, j = nvert-1; i < nvert; j = i++
再看循環(huán)匾浪，i = 0時卷哩，j = 頂點(diǎn)數(shù)減一将谊，執(zhí)行循環(huán)尊浓，第一輪循環(huán)結(jié)束栋齿，i 賦值給 j 瓦堵，跟著 i 自增柒巫，即是
循環(huán).png
?
接下來，主要是這個函數(shù)的核心谷丸。由兩個判斷組成，
((verty[i]>testy) != (verty[j]>testy))
和
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i])
?
?
1应结、理解 ((verty[i]>testy) != (verty[j]>testy))
條件1
將 (verty[i]>testy) 與 (verty[j]>testy) 當(dāng)成兩個布爾值來看待刨疼。所以只能一真一假，
((verty[i]>testy) != (verty[j]>testy)) 才返回真鹅龄。那么if的第一個條件才成立揩慕。
交點(diǎn)
看圖片，當(dāng)testy同時大于一條邊的兩個點(diǎn)時扮休，即使有交點(diǎn)也是在矩形外邊迎卤。
2、理解 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i])
條件2
還是看圖理解吧玷坠，文字總說不清楚蜗搔。
其實(shí)就是計算射線與多邊形交點(diǎn)的x值聘芜，再比較測試點(diǎn)的x值是否小于交點(diǎn)x值。通過比值求得交點(diǎn)瞎饲，應(yīng)該是叫“相似三角形”，幾何都給回老師了仗哨，哈。
【 編輯于 2018-7-26 】
