基于八區(qū)域的簡單多邊形頂點凸凹性識別算法

薛 理 楊樹文 王中輝 張 珊 馬吉晶

(蘭州交通大學測繪與地理信息學院 甘肅 蘭州 730070) (甘肅省地理國情監(jiān)測工程實驗室 甘肅 蘭州 730070)

0 引 言

簡單多邊形頂點凸凹性的判斷是計算機圖形學的基本問題，隨著計算機的發(fā)展，在模式識別、圖像處理、曲面插值等方面應用廣泛[1]。因此，如何快速、準確地判斷多邊形頂點凸凹性具有重要意義。

學者們已在該研究領域進行了大量卓有成效的研究，提出了多種識別算法[1-6]：如面積判斷法[1]、叉積判斷法[2]和象限判斷法[3]等。其中，面積判斷法首先通過極值點確定多邊形方向，進而計算各個頂點的有向面積來判斷頂點的凸凹性；叉積判斷法對每條邊定義矢量方向，利用各點相鄰兩條矢量的矢量叉積來確定頂點凸凹性；象限判斷法先假設多邊形為逆時針方向，然后根據(jù)角兩邊在直角坐標系四個象限內(nèi)的特性確定頂點內(nèi)角的范圍，進而判斷頂點的凸凹性。

上述多邊形頂點凸凹性的判斷算法多是通過定量的方式來判斷頂點的凸凹性，雖然這些算法的正確率高、思路簡潔，但計算量偏大，且未將定性與凸凹性聯(lián)系起來。通過象限判斷法來確定角度范圍，進而將定性與凸凹性聯(lián)系起來，達到判斷的目的。該方法不僅思路清晰，而且能避免大量計算，提高算法效率。然而，象限法未能充分利用角的范圍在直角坐標系內(nèi)的特性，因此只能在一定程度上加快判斷速度。

綜上所述，本文將坐標系平面平均劃分為八個區(qū)域來確定角度的范圍，進而通過定性的方式確定頂點凸凹性，能夠更充分地利用角的兩邊在平面坐標系內(nèi)的特性，減少算法計算量。同時，該算法能夠有效地判斷多邊形的方向，進一步提高算法的效率。

1 相關定義

為方便理解本文算法，在文獻[1]的基礎上給出如下定義：

定義1設存在多邊形p1,p2,…,pi,pi+1,…,pn,p1，若任意相鄰三點不在同一直線上，且任意相鄰兩邊只相交于一個端點，不相鄰兩邊不相交，則該多邊形為簡單多邊形。

定義2如果簡單多邊形相鄰的兩邊所形成的內(nèi)角(即朝向多邊形區(qū)域內(nèi)的角)不大于180°，則該角為凸角，否則為凹角。

定義3設存在簡單多邊形p1,p2,…,pi,pi+1,…,pn,p1，如果沿p1,p2,…,pn,p1方向走，如果該多邊形所圍成的區(qū)域總在左側(cè)，則稱該多邊形為逆時針多邊形，否則為順時針多邊形。也可以通過計算y值最小值頂點相鄰兩邊夾角來判斷多邊形的方向，詳細步驟請看2.2節(jié)多邊形方向的確定。

2 算法原理

2.1 平面的八區(qū)域

根據(jù)平面八區(qū)域的定義，給定線段op以端點o為坐標原點，x、y軸分別置于水平位置與豎直位置，取向右與向上的方向分別為x、y軸的正方向，形成平面直角坐標系。令線段op沿著順時針方向轉(zhuǎn)到x軸正方向所經(jīng)過的角度為θ，并且θ從0°開始每隔45°為一個區(qū)域，比如第一區(qū)域內(nèi)0°≤θ<45°，第二區(qū)域內(nèi)45°≤θ<90°以此類推，將坐標系平面分為八個區(qū)域，如圖1所示。

圖1 平面八區(qū)域

2.2 多邊形方向的確定

前人研究表明[7-8]，簡單多邊形中y最小值的頂點一定為凸頂點，即內(nèi)角小于180°。根據(jù)這一特性，先確定y最小值頂點，再按照一定的方向分析最小值頂點兩邊夾角的范圍，進而判斷簡單多邊形的方向。其具體實現(xiàn)過程如下所示：

在簡單多邊形p1p2p3p4p5p6p1中(如圖2、圖3)，p4為y最小值的頂點，該點的內(nèi)角必定小于180°。沿著p4p3邊順時針轉(zhuǎn)到p4p5邊形成的角度為θ，由于該多邊形為簡單多邊形因此θ不會等于0°、180°或360°，判斷θ的范圍在2.3節(jié)詳細介紹。如果該多邊形方向為逆時針則θ小于180°如圖2所示，如果多邊形方向為順時針則θ大于180°如圖3所示，反之亦然。因此可得如果θ小于180°則多邊形方向為逆時針，如果θ大于180°則多邊形方向為順時針。

圖2 逆時針多邊形 圖3 順時針多邊形

2.3 頂點凸凹性判斷方法

多邊形分為逆時針多邊形和順時針多邊形兩種類型，只要了解其中一種多邊形頂點的凸凹性判斷方法，另外一種可以類推出來，因此，本文僅詳細描述簡單逆時針多邊形中頂點凸凹性的判斷方法。

設p1p2p3p4p5p6p7是一個簡單逆時針多邊形，判斷頂點p4(x4，y4)的凸凹性，如圖4所示。

圖4 簡單逆時針多邊形

以p4為原點建立平面直角坐標系，x、y軸分別置于水平位置與豎直位置，取向右與向上的方向分別為x、y軸的正方向。以p4p3為起始邊，沿著順時針方向旋轉(zhuǎn)到邊p4p5所形成的角度為θ，則θ為頂點p4的內(nèi)角，如圖5所示。由于該多邊形為簡單多邊形，因此θ不會等于0°、180°或360°。

圖5 頂點p4的內(nèi)角θ

由于p4p3位于第八區(qū)域，p4p5位于第六區(qū)域，由兩邊在平面八區(qū)域的特性容易得出角θ<180°，即p4為凸頂點。同時也可以得出，如果p4p5位于第一、二或三區(qū)域，則θ>180°，那么p4為凹頂點；如果p4p5位于第五、六或七區(qū)域，則θ<180°，那么p4為凸頂點。如果p4p5位于第四區(qū)域，需要判斷p4p3和p4p5的斜率。如果(y3-y4)÷(x3-x4)<(y5-y4)÷(x5-x4)，即(y3-y4)× (x5-x4)>(y5-y4)×(x3-x4),則θ<180°，那么p4為凸頂點。如果(y3-y4)÷(x3-x4)>(y5-y4)÷(x5-x4)，即(y3-y4)× (x5-x4)<(y5-y4)×(x3-x4),則θ>180°，那么p4為凹頂點。如果p4p5位于第八區(qū)域，需要判斷p4p3和p4p5的斜率。如果(y3-y4)÷(x3-x4)>(y5-y4)÷(x5-x4)，即(y3-y4)× (x5-x4)>(y5-y4)×(x3-x4),則θ<180°，那么p4為凸頂點。如果(y3-y4)÷(x3-x4)<(y5-y4)÷(x5-x4)，即(y3-y4)× (x5-x4)<(y5-y4)×(x3-x4),則θ>180°，那么p4為凹頂點。同理可以類推出p4p3位于其他區(qū)域內(nèi)頂點p4的凸凹性。

如果多邊形為順時針方向，可根據(jù)θ′=360°-θ，由θ的范圍推出θ′的范圍，再根據(jù)θ′來判斷頂點凸凹性。

3 算法描述和算法分析

3.1 算法描述

根據(jù)上述原理和算法，本文提出了改進的簡單多邊形頂點凸凹性識別算法，具體步驟如下：

Step1給定簡單多邊形pi(xi,yi),i=1,2,…,n,pn+1=p1，遍歷所有頂點，求出y值最小值的頂點ymin=MIN(yi)。

Step2線段yminymin-1沿著順時針方向旋轉(zhuǎn)到線段yminymin+1的角度為θ，根據(jù)θ在八個區(qū)域內(nèi)的特性判斷其范圍，如果θ<180°則多邊形為逆時針多邊形，否則為順時針多邊形。

Step3遍歷每個頂點，利用角的兩邊在八區(qū)域內(nèi)的特性判斷頂點θi的范圍，如果多邊形為逆時針轉(zhuǎn)到Step4，否則轉(zhuǎn)到Step5。

Step4如果θi<180°，那么pi為凸頂點，否則為凹頂點，算法結(jié)束。

Step5如果θi<180°，那么pi為凹頂點，否則為凸頂點，算法結(jié)束。

3.2 算法分析與驗證

通過2.3節(jié)提出的凸凹性判斷方法可以看出，在多邊形方向已知的情況下，對于一個頂點pi凸凹性的判斷，在最有利的情況下，邊pi-1pi在邊pi+1pi左邊或右邊相鄰的三個區(qū)域，則只需要六次判斷即可；在最壞的情況下，邊pi-1pi在邊pi+1pi相對或同一區(qū)域，則需要判斷斜率，增加兩次乘法運算。即在邊pi-1pi所在區(qū)域確定的情況下，pi+1pi在六個區(qū)域內(nèi)只需判斷，在余下兩個區(qū)域內(nèi)需要計算乘法。原有算法(文獻[3]提出的算法)判斷頂點pi凸凹性，在邊pi-1pi所在象限確定的情況下，pi+1pi在相鄰兩個象限內(nèi)只需判斷，在另外兩個象限內(nèi)需要計算乘法[3]。因此新算法相對于原算法，更能有效地避免耗時的乘法運算。

論文采用C#編程實現(xiàn)多邊形頂點凸凹性的判斷，首先隨機生成502、1 002和50 002個點，存儲在Excel表中。然后假設每相鄰三個點形成簡單逆時針多邊形的一個頂點，接著采用原算法A與本文算法B，在運行一萬次的情況下判斷每組數(shù)據(jù)的凸凹性。由于文獻[3]提出的原算法已經(jīng)和文獻[1]、文獻[6]的算法比較過，所以本文就不再比較。

通過實驗得出改進后的算法和原算法結(jié)果一致，但在時間上，改進后的算法判斷速度更快，兩種算法時間對比如表1所示。由表1得出改進后的算法在數(shù)據(jù)相同情況下判斷所需的時間是原算法所用時間的76%左右，且頂點越多提高的效率越明顯。因此改進后算法具有更高的識別效率。

表1 原算法與本文算法對比

4 結(jié) 語

本文在四象限算法的基礎上提出基于八區(qū)域的簡單多邊形頂點凸凹性識別算法。該算法利用角兩邊在八個區(qū)域內(nèi)的特性，判斷角度范圍，進而判斷頂點凸凹性，從而在一定程度上避免角度、面積或矢量叉積等定量分析所需的計算量。另一方面利用y值最小值頂點一定是凸頂點的特點和八區(qū)域方法判斷多邊形方向。該算法時間復雜度為O(n)，思路清晰，易于理解，而且計算量小，效率較高。實驗表明改進后的算法，效率有明顯的提高。

該算法的不足之處在于：1) 雖然算法利用定性的八區(qū)域方法判斷頂點凸凹性，減少了耗時的乘法運算，但增加了判斷運算。如何同時確定多個頂點的凸凹性，去掉多余的判斷運算，有待于進一步分析；2) 該方法目前只適用于簡單多邊形，對于自相交等復雜多邊形不適用，需要對該算法進一步改進，增加相應的規(guī)則，擴展算法的應用范圍。

[1] 劉潤濤.任意多邊形頂點凹、凸性判別的簡捷算法[J].軟件學報,2002,13(7):1309-1312.

[2] 陳炳發(fā),錢志峰,廖文和.簡單多邊形凸凹性自識別算法[J].計算機輔助設計與圖報,2002,14(3):214-217.

[3] 魏東,朱功勤.任意多邊形頂點凸、凹性判定的一種算法[J].合肥工業(yè)大學學報(自然科學版),2006,29(3):373-375.

[4] 陳亞婷,嚴泰來,朱德海.基于辛普森面積的多邊形凹凸性識別算法[J].地理與地理信息科學,2010,26(6):28-30.

[5] 史萬明.多邊形頂點為凹、凸點的計算機判別方法[J].計算機輔助設計與圖形學學報,1990(3):15-16.

[6] 馬小虎,潘志庚,石教英.確定多邊形凸凹頂點的快速算法及其應用[J].計算機工程與設計,1998(3):44-48.

[7] 閆浩文,王明孝,王中輝.計算幾何[M].北京:科學出版社,2012.

[8] 陳國軍,劉婧怡,黃瑩瑩.矢量與柵格結(jié)合的分塊平面區(qū)域幾何劃分算法[J].系統(tǒng)仿真學報,2016,28(10):2460-2466.