[發(fā)明專利]一種判斷目標(biāo)點(diǎn)是否位于多邊形區(qū)域內(nèi)部的方法

在審

• 申請?zhí)枺?/td>: 201210398610.2
• 申請日: 2012-10-19
• 公開（公告）號(hào): CN102982562A
• 公開（公告）日: 2013-03-20
• 發(fā)明（設(shè)計(jì)）人: 李健;劉中秋
• 申請（專利權(quán)）人: 浙江中正智能科技有限公司
• 主分類號(hào): G06T7/60
• 分類號(hào): G06T7/60
• 代理公司: 上海漢聲知識(shí)產(chǎn)權(quán)代理有限公司 31236
• 代理人: 胡晶

技術(shù)領(lǐng)域

????計(jì)算機(jī)圖形技術(shù)和計(jì)算機(jī)幾何技術(shù)領(lǐng)域，特別涉及一種判斷目標(biāo)點(diǎn)是否位于多邊形區(qū)域內(nèi)部的方法。

?

背景技術(shù)

點(diǎn)是否位于多邊形內(nèi)的判斷計(jì)算，是計(jì)算幾何中的一個(gè)基本問題，這方面的方法在計(jì)算機(jī)圖形學(xué)、模糊識(shí)別、地理信息系統(tǒng)等眾多領(lǐng)域有著廣泛的應(yīng)用。

傳統(tǒng)的判定點(diǎn)是否位于多邊形內(nèi)的方法有如下幾種：

面積法：多邊形的所有邊和目標(biāo)點(diǎn)組成的三角形面積和是否等于總的多邊形面積，如果相等，則在內(nèi)部。反之在外部。這種方法計(jì)算量較大，用到的主要計(jì)算是查乘。

夾角和法：判斷所有邊和目標(biāo)點(diǎn)的夾角和，如果夾角和為360度，則在多邊形內(nèi)部。計(jì)算量比面積法稍小，用到主要是點(diǎn)乘和求模計(jì)算。

引射線法。從目標(biāo)點(diǎn)出發(fā)引一條射線，判斷這條射線和所有邊的交點(diǎn)數(shù)目。如果有奇數(shù)個(gè)交點(diǎn)，則說明在內(nèi)部，如果有偶數(shù)個(gè)交點(diǎn)，則說明在外部。此方法存在較多的特殊情況處理，如經(jīng)過頂點(diǎn)或者與邊線重疊等。

在中國專利CN200710121506.8中公開了一種判定方法，其先對多邊形進(jìn)行凸剖分，并建立二叉樹來管理這些凸邊行，然后，根據(jù)被檢測點(diǎn)的坐標(biāo)位置，對所建立的二叉樹進(jìn)行考察，以找到該二叉樹的一葉節(jié)點(diǎn)對應(yīng)的凸多邊形，再檢測該點(diǎn)是否位于這個(gè)凸變形內(nèi)；這種方法在多邊形的預(yù)處理的時(shí)間、空間需求和判斷計(jì)算等各個(gè)方面具有相同的復(fù)雜度

現(xiàn)有技術(shù)存在以下的問題：

1、判斷方法步驟復(fù)雜、繁瑣、不夠簡易；

2、空間需求比較大、計(jì)算速度較慢；

???3、判斷點(diǎn)是否在多邊形內(nèi)的準(zhǔn)確度不高。

發(fā)明內(nèi)容

為了克服現(xiàn)有技術(shù)的缺陷，本發(fā)明公開了一種判斷目標(biāo)點(diǎn)是否位于多邊形區(qū)域內(nèi)部的方法，這種定位方法判斷方法計(jì)算量小，準(zhǔn)確度高，易于實(shí)現(xiàn)。

本發(fā)明公開了以下技術(shù)方案：

一種判斷目標(biāo)點(diǎn)是否位于多邊形區(qū)域內(nèi)部的方法，包括如下步驟：

S1：定義構(gòu)造規(guī)則：目標(biāo)點(diǎn)為P0，多邊形各頂點(diǎn)以順時(shí)針方向依次為P1，P2，P3，…，?Pi-1，Pi，Pi+1，…，Pn；

S2：遍歷所有的邊，如果目標(biāo)點(diǎn)P0在邊的法向投影范圍，則計(jì)算目標(biāo)點(diǎn)P0與該邊的距離D0i，否則計(jì)算目標(biāo)點(diǎn)P0與該邊兩個(gè)頂點(diǎn)的最小距離D0i，記錄最小距離，以及對應(yīng)的邊或者頂點(diǎn)；如果目標(biāo)點(diǎn)P0距離邊最近，那么選擇兩個(gè)頂點(diǎn)中的任意一個(gè)為Pi，如果目標(biāo)點(diǎn)距離頂點(diǎn)最近，那么以該頂點(diǎn)為Pi；同時(shí)以Pi點(diǎn)水平向右為X正向；

S3：計(jì)算角度

a)A_i1=∠XPiPi-1，A_i1為PiX以Pi為中心、順時(shí)針旋轉(zhuǎn)到P₁P_i-1所形成的角度；

b)A_i2=∠XPiPi+1，A_i2為PiX以Pi為中心、順時(shí)針旋轉(zhuǎn)到PiPi+1所形成的角度；

c)A_i0=∠XP_iP₀,A_i0為PiX以Pi為中心、順時(shí)針旋轉(zhuǎn)到PiP₀所形成的角度；

S4：通過計(jì)算三個(gè)角度之間的關(guān)系來判斷點(diǎn)的位置

a)如果A_i1>?A_i2，且A_i1?>A_i0>?A_i2，則目標(biāo)點(diǎn)P0在多邊形區(qū)域內(nèi)，否則在多邊形區(qū)域外；

b)如果A_i1<?A_i2，且A_i0?<A_i1或A_i0>?A_i2，則目標(biāo)點(diǎn)P0在多邊形區(qū)域內(nèi)，否則在多邊形區(qū)域外；

c)A_i1=A_i0或A_i2=A_i0，則判定為在多邊形邊線上。

較佳地，所述的判斷目標(biāo)點(diǎn)是否位于多邊形區(qū)域內(nèi)部的方法，還包括S5：如果多邊形為中間鏤空或者為環(huán)形，此多邊形包括外圈多邊形和內(nèi)圈多邊形，則滿足目標(biāo)點(diǎn)P0在外圈多邊形內(nèi)部，且目標(biāo)點(diǎn)P0在內(nèi)圈多邊形外部，否則目標(biāo)點(diǎn)P0在多邊形區(qū)域外。

較佳地，所述的判斷目標(biāo)點(diǎn)是否位于多邊形區(qū)域內(nèi)部的方法，其S2中如果有若干個(gè)頂點(diǎn)距離P0相等，可選取其中任意一頂點(diǎn)為Pi。