王盛春，王文成，譚雪晗，李 靜

?

加強(qiáng)局部簡(jiǎn)便計(jì)算的點(diǎn)在多邊形內(nèi)的高效判定

王盛春1,2，王文成1,2，譚雪晗1,2，李 靜3

(1. 中國(guó)科學(xué)院軟件研究所計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190； 2. 中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 100190； 3. 中國(guó)科學(xué)院動(dòng)物研究所動(dòng)物進(jìn)化與系統(tǒng)學(xué)院重點(diǎn)實(shí)驗(yàn)室，北京 100101)

多邊形；網(wǎng)格；簡(jiǎn)便計(jì)算；點(diǎn)在多邊形內(nèi)的檢測(cè)

點(diǎn)在多邊形內(nèi)的判定檢測(cè)(point-in-polygon test)是計(jì)算幾何中一個(gè)基本問題，在計(jì)算機(jī)圖形學(xué)、模式識(shí)別、衛(wèi)星定位系統(tǒng)及地理信息系統(tǒng)等方面有著廣泛的應(yīng)用[1]。該問題的基本描述為：給定一個(gè)多邊形與一個(gè)任意的點(diǎn)，判斷點(diǎn)是否位于多邊形內(nèi)。

點(diǎn)在多邊形內(nèi)的判定檢測(cè)算法可以分為2類：①算法不需要預(yù)處理，直接對(duì)多邊形進(jìn)行某些參數(shù)的計(jì)算得到判定結(jié)果，如常見的射線法[2-3]、轉(zhuǎn)角法[4]、面積和法[5]等。其中，經(jīng)典的射線法(ray-crossing)通過從測(cè)試點(diǎn)向某方向作一條射線，根據(jù)該射線與多邊形邊的交點(diǎn)數(shù)目的奇偶性進(jìn)行判定。若交點(diǎn)數(shù)目為奇數(shù)，則該點(diǎn)位于多邊形內(nèi)；否則位于多邊形外。這類算法簡(jiǎn)單直觀，可處理任意多邊形，通常被用作與其他算法對(duì)比的基準(zhǔn)算法。但這類算法需要逐邊操作，計(jì)算時(shí)間復(fù)雜度為()。②算法通過預(yù)處理，將多邊形分解為簡(jiǎn)單幾何形狀并進(jìn)行有序管理，如梯形法[6-7]、凸剖分法[8]、層次三角形法[9]等，或建立高效的空間劃分結(jié)構(gòu)，如均勻網(wǎng)格法[1,10-11]、分層法[12]、BSP樹法[8,13]等。通過預(yù)處理的組織管理，這類算法能夠降低判定計(jì)算的復(fù)雜度，如凸剖分法[8]復(fù)雜度為(log2)，其中為多邊形的邊數(shù)。文獻(xiàn)[1]對(duì)這些算法進(jìn)行了對(duì)比分析，并提出一種基于均勻網(wǎng)格的簡(jiǎn)便快速算法。近年來，學(xué)界雖然提出了一些新的相關(guān)算法，如文獻(xiàn)[14]提出的一種基于sign()函數(shù)的點(diǎn)在多邊形內(nèi)外判別算法，將二維平面內(nèi)的點(diǎn)轉(zhuǎn)化為三維空間在平面上的點(diǎn)，借用符號(hào)函數(shù)判斷待測(cè)點(diǎn)與多邊形的位置關(guān)系，但在計(jì)算效率上，仍與文獻(xiàn)[1]有所差距。

本文在文獻(xiàn)[1]算法的基礎(chǔ)上進(jìn)行如下改進(jìn)，以進(jìn)一步提高檢測(cè)速度：

(1) 本文將網(wǎng)格中心點(diǎn)屬性的計(jì)算，轉(zhuǎn)換為網(wǎng)格線交點(diǎn)屬性的計(jì)算，并記錄各網(wǎng)格交點(diǎn)一側(cè)(本文為其右側(cè))的網(wǎng)格邊與多邊形邊的相交情況。這樣，在計(jì)算多邊形的邊與網(wǎng)格單元相交的情況時(shí)，即可同時(shí)進(jìn)行這些計(jì)算，避免了另行計(jì)算網(wǎng)格單元中心點(diǎn)屬性的計(jì)算。

(2) 不同于文獻(xiàn)[1]僅記錄與其相交的多邊形的邊，本文方法記錄位于該網(wǎng)格中的多邊形的邊片段。由于邊片段的縮小，在測(cè)試線與多邊形的邊進(jìn)行求交計(jì)算時(shí)，可基于簡(jiǎn)單的坐標(biāo)對(duì)比大幅剔除不相交的邊，提高求交測(cè)試效率。

(3) 將測(cè)試點(diǎn)與附近已知屬性的網(wǎng)格交點(diǎn)的連線，轉(zhuǎn)換為與坐標(biāo)軸平行的2條相連的直線段。這依然遵循了射線法的基本原則，但與坐標(biāo)軸平行的直線段與多邊形的邊的求交計(jì)算，可簡(jiǎn)化以加速。

1 改進(jìn)算法

本文提出的新方法仍基于均勻網(wǎng)格方法，包括2個(gè)階段：預(yù)處理和判定計(jì)算。

(1) 預(yù)處理。首先建立均勻網(wǎng)格；然后記錄網(wǎng)格線與多邊形邊的交點(diǎn)坐標(biāo)以及各個(gè)網(wǎng)格單元中所包含的邊的片段；最后逐個(gè)計(jì)算網(wǎng)格交點(diǎn)位于多邊形內(nèi)/外的位置屬性。在該屬性計(jì)算時(shí)，位于包圍盒最外圍的網(wǎng)格交點(diǎn)一定是位于多邊形外的(所取的包圍盒比多邊形的緊致包圍盒稍大一點(diǎn))，而其他網(wǎng)格交點(diǎn)的位置屬性可依據(jù)其鄰近已知屬性的網(wǎng)格點(diǎn)、其之間連線與多邊形的邊的相交次數(shù)，即可獲得。

(2) 判定計(jì)算。首先確定待測(cè)點(diǎn)所在的網(wǎng)格單元；然后沿軸方向向鄰近網(wǎng)格邊做垂線，基于該垂線在網(wǎng)格邊上的交點(diǎn)得到最近網(wǎng)格交點(diǎn)，形成一條平行軸的連線；最后根據(jù)以上這兩條平行于坐標(biāo)軸的線段與多邊形邊的交點(diǎn)個(gè)數(shù)的奇偶性與網(wǎng)格交點(diǎn)的位置屬性，即可判斷待測(cè)點(diǎn)的位置屬性。

1.1 算法概述

1.1.1 預(yù)處理

預(yù)處理過程包括：創(chuàng)建均勻網(wǎng)格、記錄多邊形與網(wǎng)格邊的交點(diǎn)坐標(biāo)、記錄各個(gè)網(wǎng)格單元包含的多邊形邊的片段和計(jì)算網(wǎng)格頂點(diǎn)的位置屬性4部分。

與其他均勻網(wǎng)格法類似，由于網(wǎng)格分辨率的大小決定網(wǎng)格創(chuàng)建的效率和后期測(cè)試點(diǎn)屬性判斷的速度，因此，創(chuàng)建網(wǎng)格時(shí)需確定網(wǎng)格的分辨率。通常，網(wǎng)格的分辨率越高，則判定的時(shí)間越短。然而，當(dāng)網(wǎng)格的分辨率越高，預(yù)處理時(shí)間與存儲(chǔ)空間也將增加。因此，在實(shí)際應(yīng)用中，需要同時(shí)考慮到預(yù)處理時(shí)間、判定時(shí)間和存儲(chǔ)空間來決定優(yōu)化的網(wǎng)格分辨率。本文采用與文獻(xiàn)[1]相同的方法確定網(wǎng)格的分辨率，即設(shè)網(wǎng)格的寬長(zhǎng)比為，多邊形的邊數(shù)為，則和方向上的單元數(shù)分別為

文獻(xiàn)[1]在確定網(wǎng)格分辨率之后，采用數(shù)字微分分析器(digital differential analyzer，DDA)[15]算法將通過每個(gè)網(wǎng)格單元的整條邊記錄在相關(guān)單元中。由于整條邊與多個(gè)網(wǎng)格單元相關(guān)，求交測(cè)試時(shí)難以基于簡(jiǎn)單的坐標(biāo)對(duì)比剔除不相交的邊。對(duì)此，本文通過計(jì)算多邊形邊與網(wǎng)格邊的交點(diǎn)，得到各網(wǎng)格單元中多邊形邊的片段。這樣，基于簡(jiǎn)單的坐標(biāo)對(duì)比，可提高剔除不相交邊的概率，有利于加速。

各網(wǎng)格線與多邊形邊的交點(diǎn)，可形成順序排列的數(shù)組。由于各條網(wǎng)格線的某一坐標(biāo)值是相同的，因此本文方法僅存儲(chǔ)網(wǎng)格線上變化的坐標(biāo)值，從而降低存儲(chǔ)空間的消耗量。由此，各網(wǎng)格交點(diǎn)，可基于其之間連線上的交點(diǎn)個(gè)數(shù)，得到其位置屬性。

圖1為計(jì)算網(wǎng)格頂點(diǎn)位置屬性的一個(gè)實(shí)例。最外層網(wǎng)格邊上的網(wǎng)格點(diǎn)均位于多邊形外，如藍(lán)色點(diǎn)所示。與文獻(xiàn)[1]類似，根據(jù)已知位置屬性的網(wǎng)格交點(diǎn)，考察相鄰網(wǎng)格點(diǎn)間連線與多邊形邊的相交次數(shù)，可推知相鄰網(wǎng)格點(diǎn)的位置屬性。以未知鄰近網(wǎng)格點(diǎn)(3,1)為例，已知(3,0)點(diǎn)位于多邊形外，網(wǎng)格邊(3,0)(3,1)與1條多邊形的邊相交，因此(3,1)點(diǎn)位于多邊形內(nèi)。同理，由于網(wǎng)格邊(3,1)(3,2)與多邊形的邊沒有相交，可推知(3,2)點(diǎn)位于多邊形內(nèi)。

1.1.2 判定計(jì)算

在確定一個(gè)待測(cè)點(diǎn)的位置屬性時(shí)，本文方法首先確定待測(cè)點(diǎn)所在的網(wǎng)格單元；然后沿軸方向向鄰近的網(wǎng)格邊做垂線，基于該垂線與網(wǎng)格邊的交點(diǎn)找到最近網(wǎng)格頂點(diǎn)，形成一條平行軸的連線，最后依據(jù)兩條平行于坐標(biāo)軸的線段與多邊形邊交點(diǎn)個(gè)數(shù)的奇偶性與網(wǎng)格交點(diǎn)的位置屬性，判斷待測(cè)點(diǎn)的位置屬性。

圖1 計(jì)算網(wǎng)格點(diǎn)位置屬性的實(shí)例圖

以圖2中的待測(cè)點(diǎn)1為例。首先，定位1點(diǎn)位于網(wǎng)格單元[1,1]中，并從待測(cè)點(diǎn)1出發(fā)向鄰近的網(wǎng)格邊做垂線交于點(diǎn)1。連接點(diǎn)1與其左側(cè)的網(wǎng)格點(diǎn)(1,1)。最后，遍歷網(wǎng)格單元[1,1]中的所有邊，計(jì)數(shù)與線段11有交點(diǎn)的邊。同時(shí)依據(jù)網(wǎng)格邊1對(duì)應(yīng)的交點(diǎn)存儲(chǔ)數(shù)組，統(tǒng)計(jì)線段1(1,1)間的交點(diǎn)個(gè)數(shù)。將2條測(cè)試邊與多邊形邊相交點(diǎn)的個(gè)數(shù)相加，交點(diǎn)總個(gè)數(shù)為1。因此，待測(cè)點(diǎn)1與網(wǎng)格點(diǎn)(1,1)的位置屬性相反，位于多邊形外。

圖2 點(diǎn)包容性判定實(shí)例圖

在本文算法的判定計(jì)算中，最主要的工作是檢測(cè)測(cè)試邊的垂線是否與網(wǎng)格單元內(nèi)的邊相交。對(duì)此，可在該垂線向上與向下兩個(gè)方向的線段中，選取較短者進(jìn)行處理，以利于減少相交邊的計(jì)算。如圖3所示，對(duì)于垂線段1：1，考察其與一條多邊形邊的片段1：(設(shè)的坐標(biāo)為(1,1)，的坐標(biāo)為(2,2))的相交情況，可按下式進(jìn)行

當(dāng)進(jìn)一步處理上述結(jié)果時(shí)，根據(jù)邊片段1的方程計(jì)算垂線1與邊片段1交點(diǎn)的軸坐標(biāo)1；然后，與垂線段1的軸坐標(biāo)范圍(設(shè)1的軸坐標(biāo)范圍為(,))比較，判定垂線段1是否與邊片段1相交。具體比較方法如下

由此，對(duì)于不相交的邊，本文能夠基于簡(jiǎn)單的坐標(biāo)比較實(shí)現(xiàn)快速剔除；對(duì)于相交的邊，與傳統(tǒng)斜邊求交中需要4次叉積運(yùn)算和4次比較不同，本文方法只需1次乘法、1次加法和2次比較即可完成判定。

圖3 判斷垂線與多邊形邊是否相交實(shí)例圖

1.2 奇異情況的處理

本文方法的本質(zhì)是射線法的局部化實(shí)現(xiàn)，當(dāng)多邊形的邊或頂點(diǎn)位于射線上時(shí)(奇異情況)，將提高相交次數(shù)統(tǒng)計(jì)的復(fù)雜性。

奇異情況主要分為2大類：測(cè)試線與多邊形頂點(diǎn)相交的奇異點(diǎn)情況和測(cè)試線與多邊形的邊共線的奇異邊情況。經(jīng)分析，該奇異情況可分為以下4種情況處理，圖4和圖5分別展示了奇異點(diǎn)與奇異邊的4種奇異情況。

(1) 若多邊形頂點(diǎn)位于網(wǎng)格邊上(或與網(wǎng)格交點(diǎn)重合)且連接該頂點(diǎn)的2條邊位于該網(wǎng)格邊異側(cè)，如圖4A區(qū)和圖4C區(qū)，則該網(wǎng)格邊(如1)關(guān)于這個(gè)多邊形頂點(diǎn)的交點(diǎn)個(gè)數(shù)記為1；

(2) 若多邊形頂點(diǎn)位于網(wǎng)格邊上(或與網(wǎng)格頂點(diǎn)重合)且連接該頂點(diǎn)的2條邊位于網(wǎng)格邊的同側(cè)，如圖4B區(qū)和圖4D區(qū)，則交點(diǎn)個(gè)數(shù)記為2；

(3) 若多邊形的邊與網(wǎng)格邊重合且連接該邊的2條邊位于網(wǎng)格邊的異側(cè)，如圖5B區(qū)和圖5D區(qū)關(guān)于網(wǎng)格線1和3的情況，則交點(diǎn)個(gè)數(shù)記為1；

(4) 若多邊形的邊與網(wǎng)格邊重合且連接該邊的2條邊位于網(wǎng)格邊的同側(cè)，如圖5A區(qū)和圖5C區(qū)關(guān)于網(wǎng)格線0和2的情況，則交點(diǎn)個(gè)數(shù)記為2。

圖4 奇異點(diǎn)的相關(guān)情況

圖5 奇異邊的相關(guān)情況

在預(yù)處理過程中，只需對(duì)奇異點(diǎn)/邊進(jìn)行標(biāo)注即可。在判定計(jì)算中，測(cè)試線遇到奇異點(diǎn)/邊時(shí)，則沿著其方向繼續(xù)前行，直至遇到非奇異情況，然后進(jìn)行相關(guān)處理即可。文獻(xiàn)[16]將文獻(xiàn)[1]中的方法擴(kuò)展到三維空間中，并對(duì)奇異情況進(jìn)行了詳細(xì)的分析。一般情況下，在奇異邊繼續(xù)向前延伸中，最多延伸兩次即可得到非奇異情況。

1.2.1 預(yù)處理

預(yù)處理階段的基本操作就是統(tǒng)計(jì)2個(gè)網(wǎng)格點(diǎn)之間的交點(diǎn)個(gè)數(shù)，然后根據(jù)交點(diǎn)個(gè)數(shù)的奇偶性判定網(wǎng)格點(diǎn)的位置屬性。就奇異點(diǎn)而言，可以圖4中網(wǎng)格點(diǎn)(2,2)和(3,2)進(jìn)行分析，假設(shè)網(wǎng)格點(diǎn)(2,0)和(3,0)的位置屬性為多邊形外。在確定網(wǎng)格點(diǎn)(2,2)位置屬性時(shí)，首先需要向上搜索鄰近的網(wǎng)格點(diǎn)，由于網(wǎng)格點(diǎn)(2,1)為奇異點(diǎn)，因此向上搜索至網(wǎng)格點(diǎn)(2,0)。統(tǒng)計(jì)網(wǎng)格點(diǎn)(2,0)和(2,2)之間的交點(diǎn)個(gè)數(shù)，并依據(jù)上述的方法，連接頂點(diǎn)3的2條邊位于網(wǎng)格邊的異側(cè)，交點(diǎn)個(gè)數(shù)為1，因此網(wǎng)格點(diǎn)(2,2)和(2,0)的位置屬性相反，位于多邊形內(nèi)，結(jié)論正確。同理，確定網(wǎng)格點(diǎn)(3,2)的位置屬性，依據(jù)上述的方法，網(wǎng)格點(diǎn)(3,2)和(3,0)之間的交點(diǎn)個(gè)數(shù)為2個(gè)，因此網(wǎng)格點(diǎn)(3,2)與網(wǎng)格點(diǎn)(3,0)位置屬性相同，位于多邊形外，結(jié)論正確。就奇異邊而言，只需將奇異邊看作成一個(gè)奇異點(diǎn)，采用與奇異點(diǎn)相同的方法進(jìn)行計(jì)算。

在奇異情況的處理過程中，最主要的操作是判斷奇異點(diǎn)/邊兩端的邊是否處于奇異點(diǎn)/邊的同側(cè)或者異側(cè)。對(duì)于該問題，可通過比較2條邊的頂點(diǎn)坐標(biāo)解決。以圖5A區(qū)為例，該情況的奇異邊垂直軸，可設(shè)方程為，因此，通過對(duì)比奇異邊兩端邊的坐標(biāo)值就能夠判斷出相應(yīng)邊的分布情況。若1邊2個(gè)端點(diǎn)坐標(biāo)的值均不小于(或均不大于)值且1邊兩個(gè)端點(diǎn)坐標(biāo)的值均不小于(或均不大于)值，則邊1和1處于奇異邊1的同側(cè)；反之，邊1和1處于奇異邊1的異側(cè)。同理，對(duì)于平行軸的奇異邊，只需通過對(duì)應(yīng)的軸坐標(biāo)值的比較即可得出結(jié)果。

1.2.2 判定計(jì)算

判定階段的奇異情況主要包括：測(cè)試邊與網(wǎng)格邊重合、測(cè)試邊與多邊形的邊重合和測(cè)試邊經(jīng)過多邊形的頂點(diǎn)。對(duì)于該類奇異情況，可以采用類似奇異邊的方式進(jìn)行計(jì)算。

(1) 對(duì)于測(cè)試邊與網(wǎng)格邊重合的奇異情況。其處理方法為：直接根據(jù)待測(cè)點(diǎn)與鄰近網(wǎng)格點(diǎn)間的交點(diǎn)個(gè)數(shù)的奇偶性確定待測(cè)點(diǎn)的位置屬性。如圖2中的待測(cè)點(diǎn)4，其測(cè)試邊與網(wǎng)格線重合。因此可以通過連接待測(cè)點(diǎn)4與網(wǎng)格點(diǎn)(5,3)，然后根據(jù)該線段之間的交點(diǎn)個(gè)數(shù)確定待測(cè)點(diǎn)4的位置屬性。由于該測(cè)試邊通過多邊形的頂點(diǎn)6，且與該頂點(diǎn)相連的兩條邊位于測(cè)試邊的異側(cè)，交點(diǎn)個(gè)數(shù)為1。因此待測(cè)點(diǎn)4的位置屬性與網(wǎng)格點(diǎn)(5,3)位置屬性相反，位于多邊形外。

(2) 對(duì)于測(cè)試邊與多邊形的邊重合的奇異情況。其處理方法為：延伸測(cè)試邊，直至穿出多邊形的邊，并交于鄰近的網(wǎng)格邊，然后連接到與其交點(diǎn)最近的網(wǎng)格點(diǎn)，最后統(tǒng)計(jì)測(cè)試邊與多邊形的交點(diǎn)個(gè)數(shù)，以此確定待測(cè)點(diǎn)的位置屬性。如圖2中的待測(cè)點(diǎn)2，其測(cè)試邊與多邊形邊1211重合。依據(jù)上述規(guī)定，延長(zhǎng)測(cè)試邊使其與網(wǎng)格線0交于點(diǎn)2，同時(shí)連接點(diǎn)2與網(wǎng)格點(diǎn)(0,0)。統(tǒng)計(jì)測(cè)試邊與多邊形邊的交點(diǎn)個(gè)數(shù)，由于邊1211兩端連接的邊處于測(cè)試邊的同側(cè)，其交點(diǎn)個(gè)數(shù)記為2。另外，測(cè)試邊與多邊形邊10相交，交點(diǎn)總數(shù)為3，因此，待測(cè)點(diǎn)2的位置屬性與網(wǎng)格點(diǎn)(0,0)位置屬性相反，位于多邊形內(nèi)。

(3) 對(duì)于測(cè)試邊經(jīng)過多邊形的頂點(diǎn)的奇異情況。其處理方法與預(yù)處理階段的奇異點(diǎn)情況相似，可利用相同的處理方法進(jìn)行計(jì)算。如圖2中的待測(cè)點(diǎn)3和5，其測(cè)試邊分別經(jīng)過頂點(diǎn)8和10。由于連接頂點(diǎn)8的兩條邊處于3測(cè)試邊的兩側(cè)，且連接頂點(diǎn)10的兩條邊處于5測(cè)試邊的同側(cè)，測(cè)試邊33，55與多邊形的交點(diǎn)個(gè)數(shù)分別為1和4。因此3的位置屬性與網(wǎng)格點(diǎn)(3,1)的位置屬性相反，位于多邊形外；5的位置屬性與網(wǎng)格點(diǎn)(1,2)的位置屬性相同，位于多邊形內(nèi)。

2 復(fù)雜度分析

根據(jù)文獻(xiàn)[1]對(duì)網(wǎng)格中心點(diǎn)算法的分析，網(wǎng)格單元數(shù)的復(fù)雜度為()，空間復(fù)雜度為()。由于本文方法采用與其相同的公式確定網(wǎng)格分辨率，而在預(yù)處理過程中僅為每個(gè)網(wǎng)格交點(diǎn)增加了一個(gè)bit位記錄其位置屬性，且增加了()個(gè)字節(jié)存儲(chǔ)多邊形邊與網(wǎng)格邊的交點(diǎn)，因此本文方法的空間復(fù)雜度仍為()。

本文方法的預(yù)處理過程如下：

(1) 創(chuàng)建均勻網(wǎng)格。本文方法與文獻(xiàn)[1]采用相同的公式確定網(wǎng)格分辨率，時(shí)間復(fù)雜度為()。

(2) 計(jì)算網(wǎng)格線與多邊形邊的交點(diǎn)坐標(biāo)，并將其存儲(chǔ)到相應(yīng)的數(shù)組中。由于一條邊一般只與數(shù)個(gè)網(wǎng)格單元相交，檢測(cè)條邊，其時(shí)間復(fù)雜度為()。

(3) 將所有的多邊形邊片段加入到對(duì)應(yīng)的網(wǎng)格單元中，類似文獻(xiàn)[10]，時(shí)間復(fù)雜度為()。

(4) 確定網(wǎng)格交點(diǎn)的位置屬性。對(duì)于每個(gè)網(wǎng)格交點(diǎn)，只需檢測(cè)其臨近網(wǎng)格點(diǎn)的位置屬性和查詢其之間網(wǎng)格邊對(duì)應(yīng)的交點(diǎn)數(shù)目即可，時(shí)間復(fù)雜度為()。

本文方法的判定計(jì)算過程如下：

(1) 被測(cè)點(diǎn)位于無邊的網(wǎng)格內(nèi)。被測(cè)點(diǎn)與臨近網(wǎng)格頂點(diǎn)具有相同的屬性，時(shí)間復(fù)雜度為(1)。

雖然本文方法與文獻(xiàn)[1]具有相同的時(shí)間復(fù)雜度，但本文方法通過形成平行坐標(biāo)軸的測(cè)試線、記錄多邊形位于各個(gè)網(wǎng)格單元中的邊片段，由此可基于一些簡(jiǎn)單計(jì)算，大幅提高測(cè)試線與多邊形的邊的求交計(jì)算效率。

3 實(shí)驗(yàn)與討論

本文在一臺(tái)微機(jī)上進(jìn)行了算法實(shí)現(xiàn)，該微機(jī)的硬件環(huán)境為Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz，16 GB ARM，軟件開發(fā)環(huán)境為MS Windows 10操作系統(tǒng)，visual studio 2017。近年來，點(diǎn)在多邊形內(nèi)判定算法的研究不多且進(jìn)展緩慢，其中較好的算法有凸剖分法[8]、CBCA[10]和QCPM[11]等，這些方法在文獻(xiàn)[1]中均有對(duì)比分析。由于本文方法是在文獻(xiàn)[1]的基礎(chǔ)上進(jìn)行改進(jìn)，且上述方法在性能方面均次于文獻(xiàn)[1]方法，因此，本文方法僅與文獻(xiàn)[1]方法進(jìn)行對(duì)比實(shí)驗(yàn)。測(cè)試用例來自文獻(xiàn)[10]，如圖6所示。測(cè)試用點(diǎn)1000×1000個(gè)，其均勻分布在比多邊形包圍盒稍大的范圍內(nèi)。

Pol10Pol100 Pol1249Pol28000

實(shí)驗(yàn)統(tǒng)計(jì)數(shù)據(jù)見表1，其中，判定時(shí)間為檢測(cè)所有測(cè)試點(diǎn)的總時(shí)間。由表1可知，由于本文方法需要計(jì)算多邊形邊與網(wǎng)格邊的交點(diǎn)，并對(duì)這些交點(diǎn)進(jìn)行排序和存儲(chǔ)，因此在預(yù)處理階段本文方法耗費(fèi)了更多時(shí)間。但在判定計(jì)算過程中，相較于網(wǎng)格中心點(diǎn)算法[1]，本文方法的效率提升了2倍多，且隨著多邊形的邊數(shù)增多、復(fù)雜性的增大，本文方法的加速更多。

表1 新算法與網(wǎng)格中心點(diǎn)算法的對(duì)比實(shí)驗(yàn)數(shù)據(jù)

多邊形邊數(shù)網(wǎng)格分辨率算法預(yù)處理時(shí)間(加速率rp)# (ms)判定時(shí)間(加速率rd)^ (ms) Pol10108×6網(wǎng)格中心點(diǎn)算法0.33331.965 本文新算法0.339 (–0.017 70)15.199 (1.103 10) Pol10010038×18網(wǎng)格中心點(diǎn)算法0.40929.036 本文新算法1.422 (–0.712 38)12.747 (1.277 87) Pol12491 249100×46網(wǎng)格中心點(diǎn)算法0.90026.064 本文新算法9.889 (–0.908 99)12.918 (1.017 65) Pol2800028 000100×100網(wǎng)格中心點(diǎn)算法4.73484.590 本文新算法195.272 (–0.975 76)24.913 (2.395 42)

(注：# r=(T–T)/T，T為網(wǎng)格中心點(diǎn)算法的預(yù)處理時(shí)間；T為新算法的預(yù)處理時(shí)間；^ r=(T?T)/T，T為網(wǎng)格中心點(diǎn)算法的判定計(jì)算時(shí)間；T為新算法的判定計(jì)算時(shí)間)

表2 新算法與網(wǎng)格中心點(diǎn)算法的數(shù)值計(jì)算次數(shù)的對(duì)比實(shí)驗(yàn)數(shù)據(jù)

多邊形邊數(shù)網(wǎng)格分辨率網(wǎng)格中心點(diǎn)算法本文新算法 乘法次數(shù)加法次數(shù)比較次數(shù)乘法次數(shù)加法次數(shù)比較次數(shù) Pol10108×67 296 05614 592 1123 648 028164 778164 778329 556 Pol10010038×185 309 34410 618 6882 654 672968 8496 884193 768 Pol12491 249100×465 251 41610 502 8322 625 70888 93788 937177 874 Pol2800028 000100×10027 896 33655 792 67213 948 16897 41397 413194 826

為了進(jìn)一步分析本文方法加速的原因，本文針對(duì)網(wǎng)格中心點(diǎn)算法和本文方法的判定計(jì)算過程的數(shù)值計(jì)算次數(shù)進(jìn)行了統(tǒng)計(jì)分析，即測(cè)試邊與多邊形邊的求交過程的計(jì)算量，實(shí)驗(yàn)結(jié)果見表2，其中，乘法次數(shù)和加法次數(shù)分別代表測(cè)試邊與多邊形邊在求交過程中需要進(jìn)行乘法運(yùn)算和加法運(yùn)算的次數(shù)。對(duì)于比較次數(shù)，在網(wǎng)格中心點(diǎn)算法中，主要是比較叉積值與0值的次數(shù)，而在本文算法中，主要是比較測(cè)試邊和多邊形邊交點(diǎn)坐標(biāo)值與測(cè)試邊坐標(biāo)值的次數(shù)。如第1.1.2節(jié)中所述，網(wǎng)格中心點(diǎn)算法中計(jì)算兩條斜邊是否相交需要4次叉積運(yùn)算和4次比較運(yùn)算，即需要進(jìn)行16次加法和8次乘法，而本文方法在一次求交過程中只需要1次乘法、1次加法和2次比較。從表2可看出，在確定網(wǎng)格分辨率和測(cè)試點(diǎn)的情況下，本文方法所需的乘法計(jì)算和加法計(jì)算次數(shù)明顯低于網(wǎng)格中心點(diǎn)算法所需的計(jì)算次數(shù)，同時(shí)，本文方法所需的比較次數(shù)也明顯低于網(wǎng)格中心點(diǎn)算法所需的比較次數(shù)。

4 結(jié)束語

本文提出一種新的基于均勻網(wǎng)格的點(diǎn)在多邊形內(nèi)的判定算法。通過加強(qiáng)簡(jiǎn)便計(jì)算的處理，很好地減少測(cè)試線與多邊形邊的求交計(jì)算開銷，提高了射線法局部化實(shí)現(xiàn)的效率。實(shí)驗(yàn)表明，相比目前最快的類似算法，可將測(cè)試計(jì)算的效率提高2倍多，且多邊形的邊越多越復(fù)雜，加速性能越高。

[1] 李靜, 王文成. 基于網(wǎng)格中心點(diǎn)的點(diǎn)在多邊形內(nèi)的高效判定[J]. 軟件學(xué)報(bào), 2012, 23(9): 2481-2488.

[2] HUGHES J F, VAN DAM A, FOLEY J D, et al. Computer graphics: Principles and practice [M]. New Jersey: Pearson Education, 2014: 81-98.

[3] FEITO F, TORRES J C, URE?A A. Orientation, simplicity, and inclusion test for planar polygons [J]. Mathematical Gazette, 1995, 19(4): 595-600.

[4] FEITO F R, TORRES J C. Inclusion test for general polyhedral [J]. Computers and Graphics, 1997, 21(1): 23-30.

[5] 張宏, 溫永寧, 劉愛利. 地理信息系統(tǒng)算法基礎(chǔ)[M]. 北京: 科學(xué)出版社, 2006: 25-28.

[6] BERG M, CHEONG O, KREVELD M, et al. Computational geometry: Algorithms and applications [M]. Berlin: Springer-Verlag, 2008: 121-144.

[7] ZALIK B, CLAPWORTHY G J. A universal trapezoidation algorithm for planar polygons [J]. Computers and Graphics, 1999, 23(3): 353-363.

[8] LI J, WANG W C, WU E H. Point-in-polygon tests by convex decomposition [J]. Computers and Graphics, 2007, 31(4): 636-648.

[9] JIMéNEZ J J, FEITO F R, SEGURA R J. A new hierarchical triangle-based point-in-polygon data structure [J]. Computers and Geoscienes, 2009, 35(9): 1843-1853.

[10] ZALIK B, KOLINGEROVA I. A cell-based point-in-polygon algorithm suitable for large sets of points [J]. Computers and Geosciences, 2001, 27(10): 1135-1145.

[11] YANG S, YONG J H, SUN J, et al. A point-in-polygon method based on a quasi-closest point [J]. Computers and Geosciences, 2010, 36(2): 205-213.

[12] WANG W C, LI J, WU E H. 2D point-in-polygon test by classifying edges into layers [J]. Computers and Graphics, 2005, 29(3): 427-439.

[13] 李楠, 肖克炎. 一種改進(jìn)的點(diǎn)在多邊形內(nèi)外判斷算法[J]. 計(jì)算機(jī)工程, 2012, 38(5): 30-34.

[14] 孫愛玲, 趙光華, 趙敏華, 等. 基于sign(x)函數(shù)的點(diǎn)在多邊形內(nèi)外判別算法及應(yīng)用[J]. 計(jì)算機(jī)工程與科學(xué), 2017, 39(4): 785-790.

[15] CLEARY J G, GEOFF W. Analysis of an algorithm for fast ray tracing using uniform space subdivision [J]. Visual Computer, 1988, 4(2): 65-83.

[16] LI J, WANG W C. Fast and robust GPU-based point-in-polyhedron determination [J]. Computer-Aided Design, 2017, 87: 20-28.

Efficient Point-in-Polygon Tests with Local and Simple Computation

WANG Sheng-chun1,2, WANG Wen-cheng1,2, TAN Xue-han1,2, LI Jing3

(1. State Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China; 2. School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100190, China; 3. Key Laboratory of Zoological Systematics and Evolution, Institute of Zoology, Chinese Academy of Sciences, Beijing 100101, China)

polygon; grid; simple computation; point-in-polygon tests

TP 391

10.11996/JG.j.2095-302X.2019020267

A

2095-302X(2019)02-0267-07

2018-09-01；

2018-09-18

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2017YFB1002700)；國(guó)家自然科學(xué)基金項(xiàng)目(61661146002，61872348)

王盛春(1991-)，男，陜西延安人，博士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、紋理分析等。E-mail：wangsc@ios.ac.cn

王文成(1967-)，男，湖南雙峰人，研究員，博士，博士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)及可視分析等。 E-mail：whn@ios.ac.cn