基于線性方程的凸多邊形內(nèi)外點(diǎn)判別算法研究

關(guān)鍵詞：凸多邊形；線性方程；高精度；點(diǎn)包含測(cè)試

中圖分類號(hào)：ＴＰ３９１ 文獻(xiàn)標(biāo)志碼：Ａ 文章編號(hào)：１００１-８３９５（２０２３）０４-０５６０-０９

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

點(diǎn)與多邊形位置關(guān)系的判別算法，即點(diǎn)包含算法，是多個(gè)領(lǐng)域的研究基礎(chǔ)，目的在于檢測(cè)目標(biāo)點(diǎn)位于給定多邊形的內(nèi)部或外部，在計(jì)算幾何、計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)等領(lǐng)域均有大量的研究與應(yīng)用． 平面點(diǎn)包含算法是三維點(diǎn)包含算法的基礎(chǔ)［１］． 傳統(tǒng)多邊形內(nèi)外點(diǎn)判別算法主要有：射線法［２-４］、轉(zhuǎn)角法［５］、面積和法［６］等．

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

（ａ）射線穿過(guò)多邊形一個(gè)或多個(gè)頂點(diǎn)． 當(dāng)從待測(cè)點(diǎn)發(fā)出的射線經(jīng)過(guò)多邊形的一個(gè)或多個(gè)頂點(diǎn)時(shí)，根據(jù)交點(diǎn)個(gè)數(shù)的奇偶性進(jìn)行內(nèi)外點(diǎn)測(cè)試是錯(cuò)誤的，如圖１ 中的Ｒ１、Ｒ４；

（ｂ）射線與多邊形的某一條或多條邊重合．當(dāng)從待測(cè)點(diǎn)發(fā)出的射線與多邊形的某一條或多條邊重合時(shí)，傳統(tǒng)射線法的計(jì)算規(guī)則也不再適用，如圖１ 中的Ｒ２；

（ｃ）待測(cè)點(diǎn)與多邊形的某個(gè)頂點(diǎn)重合． 當(dāng)待測(cè)點(diǎn)與多邊形的某個(gè)頂點(diǎn)重合時(shí)，傳統(tǒng)射線法的計(jì)算規(guī)則同樣也會(huì)出錯(cuò)，導(dǎo)致傳統(tǒng)射線法判斷失誤，如圖１ 中的Ｒ３．