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再多邊形內部。


===

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 Cliff 的頭像
    Cliff

    Cliff的部落格

    Cliff 發表在 痞客邦 留言(0) 人氣()