基于線性方程的凸多邊形內外點判別算法研究

關鍵詞：凸多邊形；線性方程；高精度；點包含測試

中圖分類號：ＴＰ３９１ 文獻標志碼：Ａ 文章編號：１００１-８３９５（２０２３）０４-０５６０-０９

ｄｏｉ：１０． ３９６９ ／ ｊ． ｉｓｓｎ． １００１-８３９５． ２０２３． ０４． ０１７

點與多邊形位置關系的判別算法，即點包含算法，是多個領域的研究基礎，目的在于檢測目標點位于給定多邊形的內部或外部，在計算幾何、計算機圖形學、地理信息系統等領域均有大量的研究與應用． 平面點包含算法是三維點包含算法的基礎［１］． 傳統多邊形內外點判別算法主要有：射線法［２-４］、轉角法［５］、面積和法［６］等．

１）射線法． 最早提出的點包含算法，其基本原理可描述為：以待測點為端點，發出一條射線，若該射線與多邊形的交點數為奇數，則該點位于多邊形內，反之則位于多邊形外． 射線法適用于任意多邊形，且不需要考慮精度誤差和多邊形點給出的順序． 由于射線發出的隨機性，對于一些特殊情況，射線法判斷將會出現異常：

（ａ）射線穿過多邊形一個或多個頂點． 當從待測點發出的射線經過多邊形的一個或多個頂點時，根據交點個數的奇偶性進行內外點測試是錯誤的，如圖１ 中的Ｒ１、Ｒ４；

（ｂ）射線與多邊形的某一條或多條邊重合．當從待測點發出的射線與多邊形的某一條或多條邊重合時，傳統射線法的計算規則也不再適用，如圖１ 中的Ｒ２；

（ｃ）待測點與多邊形的某個頂點重合． 當待測點與多邊形的某個頂點重合時，傳統射線法的計算規則同樣也會出錯，導致傳統射線法判斷失誤，如圖１ 中的Ｒ３．