基于二分法的凸多邊形內(nèi)外點判別算法

于凱，俞孟蕻

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003）

基于二分法的凸多邊形內(nèi)外點判別算法

于凱，俞孟蕻

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003）

多邊形內(nèi)外點判定算法是圖形學的基礎(chǔ)型算法，目的是判定待測點是否在指定的多邊形之內(nèi)。由于傳統(tǒng)的射線法與角度和法效率偏低，平均時間復(fù)雜度為O（n），當多邊形邊數(shù)或者待測點個數(shù)較多時，算法耗時較高。因此本文分析了傳統(tǒng)的射線法與角度和法的缺點；提出了基于二分法的凸多邊形內(nèi)外點判別算法；最后進行實驗仿真，證明該算法的平均時間復(fù)雜度為O（n/2）。該算法通過遞歸的分割凸多邊形，判斷待測點與分割線的相對位置，最終轉(zhuǎn)化為三角形內(nèi)外點的判別，具有快速、穩(wěn)定、準確的優(yōu)勢。

凸多邊形；二分法；包含測試；遞歸分割

多邊形內(nèi)外點判別算法也叫做點的包含測試（point-inpolygon test），目的是測試一個點是否在多邊形內(nèi)［1］。該算法在計算機圖形學、模式識別、地理信息系統(tǒng)等眾多領(lǐng)域中有著廣泛的應(yīng)用。例如，當工業(yè)上需要判斷礦井是否在指定的區(qū)域內(nèi)，或者游戲中需要判斷點擊的位置是否在指定的區(qū)域內(nèi)。解決此類問題首先通過仿真，將指定區(qū)域建模成多邊形，而礦井或者點擊的位置就是待測點，通過多邊形內(nèi)外點判別算法判定此待測點是否在該多邊形內(nèi)，從而確定礦井或者點擊位置是否在指定區(qū)域內(nèi)。算法的平均時間復(fù)雜度也就是判定待測點是否在多邊形內(nèi)的平均耗時，耗時減少，會使得游戲的體驗更好，工業(yè)上工程的進度更快。因此怎樣節(jié)省算法的耗時時本文研究的主要問題。邊形交點的個數(shù)來判斷被測點是否在多邊形內(nèi)，若交點個數(shù)為偶數(shù)，則待測點不在多邊形之內(nèi)，若交點個數(shù)為奇數(shù)，則待測點在多邊形內(nèi)部。角度和法，通過計算被測點與個頂點連線所形成的角度之和來判斷被測點是否在多邊形內(nèi)，若夾角之和為360度，則待測點位于多邊形內(nèi)部，否則待測點不在多邊形內(nèi)部［6］。此類方法雖然易于實現(xiàn)，但是有如下缺點：對于每一個待測點，均需要進行n次判定（n為多邊形邊數(shù)）才能確定待測點的位置，即最優(yōu)、最差、平均時間復(fù)雜度均為O（n）；只能判斷待測點是否在多邊形內(nèi)，而不能確定待測點的區(qū)域。

第二類算法是需要預(yù)處理的算法，如網(wǎng)格分割法、分層法等，文獻［2-9］采用了預(yù)處理的方法。網(wǎng)格分割法首先建立均勻網(wǎng)格，并從左至右依次計算每個網(wǎng)格單元中心點的位置屬性，確定待測點所在的網(wǎng)格，再根據(jù)點與網(wǎng)格中心點的關(guān)系判斷待測點的位置［3］。分層法是將多邊形的邊分層管理，通過判斷待測點與每一層的邊的關(guān)系來確定待測點的位置［5］。此類算法不僅可以判斷待測點是否在多邊形內(nèi)，還可以確定待測點的大致區(qū)域，此類算法缺點如下：預(yù)處理往往比較耗時，不同的預(yù)處理結(jié)果可能導(dǎo)致算法性能的大幅度波動。例如網(wǎng)格法中，網(wǎng)格的大小對于算法性能的影響很明顯，網(wǎng)格過大或者過小均會降低算法的效率；需要額外的存儲空間存儲預(yù)處理結(jié)果，在降低算法時間復(fù)雜度的同時卻增加了算法的空間復(fù)雜度。根據(jù)是否需要對多邊形進行預(yù)處理可以將多邊形內(nèi)外點判別算法分為兩類，一類是不需要進行預(yù)處理的算法，如射線法、角度和法，文獻［10］中對射線法進行了改進，算法平均時間復(fù)雜度為O（n）。

1　基本約定與算法思想

1.1算法原理與依據(jù)

本算法核心思想包括三部分，使用頂點向量組織管理多邊形的頂點、使用二分法遞歸的分割多邊形、判斷分割線與待測點的相對位置。

由于任意多邊形均可以看成是一組點集按照順時針或者逆時的順序連線，所形成的封閉圖形，因此本算法使用向量的管理多邊形的頂點集合，在本算法中稱之為頂點向量。每一個多邊形均對應(yīng)唯一一個頂點向量，每一個頂點向量也可以確定一個唯一的多邊形［11］。根據(jù)當前多邊形的頂點總數(shù)，使用二分法分割多邊形，實際上就是將當前的頂點向量分割成兩個新的頂點向量，因此對應(yīng)兩個新的多邊形。通過判斷待測點與分割線的相對位置，在兩個新的頂點向量中選擇一個，再次進行分割與判斷，如此遞歸循環(huán)，直到當前頂點向量中只有3個頂點為止，此時采用射線法可以輕松的判斷出待測點是否在多邊形內(nèi)，同時可以使用這3個頂點確定待測點所在的三角形區(qū)域。

1.2頂點向量

頂點向量是一個保存了當前多邊形頂點信息的向量。

為了方便管理多邊形的頂點，在構(gòu)造多邊形時，將頂點進行有序管理。首先選擇所有頂點中橫坐標最小的頂點（如果有多個，則選擇其中一個），將其作為頂點向量中的第一個頂點，編號為0。然后按照逆時針的順序?qū)⑵溆喔鱾€頂點依次加入頂點向量［12］，編號依次加1。頂點向量中的每個節(jié)點不僅保存了頂點的橫縱坐標，還記錄了頂點的編號。當多邊形進行變化時，頂點向量也隨之更新。

1.3凸多邊形的分割

定義1凸多邊形是指沒有任何一個內(nèi)角是優(yōu)角 （大于180度小于360度）的多邊形。

定理1連接凸多邊形任意兩頂點，一定將此凸多邊形分割為兩個凸多邊形。

證明：因為凸多邊形的任意兩個頂點的連線均在多邊形內(nèi)部，所以，連接任意兩個頂點后，會將原有的內(nèi)角分為兩個新的內(nèi)角。又因為凸多邊形的內(nèi)角全部為非優(yōu)角，因此產(chǎn)生的新角也一定為非優(yōu)角，所以分割后的兩個多邊形仍為凸多邊形。

定義2分割線是由左右端點組成的一條線段，其左側(cè)端點固定，為凸多邊形頂點向量中的第一個頂點，即橫坐標最小的頂點。右側(cè)端點根據(jù)當前凸多邊形的頂點總數(shù)求出。分割線方向朝向x軸正方向，將凸多邊形分割為兩個凸多邊形。

1）求取分割線

給定一個的凸多邊形M=V0V1…Vn-1，求取分割線的方法如下：

Step1.在當前凸多邊形對應(yīng)的頂點向量中，選取編號為0的頂點，作為分割線的左端點，記為P0；

Step2.計算當前凸多邊形定點個數(shù)，記為N。設(shè)分割線右側(cè)端點為當前凸多邊形頂點向量中的第i個頂點。則i=［N/2］向下取整，記為P1；

Step3.連接P0，P1即為分割線，求得分割線的方程f（x，y）=0。2）待測點與分割線的位置關(guān)系

由于分割線的方向固定，都是朝向x軸正方向。因此，將待測點帶入分割線方程，若f（x，y）＞0，則待測點在分割線上方；若f（x，y）＜0，則待測點在分割線下方；若f（x，y）=0，則在分割線所在直線上。

1.4遞歸分割

遞歸分割時，分割線左側(cè)端點不動，根據(jù)點與分割線的位置關(guān)系，將分割后的凸多邊形再次進行分割［13］。一個凸多邊形經(jīng)過分割后最終會形成若干個三角形。最終將點與凸多邊形的關(guān)系轉(zhuǎn)化為點與三角形的關(guān)系。

1.5待測點的區(qū)域判斷

每次分割會造成頂點向量的改變，但是并不改變頂點的相對順序。當遞歸分割完成時，頂點向量中只有3個頂點，第一個頂點是分割線的左端點，因此可以使用第二個頂點的編號作為三角形區(qū)域的編號。凸多邊形的區(qū)域劃分如圖1所示，待測點分布區(qū)域的仿真結(jié)果如圖2所示。

圖1　凸多邊形的區(qū)域劃分

圖2　待測點的分布區(qū)域

從圖2中可以看出，待測點被分成了3個區(qū)域，分別用三角形、圓圈和方框表示。

2　算法描述

算法主要步驟如下：

1）選擇橫坐標最大、橫坐標最小、縱坐標最大、縱坐標最小的4個頂點（若有多個，選擇一個），制作一個矩形包圍框。若待測點的橫坐標、縱坐標其中一個或者兩個均不在此包圍框范圍內(nèi)，則判斷待測點不在凸多邊形之內(nèi)，算法結(jié)束。否則執(zhí)行2）。

2）計算當前凸多邊形的頂點個數(shù)N，若N=3，則直接使用射線法進行三角形內(nèi)外點的判定，否則執(zhí)行3）。

3）按照1.4節(jié)求分割線的方法求出分割線，分割凸多邊形為兩個凸多邊形。判斷待測點與分割線的位置關(guān)系，即將待測點帶入直線方程計算結(jié)果記為R。如果R=0且待測點的橫坐標在分割線左右端點的橫坐標區(qū)間內(nèi)，則待測點在分割線上，也在凸多邊形之內(nèi)，算法結(jié)束。否則執(zhí)行4）。

4）若R＞0，則待測點在分割線的上方，刪除當前頂點向量中在分割線下方的頂點（不包括分割線的兩端點），形成新的凸多邊形與新的向量；若R＜0，則待測點在分割線的下方，刪除當前頂點向量中在分割線上方的頂點（不包括分割線的兩端點），形成新的凸多邊形與新的向量，執(zhí)行2）。

3　計算量分析

對于有n條邊的凸多邊形，本算法最多需要進行［（n-1）/2］次與分割線的比較和3次與凸多邊形邊的比較。當多邊形頂點個數(shù)為4時，本算法具有最差的時間復(fù)雜度O（n），當頂點個數(shù)增加時，算法性能將得到提升。對于某些點，本算法只需要3次計算就可以確定待測點的位置，因此本算法最優(yōu)時間復(fù)雜度為O（1）。因此，本算法平均時間復(fù)雜度為O（n/2）。

而使用射線法進行內(nèi)外點檢測時，必須將待測點與多邊形的每一條邊進行比較才能確定該點是否在多邊形內(nèi)，即射線法時間復(fù)雜度始終為O（n）。因此，對于指定的凸多邊形，待測點個數(shù)越多，本算法相對于射線法節(jié)省的時間也就越多。

4　實驗與分析

本文使用Visual Studio 2013對本算法以及射線法進行了比較。測試計算機配置Intel（R）Core（TM）i7-4870HQ的CPU、16GB內(nèi)存和Windows7 x64操作系統(tǒng)。

1）測試凸多邊形頂點個數(shù)與算法耗時的關(guān)系

實驗使用10 000個隨機待測點分別對頂點個數(shù)為10、20、30、40、50的凸多邊形進行了內(nèi)外點的測試，頂點個數(shù)與算法耗時關(guān)系見圖3。頂點個數(shù)與算法耗時比較表，見表1。

實驗證明，當凸多邊形具有相同頂點個數(shù)時，本算法性能明顯優(yōu)于射線法。當多邊形頂點個數(shù)較少時，算法優(yōu)勢不明顯。這是因為當多邊形頂點個數(shù)較少時，本算法不僅需要與分割線進行比較，還需要與三角形區(qū)域的三條邊進行比較［14］。例如，當凸多邊形只有4個頂點時，本算法性能達到最差，即需要進行1次與分割線的比較，和3次與邊的比較，與射線法一樣共需4次比較。因此，頂點個數(shù)越多，本算法性能越好。

2）測試待測點個數(shù)與算法耗時的關(guān)系

實驗分別使用10 000到60 000個隨機待測點對頂點個數(shù)為10的凸多邊形進行了內(nèi)外點的測試，待測點個數(shù)與算法耗時關(guān)系見圖4。待測點個數(shù)與算法耗時比較表，見表2。

圖3　頂點個數(shù)與算法耗時關(guān)系

表1　頂點個數(shù)與算法耗時比較

圖4　待測點個數(shù)與算法耗時關(guān)系

表2　待測點個數(shù)與算法耗時比較

實驗證明，待測點個數(shù)越多本算法性能越好，相對于射線法節(jié)省的時間也越多。由表2可以看出，當待測點個數(shù)線性增加時，本算法相對于射線法的耗時并不是線性減少，這是因為待測點的分布具有隨機性。

5　結(jié)　論

本文提供了一種簡單有效的凸多邊形內(nèi)外點判定算法，它不需要對凸多邊形進行預(yù)處理，節(jié)省了大量預(yù)處理的時間消耗。本算法使用頂點向量對凸多邊形的頂點進行管理，并使用二分法遞歸的分割凸多邊形，將待測點與凸多邊形的位置關(guān)系轉(zhuǎn)化為待測點與三角形的位置關(guān)系。由于使用了分割法，本算法不僅可以判定待測點是否在多邊形內(nèi)，還能給出待測點的三角形區(qū)域，并且頂點個數(shù)越多，劃分的區(qū)域就越精確。

本算法時間復(fù)雜度在O（1）到O（n）之間，而平均時間復(fù)雜度為O（n/2）。因此與射線法相比，本算法在大多數(shù)情況下均可以節(jié)約20％～50％的算法耗時，實驗結(jié)果表明，本算法易于實現(xiàn)，高效穩(wěn)定。

［1］周欣，張樹有，潘志庚.基于鏈碼和特征形的多邊形內(nèi)外點判斷算法 ［J］.計算機輔助設(shè)計與圖形學學報，2006，18 （9）:1317-1321.

［2］張寧寧，張樹有，譚建榮.映射相關(guān)邊概念的多邊形內(nèi)外點判別算法 ［J］.計算機輔助設(shè)計與圖形學學報，2004，16 （7）:935-938.

［3］李靜，王文成.基于網(wǎng)格中心點的點在多邊形內(nèi)的高效判定［J］.軟件學報，2012，23（9）:2481-2488.

［4］肖飛.基于點序的多邊形分割方法探討［J］.信息技術(shù)與信息化，2012（5）:100-102，105.

［5］趙海森，楊承磊，呂琳.多邊形中的點可見性快速算法［J］.計算機輔助設(shè)計與圖形學學報，2013，25（3）:331-340.

［6］楊玉婷，康厚良.2D圖形引擎中的平面多邊形內(nèi)外點判別［J］.圖學學報，2013，34（3）:100-105.

［7］高天豪，王文成，朱濱海.基于凸片段分解和格網(wǎng)的點在多邊形中的可見邊檢測 ［J］.計算機輔助設(shè)計與圖形學學報，2013，25（8）:1114-1120.

［8］向俊，王靜，夏幼明.判斷點與多邊形拓撲關(guān)系的改進算法［J］.計算機工程與設(shè)計，2014，35（5）:1732-1737.

［9］楊雅軍，段明義.判斷點與指定多邊形區(qū)域的關(guān)系的改進算法［J］.電腦知識與技術(shù)，2014，10（22）:5362-5364.

［10］翟艷，徐衛(wèi)亞，張強.點與多邊形或多面體的拓撲關(guān)系判斷［J］.計算機工程與設(shè)計，2015，36（4）:972-976.

［11］王鵬飛.四邊形阻抗原理應(yīng)用中出現(xiàn)的問題及解決辦法［J］.陜西電力，2011（8）：79-81，89.

［12］施先旺，劉婷婷，李國良.采用有限狀態(tài)機實現(xiàn)控制指令的可靠檢測［J］.火箭推進，2011（5）：63-68.

［13］趙志偉，陳學有，潘瓊.采用特征值法和Prony法相結(jié)合的PSS自適應(yīng)控制［J］.陜西電力，2012（6）：49-52，62.

［14］張偉，陳鋒，馬軍強，等.軌/姿控發(fā)動機脈沖后效沖量快速算法的研究及應(yīng)用［J］.火箭推進，2012（1）：51-56.

Point inclusion test method based on dichotomy

YU Kai，YU Meng-hong
（College of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang 212003，China）

Point inclusion test is a basic algorithm of computer graphics，it's purpose is to determine whether a test point is in the specific polygon.Traditional ray-crossing method and angle algorithm have relative low efficiency，their average time complexity are O（n）.So，if a polygon has a great many edges or test points，these algorithms will take much more time.This paper analyses the shortcomings of traditional ray-crossing method and angle algorithm，then proposes an efficient point-inpolygon test method based on dichotomy.At last，this paper uses many experiments to show that the average time complexity of this algorithm is O（n/2）.By partitioning convex polygon recursively and judging the relative position between points and the line，this method eventually translate this problem into judging the relative position between triangle and points.Compared with the classic algorithms，such as the ray crossing method or the angle algorithm，this algorithm not only have the advantage rapid and stable，also can give which triangle region the points locate in.

convex polygon；dichotomy；include testing；recursive partitioning

TN0

A

1674－6236（2016）16-0187-04

2015-09-06稿件編號：201509043

于 凱（1989—），男，江蘇徐州人，碩士研究生。研究方向：模式識別與智能系統(tǒng)，圖像處理。