謝少菲，高鐵軍，魏戀歡

(東北大學 資源與土木工程學院，遼寧 沈陽 110819)

0 引 言

點在多邊形內外判定是計算機圖形學中重要的基礎算法，在計算機圖形處理、地理信息系統(tǒng)(GIS)、CAD/CAM、模式識別、醫(yī)學圖像處理等領域都有著大量的應用。平面點在多邊形內外的判斷已經有大量的經典算法，但區(qū)域內大量目標實時越界監(jiān)控、海量激光點云數(shù)據(jù)分割與分析仍需尋找更加高效的多點在多邊形內判定算法。

點在多邊形的內外檢測方法主要分為兩大類。

(1)無需預處理數(shù)據(jù)，根據(jù)幾何特性直接判定待定點內外位置屬性，如：射線法[1-4]、凸多邊形分割[5]、sign(x)函數(shù)[6-8]方法和纏繞數(shù)[9]方法。射線法的原理是通過待定點發(fā)出的射線與多邊形交點數(shù)的奇偶性來判斷點與多邊形位置關系；基于凸多邊形分割的方法通過不斷分割多邊形來確定點位置，但只能處理凸多邊形；基于sign(x)函數(shù)的方法利用三維空間，借用符號函數(shù)判斷待定點與多邊形的位置關系，相較射線法更準更快；纏繞數(shù)的方法顧名思義就是通過多邊形纏繞待定點的圈數(shù)判定點的位置，圈數(shù)不為零則點在內部。該類算法不需預處理操作，在少量點判定時優(yōu)勢明顯，但當待定點數(shù)量較大時效率不足。

(2)需要預處理多邊形數(shù)據(jù)，然后再判定點的位置屬性，該類方法適用于待定點數(shù)量較大時的高效判定，如BSP樹法[10]、自適應網格法[11，12]和均勻網格法[13-15]等。BSP[10]樹法是將多邊形進行凸剖分后進行二叉樹管理，利用二叉樹快速確定待定點所在凸多邊形后再判斷，該方法不能處理自相交多邊形；自適應網格法[11，12]使用不同大小的網格對多邊形進行填充，實現(xiàn)大量點的高效判定，但不能處理自相交多邊形，判定精度受網格尺寸限制。均勻網格法[13-15]是將多邊形放入均勻網格中，通過預處理得到每個網格與多邊形的內外位置關系，再根據(jù)待定點所在網格的內外屬性判定其位置屬性，它能夠處理任意形狀的多邊形。Zalik等[13]提出的CBCA方法，利用Flood-fill算法進行預處理，由于涉及到大量單元格的重復訪問，預處理耗時長。李靜等[14]提出了效率更高的基于網格中心點的判定方法，預處理階段使用數(shù)值微分法(DDA)確定多邊形邊穿過的網格單元，以傳遞的方式確定所有網格中心點在多邊形的內外屬性。點判定時，采用局部射線法，根據(jù)待定點與所在格中心點連線與多邊形的交點數(shù)判定內外。王盛春等[15]在文獻[14]的基礎上，預處理額外分割出網格包含的多邊形邊的片段，判定時根據(jù)邊片段兩端點的坐標比較，來減少求交判定次數(shù)，點判定階段效率提高明顯，但預處理計算復雜耗時。

本文在文獻[14，15]的啟發(fā)下提出了更高效的基于網格的判定算法。在預處理階段將DDA算法與邊界代數(shù)法相結合，在分割多邊形邊的同時確定所有網格的左下角點位置屬性。在判定階段通過對邊界網格分塊實現(xiàn)待定點位置屬性快速判定，對比實驗驗證本文方法計算效率最高。

1 基于網格的判定算法

本算法分為預處理與點位置判定兩個階段(圖1)。

圖1 算法流程

(1)預處理階段包含創(chuàng)建網格、DDA算法確定邊界網格并分割多邊形邊片段和邊界代數(shù)法確定網格角點位置屬性。本文網格分辨率計算采用文獻[13-15]的經驗公式。在X和Y方向上的單元數(shù)Mx、My分別為

Mx=2[λn1/2]，My=2[(1/λ)n1/2]

(1)

其中，n為多邊形邊數(shù)，λ為網格單元的寬長比。

(2)點位置判定階段，若待定點位于非邊界網格內，根據(jù)網格單元位置屬性直接判定點位置屬性；若點位于邊界網格內，通過叉乘計算確定點在多邊形邊上、頂點上、內、外。

1.1 預處理

確定分辨率(式(1))后創(chuàng)建網格，然后計算邊界網格以及其所包含的邊片段并確定每個網格單元的左下角點內外位置屬性。使用DDA算法計算多邊形邊穿越的網格單元，定義此類網格單元為邊界網格。DDA算法如圖2所示，線段AB代表多邊形某一邊，x、y代表該線段由A至B方向上與不同格網列、行相交后的交點至起點A的距離，dx、dy代表相鄰兩條格網列線、格網行線所截取的線段長度。通過比較x和y的大小，來確定線段穿過了哪些網格。與此同時將線段與網格線的交點以及自身端點的坐標記錄在對應網格中，即網格所包含的邊片段。

圖2 DDA算法示意

同時，應用邊界代數(shù)法確定各單元格左下角點內外位置屬性。當多邊形邊穿過網格水平線時，該水平線與多邊形邊交點左側同行的所有網格角點的位置屬性值進行代數(shù)加減，如：網格角點位置屬性初始值定義為0，計算邊上行時其左側所有網格角點屬性值加1，下行時其右側網格角點屬性值減1(圖3(a))。遍歷所有多邊形邊后，即得到所有網格的左下角點相對與多邊形的內外位置屬性值，值為0說明該網格單元位于多邊形外部，非0位于多邊形內部(圖3(b))。邊界代數(shù)法適用于自相交、環(huán)狀等復雜多邊形。

圖3 邊界代數(shù)法示意

當出現(xiàn)多邊形的邊經過網格角點或與網格線重合特例情況時(圖4)，為保證網格角點位置屬性的唯一性，強制規(guī)定網格角點位于穿過該點的多邊形邊左側。如圖4中a、b、c、d這4個網格角點，點a、點b兩點均被邊P2P3穿過，強制認為兩點位于邊P2P3左側，邊界代數(shù)法運算后，點a位于多邊形外，點b位于多邊形內。同理，點c位于邊P1P2左側，邊界代數(shù)運算判定為多邊形外部；點d位于邊P3P4左側，邊界代數(shù)運算后判定為多邊形內部。

圖4 預處理階段奇異情況處理

多邊形預處理后確定了多邊形邊(圖5)穿過的邊界網格(灰色)、邊界網格中所包含的多邊形邊的片段、網格左下角點相對于多邊形的內外位置屬性(實心點為內部點，空心點為外部點)。圖5中含自相交多邊形和環(huán)狀多邊形，邊界代數(shù)法均能正確計算網格左下角點位置屬性。如r3行的角點a位于邊P0P1、邊P2P3右側，邊P1P2左側，位置屬性值計算結果為-1不等于0，判定角點a位于多邊形內部；角點b與角點a之間有邊P8P9穿過，點b位于邊P8P9左側，位置屬性值計算結果為0，判定角點b位于多邊形外部，其余角點位置屬性計算同理。

圖5 預處理結果

1.2 點的位置判定

待定點坐標轉換為網格坐標后位于非邊界網格，則可直接根據(jù)單元格左下角點位置屬性判定待定點位置屬性；若位于邊界網格，首先坐標比較判斷待定點是否位于邊片段集合矩形范圍內，不位于則直接根據(jù)最近網格角點位置屬性確定待定點位置，位于則使用文獻[14]的局部射線法進行判定。局部射線法是將待定點與其所在單元格左下角點連線，計算該線段與多邊形邊的交點數(shù)的奇偶性，奇數(shù)則待定點與單元格左下角位置屬性相反，偶數(shù)則相同。圖6(a)～圖6(e)例舉了邊界網格中的幾種可能出現(xiàn)的情況，當待定點位于陰影區(qū)域(邊片段集合矩形范圍之外的區(qū)域)則可直接確定其內外屬性，待定點位置屬性等同于陰影區(qū)域所包含的任意的單元格角點內外屬性；位于邊片段集合矩形范圍的點則需通過叉乘計算交點數(shù)量來判定。以圖6(c)為例，P1點橫坐標小于單元格中所有邊片段端點的橫坐標最小值，則說明P1點與C點之間不存在任何邊片段，確定待定點P1與點C位置屬性相同。P2點位于邊片段集合矩形范圍內，做P2點與C點連線，叉乘判斷線段P2C與所有邊片段有一個交點，奇數(shù)則P2位置屬性與點C相反。若邊界網格的四邊均有多邊形邊穿過，如圖6(e)所示，邊片段集合矩形范圍與該單元格區(qū)域相同，其中的待定點只能通過局部射線法進行判定。在判定相交的計算過程中，先通過坐標比較排除部分不相關邊，減少叉乘計算量。仍以圖6(e)的情況為例，過邊E1E2的兩端點分別做水平和垂直直線(圖中虛線)，將單元格劃分成4個區(qū)域，其中待定點P1、P2和P3所在矩形區(qū)域中的點與點C連線后均不可能與邊E1E2有交點，故當待定點不在E1E2矩形區(qū)域時，邊E1E2不參與叉乘求交計算。

圖6 邊界網格分塊典型示例

根據(jù)上述判定方法，大部分待定點可以快速判定其位置屬性，無需叉乘計算求交點數(shù)量。如圖7所示，黑色與灰色區(qū)域中的待定點均不用進行叉乘運算，黑色區(qū)域為內部，灰色區(qū)域為外部，兩區(qū)域面積和相對整個矩形面積占比越高，越有利于提高判定效率。

圖7 邊界網格分塊整體結果

判斷兩個線段是否有交點需要4次叉乘運算，兩線段相互跨立則存在交點。若某一線段A的兩個端點分別在另一條線段B的左側和右側(兩端點叉乘結果異號)則A跨立B，同理計算B是否跨立A，若線段A和線段B相互跨立則有交點，否則沒有交點。若作為連線端點的待定點與一條邊片段的叉乘計算結果為0且待定點位于該邊片段矩形范圍內，則待定點位于多邊形邊上。若一待定點判定為在兩條不同多邊形邊上，則判定其在多邊形頂點上。

判定過程用到了局部射線法，使用叉乘計算點在線的左右來判斷是否存在交點，存在待定點與參考點連線經過多邊形頂點或與多邊形邊重合的特例情況，如圖8所示，采用與預處理奇異情況相同的規(guī)則，通過強制規(guī)定在線上的點位于線的左側規(guī)則來處理。圖8[14](a)中O為已知位置的參考點，連線OQ1經過多邊形頂點P1，強制認為點P1在OQ1左側，因此連線OQ1與a1、b1無交點；圖8(b)中，設定P2位于OQ2左側，則連線OQ2與a2相交，與b2不相交，結論正確；圖8(c)中，連線OQ3經過多邊形邊b3，先判定待定點Q3是否在邊b3上，若在則直接判定待定點位于多邊形邊上，否則設定b3兩端點均在OQ3左側，則連線OQ3與a3、c3均相交，有兩個交點，結論正確；圖8(d)同理。

圖8 奇異情況

2 復雜度分析

2.1 空間復雜度分析

文獻[14，15]的網格單元數(shù)的復雜度和空間復雜度均為O(N)。由于分辨率的選取方式相同，且只為每個網格添加了分塊所用坐標，故空間復雜度與兩文一致為O(N)。

2.2 時間復雜度分析

本文預處理過程：①創(chuàng)建網格。采用與文獻[14，15]相同分辨率公式，時間復雜度為O(N)。②DDA算法計算邊界網格及其邊片段，需要遍歷N條邊，時間復雜度為O(N)。③邊界代數(shù)法與DDA算法同時進行，且也只與多邊形邊數(shù)相關，時間復雜度為O(N)。

3 實驗與討論

選用與文獻[13-15]相同的多邊形樣例進行驗證，預處理后如圖9所示，黑色是邊界網格，白色是外部網格，灰色是內部網格。測試用點為1 000 000個隨機點，均勻分布在包含多邊形的矩形范圍內。

圖9 實驗所用多邊形

在AMD 2.38 GHz，16 G RAM的電腦上，VS2019 C++編程對文獻[14，15]和本文方法進行了對比實驗(表1)。受益于DDA結合邊界代數(shù)法以及邊界網格分塊法，本文方法計算效率提高明顯。使用DDA算法結合邊界代數(shù)法進行數(shù)據(jù)預處理，在DDA的過程中識別邊界網格、分割并記錄邊片段，同時應用邊界代數(shù)法確定網格角點的多邊形內外位置屬性。由于邊界代數(shù)法是代數(shù)加減運算，計算速度快，但隨著網格分辨率的提高，代數(shù)運算次數(shù)會增加，預處理耗時會增加并達到與文獻[14]相當?shù)乃健Ｔ邳c判斷過程中，本文方法對邊界網格分塊，通過坐標比較與局部射線法確定待定點位置屬性，交點計算叉乘次數(shù)大幅度減少，判定效率較文獻[14]提高了兩倍。文獻[15]預處理階段計算多邊形與網格線交點并排序，預處理復雜、耗時多，但在判定時將交點數(shù)量計算轉化為統(tǒng)計連線線段水平分量的交點數(shù)量和計算線段垂直分量的實際交點，預處理時間雖然較長但判定時間得以改善。在垂直分量交點數(shù)量計算過程中通過坐標比較排除了不相關邊，但邊界網格中的所有待定點都需要與所在網格的所有邊片段進行比較，本文通過邊界網格分塊減少了此過程。表1說明本文方法在復雜多邊形的處理中預處理優(yōu)于文獻[15]，判斷過程優(yōu)于文獻[14]，總時間優(yōu)于兩者。

表1 算法用時比較

表2統(tǒng)計了3種方法在判定過程中需要進行求交判定的點數(shù)，以及實際求交判定的次數(shù)。結果可以看出文獻[15]相較文獻[14]有效減少求交次數(shù)，而本文則是通過直接減少求交計算點數(shù)量實現(xiàn)判定加速。下述算法1[14]與算法2[15]的對比可以看出文獻[15]通過條件比較剔除部分邊片段減少了求交次數(shù)以實現(xiàn)判定加速，但是需要求交判定的待定點數(shù)量相比文獻[14]沒有變化，需要遍歷每個待定點所在網格的所有邊片段；本文提出的算法3通過邊界網格分塊減少需要求交計算待定點的數(shù)量，從而有效降低了對網格中邊片段的遍歷次數(shù)，進而實現(xiàn)了判定加速。

表2 判定次數(shù)對比

算法1：文獻[14]判定算法

在二十世紀中葉以前，我國主要以俄國的視唱體系進行教學。它包含了二十世紀以前西方音樂中各個歷史發(fā)展過程中產生的音樂作品。并且形成了以自然大小調和聲基礎為主的完整的視唱練耳體系。之后，在經過我國視唱練耳專業(yè)學者多年來的反復斟酌與不懈的努力，并吸取了各國視唱教學體系中的優(yōu)點，逐漸形成了具有中國特色而又融匯了各國視唱教學的視唱練耳教學體系，為我國的基礎音樂教育在培養(yǎng)人才等各方面做出了巨大貢獻。

(1) for in 待定點集

(2) if 點在邊界網格

(3) for in 穿過網格的邊集

(4) 叉乘求交判定

(5) else

(6) 直接確定位置

算法2：文獻[15]判定算法

(1) for in 待定點集

(3) for in 網格包含邊片段集

(4) if 點在邊片段坐標范圍內

(5) 求交點判定

(6) else

(7) 剔除該邊片段

(8) else

(9) 直接確定位置

算法3：本文判定算法

(1) for in 待定點集

(2) if 點在邊界網格

(3) if 點在邊片段矩形區(qū)域

(4) for in 網格包含邊片段集

(5) 叉乘求交判定

(6) else

(7) 直接確定位置

(8) else

(9) 直接確定位置

4 結束語

本文提出了一種基于網格的多點在多邊形內高效判定方法，包含預處理和點判定兩個階段。預處理階段應用DDA算法結合邊界代數(shù)法快速確定邊界網格、分割邊片段以及確定網格左下角點內外位置屬性。點判定階段參照網格角點位置屬性直接判定非邊界網格點內外位置屬性；使用邊界網格分塊法直接判定邊界網格內位于邊片段區(qū)域外點的位置屬性，對于位于邊片段區(qū)域內的點通過叉乘計算識別點在多邊形內、外、頂點或邊上。邊界網格分塊可以有效減少需要求交計算的點數(shù)量，進而有效縮減點判定時間。本文方法適用于凹凸多邊形、自相交多邊形以及環(huán)狀多邊形，特別是多邊形邊和待定點的數(shù)量較大時更有優(yōu)勢。