基于二分法的凸多邊形內外點判別算法

于凱，俞孟蕻

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003）

基于二分法的凸多邊形內外點判別算法

于凱，俞孟蕻

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003）

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

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

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

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

1　基本約定與算法思想

1.1算法原理與依據

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

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

1.2頂點向量

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

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

1.3凸多邊形的分割

定義1凸多邊形是指沒有任何一個內角是優角 （大于180度小于360度）的多邊形。

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

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

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

1）求取分割線

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

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

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

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

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

1.4遞歸分割

遞歸分割時，分割線左側端點不動，根據點與分割線的位置關系，將分割后的凸多邊形再次進行分割［13］。一個凸多邊形經過分割后最終會形成若干個三角形。最終將點與凸多邊形的關系轉化為點與三角形的關系。

1.5待測點的區域判斷

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

圖1　凸多邊形的區域劃分

圖2　待測點的分布區域

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

2　算法描述

算法主要步驟如下：

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

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

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

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

3　計算量分析

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

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

4　實驗與分析

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

1）測試凸多邊形頂點個數與算法耗時的關系

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

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

2）測試待測點個數與算法耗時的關系

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

圖3　頂點個數與算法耗時關系

表1　頂點個數與算法耗時比較

圖4　待測點個數與算法耗時關系

表2　待測點個數與算法耗時比較

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

5　結　論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

［14］張偉，陳鋒，馬軍強，等.軌/姿控發動機脈沖后效沖量快速算法的研究及應用［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—），男，江蘇徐州人，碩士研究生。研究方向：模式識別與智能系統，圖像處理。