close
原文出處：http://www.wretch.cc/blog/cwz0205/17885710
c++ 判斷點是否在多邊形內
再經典不過的算法了：
水平/垂直交叉點數判別法（適用於任意多邊形）
注意到如果從P作水平向左的射線的話，如果P在多邊形內部，那麼這條射線與多邊形的交點必為奇數，如果P在多邊形外部，則交點個數必為偶數（0也在內）。所以，我們可以順序考慮多邊形的每條邊，求出交點的總個數。還有一些特殊情況要考慮。假如考慮邊(P1,P2)，
1)如果射線正好穿過P1或者P2,那麼這個交點會被算作2次，處理辦法是如果P的從坐標與P1,P2中較小的縱坐標相同，則直接忽略這種情況
2)如果射線水平，則射線要麼與其無交點，要麼有無數個，這種情況也直接忽略。
3)如果射線豎直，而P0的橫坐標小於P1,P2的橫坐標，則必然相交。
4)再判斷相交之前，先判斷P是否在邊(P1,P2)的上面，如果在，則直接得出結論：P再多邊形內部。
===
全站熱搜
留言列表
