快速多邊形區域三角化算法與實現

收稿日期：2007-11-26；修回日期：2008-03-04

基金項目：國家自然科學基金資助項目(50774092)

作者簡介：畢林(1975-)，男，博士研究生，主要研究方向為GIS、數字礦山軟件(mr.bilin@163.com)；王李管(1964-)，男，博導，主要研究方向為數字礦山；陳建宏(1963-)，男，博導，主要研究方向為礦山GIS；馮興隆(1980-)，男，博士研究生，主要研究方向為數字礦山*

(1.中南大學 資源與安全工程學院，長沙 410083; 2.長沙迪邁信息科技有限公司， 長沙 410083)

摘 要：多邊形區域三角化的基本思想是：首先將簡單多邊形分解為多個單調多邊形，然后對每個單調多邊形進行三角化。快速多邊形區域三角化算法先由多邊形頂點的位置特征分為不同的類型，并沿指定方向對頂點進行排序，然后順序取出各頂點，根據頂點類型，確定準單調多邊形的產生、增長或結束，最后對所產生的多個單調多邊形進行三角化。該算法充分利用多邊形的頂點、邊的拓撲關系，計算量少、實現簡單，適用于帶有洞、島的任意簡單多邊形，速度較快。

關鍵詞：多邊形；單調多邊形；拓撲關系；線性時間復雜度；三角化

中圖分類號：TP391. 72

文獻標志碼：A

文章編號：1001-3695(2008)10-3030-04

Fast triangulation algorithm for polygon regions and implementation

BI Lin¹，2， WANG Li-guan¹，2， CHEN Jian-hong¹， FENG Xing-long¹

(1.School of Resources Safety Engineering，Central South University，Changsha 410083，China; 2.Digital Mine Co.Ltd，Changsha 410083，China)

Abstract:The basic idea of triangulation for simple triangle was described as follows: the polygon was subdivided into mono-tonous polygons and then triangulated. The algorithm classified all the vertexes by its location characteristics， and sorted them along the appointed axis， and then selected the vertexes orderly to decide the creation， expansion or formation of a monotonous polygon by its type， at last triangulated the formative monotonous polygon. In the algorithm， the topology of the vertexes and edges made full use of so as to reduce calculation task， simplify implementation and made it suitable for any simple triangle with holes and islands ， speediness and nearly linear time complexity.

Key words：polygon; monotonous polygon; topological relationship; linear time complexity; triangulation

多邊形的三角剖分就是在不產生新頂點的條件下將平面多邊形劃分成一系列不相重疊的三角形[1]。在計算機圖形學、圖像處理、機械仿真等領域，經常要解決平面多邊形的三角剖分問題。多邊形三角剖分的算法很多，如Toussaint等人提出來的Recursive Ear Cutting 算法；Garey等人[2]提出的Sweep Line algorithm算法；Seidel[3]提出的Incremental Randomized 算法等.在這些算法中Recursive Ear Cutting性能較差，較難擴展到帶洞多邊形的情況。Incremental randomized算法性能較好，但未見實現方面的報道。Chazelle[4]證明了多邊形的三角剖分可以在O（n）級時間內完成，但他的這種算法的實現非常困難[5]。李學軍等人[6]提出的快速算法只是在單調多邊形三角化時的時間復雜度為O（n），而在多邊形單調化時復雜度比O（n）要高，同時對含有島的多邊形是否支持還有待于進一步驗證。劉海濤等人[7]提出的算法是將凹邊形分解成凸多邊形，再通過添加輔助點的方式對子多邊形進行三角剖分，時間復雜度為O (jn+n log n+jk log n)。本文從多邊形內在幾何關系出發，建立適當的數據結構，實現了一種快速三角化算法，在不考慮數據前期處理的情況下，時間復雜度近似為O（n）的多邊形三角化算法。該算法適應于帶洞、島的任意簡單多邊形，實現較為簡單，計算量較少。

1 基本原理和方法

本算法的基本原理是首先將簡單多邊形按照一定的規則拆分為一個或多個單調多邊形，然后通過對單調多邊形的三角化來實現對簡單多邊形的三角化。如果將一個多邊形邊界劃分為兩條折線，且這兩條折線都是以某條直線為投影方向的單調折線，則該多邊形被稱為單調多邊形[8]。為了建立多邊形三角化算法，首先根據數據的幾何關系建立頂點數據數組VerTexArray及邊數據鏈表EgesLink。其數據結構如下：

a）頂點

struct vertex

{

int PntId;//頂點ID號

int LorR;//左還是右節點.0:起點，1:左， 2:右

struct booltessedge *NextEdge; //下條邊

struct booltessedge *PrevEdge; //上條邊

}

b）邊

struct edge

{

struct vertex * Vertexes[2];

//兩個端點，[0]：前端點，[1]：后端點

struct edge *Next; //下一條邊

struct edge *Prev;//上一條邊

}

然后按某條軸線對頂點數組進行排序，再順序取出各頂點，不斷形成一個或多個準單調多邊形。準單調多邊形是該算法中一個重要概念。

定義1 準單調多邊形。在簡單多邊形拆分成單調多邊形的過程中，由已經取出的頂點和邊的全部或部分組成的還未形成單調多邊形前的圖形稱為準單調多邊形(QP)。準單調多邊形的數據結構如下:

c）準單調多邊形

struct quasi-monotonous-polygon

{

struct vertex ** Vertexex; //頂點數組

intNumVtx; //頂點個數

struct edge* HeadEdge; //頭邊

struct edge*TailEdge;//尾邊

struct vertex *PrevVtx//最近一次進入該QP的頂點

}

定義2 單調增長。在加入當前頂點后不影響QP的單調性的增長稱為單調增長。

在單調多邊形的形成過程中，根據新加入頂點的類型判斷該頂點在單調多邊形形成過程中的作用，即由它或者形成新的QP，或者加入到已有QP中使其發生單調增長，或者是已有QP的閉合點從而形成最終的單調多邊形。該算法就是在QP不斷地產生→增長→形成單調多邊形→三角化過程中完成。在增長的過程中可能使QP發生分裂，也可能產生新的QP。其過程如圖1所示。其中，QP的分離是指當某一頂點加入時將一QP分離成兩個QP。在實現過程中，QP的增長過程是通過如下方式進行：順序取出各頂點，判斷該頂點的加入是否影響QP的單調性，如果仍保持單調性，則將該頂點的上一條邊（prevEdge）作為QP的尾邊（tailEdge），下一條邊（nextEdge）作為QP的頭邊（headEdge）。在準多邊形的產生、增長以及形成過程中都必須保持多邊形的各邊首尾相連的連通性。其處理方法如下：通過判斷本次增長與上次增長是否在同一邊。如果不在同一邊，則添加兩條以最近兩次加入的頂點為端點、方向相反的邊。這兩條邊將該QP前部分封閉成單調多邊形，后部分繼續增長，如圖2所示，從而保證多邊形的連通性，以使該算法得以正確進行。

定理1 如果某QP的頭邊（headEdge）為待加入頂點的上一條邊（prevEdge），或者尾邊(tailEdge)為待加入頂點的下一條邊（nextEdge），則加入該頂點后不影響該QP的單調性。

證明 假設多邊形以逆時針為正向，頂點排序以Y軸為索引軸、升序排列，依次從小到大取出各頂點（以下都遵從該假設）。如圖3所示，設V1為QP上前一次加入的頂點，V2為待加入頂點，如果QP.tailEdge == V2.nextEdge，由上面提到的QP的增長過程可知，QP.tailEdge = =V1.prevEdge，所以有V2.nextEdge == V1.prevEdge，故V1、V2是一條邊（tailEdge）的兩個端點，所以任何垂直于Y軸的直線與V1V2的交點只有一個，即V1到V2為單調的。同理可以證明QP的頭邊（headEdge）為待加入頂點的上一條邊（prevEdge）的情況。

定義3 單調增長點。滿足定理1條件的頂點稱為QP的單調增長點。

定義4 頭單調增長點。如果待加入頂點的上一條邊（prevEdge）為QP的頭邊（headEdge），則該頂點稱為頭單調增長點。

定義5 尾單調增長點。如果待加入頂點的下一條邊（nextEdge）為QP尾邊(tailEdge)，則該頂點稱為尾單調增長點。

定義6 閉合點。如果待加入頂點既是同一個QP的頭單調增長點又是尾單調增長點，該頂點必然使該QP閉合，稱其為閉合點。

定義7 合并點。如果待加入頂點屬于不同QP的頭單調增長點又是尾單調增長點，該頂點必然使這兩個QP合并，稱其為合并點。

定義8 尖點。如果共用一個頂點的兩條邊的另外兩個端點的索引值都大于該頂點索引值，這樣的點稱為尖點[9]。

根據尖點相對于QP的位置，可以將其細分為三種類型，即環上尖點、洞環尖點和島環尖點，如圖4所示。

定義9 洞環尖點。當逆時針方向為多邊形的方向時，其內部表達洞的環方向為順時針。在QP增長過程中，該環上第一個出現的尖點稱為洞環尖點。

定義10 島環尖點。洞中與其方向相反的環為島環，在QP增長過程中，該環上第一個出現的尖點稱為島環尖點。

定義11 環上尖點。不屬于洞環尖點和島環尖點的尖點稱為環上尖點。

定理2 如果QP的頭邊（headEdge）不是待加入頂點的上一條邊（prevEdge），同時尾邊(tailEdge)也不是待加入頂點的下一條邊（nextEdge），則該頂點必為尖點。

證明 如圖3所示，V為待加入的頂點，V1為上一次加入的點，V.nextEdge≠QP.tailEdge，用反證法證明，假設共用該頂點的兩條邊的另外頂點V2、V3的索引值Y都不大于V的索引值，如YV2 < YV，由于頂點是從小到大順序取出的，對于邊〈V，V2〉來說，V2必定先于V一步取出，即QP.tailEdge=V2.prev-Edge = V.nextEdge，這與條件V.nextEdge≠QP.tailEdge矛盾，P0命題得證。同理可以證明QP的頭邊不是待加入頂點的上一條邊時的情況。

定義12 設向量V1V2，頂點V0，W=V0V1×V0V2，則將W方向定義為頂點V0到向量V1V2的方向，且規定當方向與多邊形方向一致時方向為正，反之為負。

定理3 在QP增長過程中，當且僅當頂點到某QP的頭邊與尾邊的方向都為正時，該頂點是該QP的洞環尖點。

證明 先證明其充分性，根據洞環尖點的定義，它是在QP增長過程中，某洞環上出現的第一個尖點，則此時該洞環的外環上的邊必定已部分加入到某QP中，洞是由內環與外環構成，外環與多邊形方向一致，同時內環上的各點必然在外環內部（頭邊的左邊，尾邊的右邊），由右手法則可知洞環尖點與由外環邊加入到該QP的頭邊與尾邊的方向都為正；必要性，用反證法證明，假設洞環尖點到QP的尾邊的方向為負，則由右手法則可知該點必然在尾邊左邊；同樣假設洞環尖點到QP的頭邊的方向為負，則由右手法則可知該點必然在頭邊的右邊，這與內環上各點必然在外環內部矛盾，命題得證。

由定理3可以導出推論1。

推論1 在QP增長過程中，當頂點到某QP的頭邊或尾邊的方向為負時，該頂點必是該QP的島環尖點或環上尖點。

島環尖點或環上尖點都不應該與QP之間有“橋”[7]，相反洞環尖點與QP上是有“橋”的，所以要在它們之間添加新邊。

2 多邊形三角化算法

該算法用類C語言描述如下：

算法1多邊形三角化算法

PolygonTriangulation（）

{

for ( pos=0; pos<頂點個數; pos++ )

{

currVtx = this->VerTexArray[pos];

//判斷currVtx是否是某QP的單調增長點；定理1

if (currVtx是頭單調增長點)

{

if(QP. PrevVtx

QP. HeadEdge->Vertexes[0])

//最近兩次不在同一邊增長

{

AddNew2Edges (QP.PrevVtx，currVtx);

//添加以這兩點為端點的兩條方向相反的邊

MonoTriangulation(QP);//算法2，

//前部分形成的單調多邊形三角化

}

//增長

QP.HeadEdge = currVtx->NextEdge;

QP.PrevEdge = currVtx;

currVtx->LorR = 2;

}

else if (currVtx是尾單調增長點)

{

if ( QP. PrevVtx

QP. TailEdge->Vertexes[1])

//最近兩次不在同一邊增長

{

AddNew2Edges(QP.PrevVtx，currVtx);

//添加以這兩點為端點的兩條方向相反的邊

MonoTriangulation(QP);//算法2，

//前部分形成的單調多邊形三角化

}

//增長

QP.TailEdge = currVtx->PrevEdge;

QP.PrevEdge = currVtx;

currVtx->LorR = 1;

}

else if (currVtx是閉合點)

MonoTriangulation(QP);

else if (currVtx是合并點)

{

if ( QP1. PrevVtx

QP.1 HeadEdge->Vertexes[0])

//currVtx在QP1的頭邊單調增長

{

AddNew2Edges(QP1.PrevVtx，currVtx);

MonoTriangulation(QP1);//算法2

}

if ( QP2. PrevVtx

QP2. TailEdge->Vertexes[1])

// currVtx在QP2的尾邊單調增長

{

AddNew2Edges(QP2.PrevVtx，currVtx);

MonoTriangulation(QP2);//算法2

}

QP2.TailEdge = QP1.TailEdge;

QP2.PrevEdge = currVtx;

currVtx->LorR = 0;//起點

}

else //尖點，定理2

{

計算currVtx到QP.HeadEdge的方向；

if (方向 <0)產生新QP；//島環尖點或環上尖點，推論1

else if ( 方向 > 0)//洞環尖點，定理3

{

AddNew2Edges(QP.PrevVtx，currVtx);//產生新QP；

}

else 產生新QP；

currVtx->LoR = 0;//起點

}} }

算法2 單調多邊形的三角化

單調多邊形三角化方法舉例說明，如圖5所示。單調多邊形QP分別由兩條折線鏈表L_Chain（A、F、G），R_Chain(A、B、C、D、E、H)組成。

a)從R_Chain中連續取出A、B、C三個頂點形成鏈L，這三個頂點都在右邊折線鏈表上，∠ABC為銳角，這樣A、B、C三點可以組成一個三角形，A、C相連形成一條斜線，同時從L中移出頂點B；

b)向L添加頂點D，∠ACD為鈍角，△ACD在多邊表外部，則繼續向L添加點E，此時L中數據為（A、C、D、E）；

c)向L中添加頂點F，F點屬于L_Chain，而其他點都屬于R_Chain，并且每個角都為鈍角，所以可以將F與C、D、E相連，得到△ACF、△FCD、△FDE三個三角形，然后從L中移出A、C、D三個頂點，此時L中的數據為（F、E）。

d)繼續順序取出QP中的各頂點，進行以上操作，直到該QP中的所有頂點全部取出。

MonoTriangulation(QP)

{

V1=QP. Vertexex[0];

V2=QP. Vertexex[1];

L.Add(V1); L.Add(V2);

for ( pos = 2;pos < QP.NumVtx; pos++)

{

V3 = QP. Vertexex[pos];

L.Add(V3);

if(V3.LorRV2.LorR )//不在同一邊

{

V3與L中除第一個頂點外所有頂點相連形成三角形；

從L中刪除除最后兩個頂點外的所有頂點；

V1 = L.GetAt(0);

V2 = L.GetAt(1);

}

else

{

if(∠V1V2V3是銳角)

{

連接V1、V3；

從L中刪除V2；V2=V3;

}}}}

3 算法分析

對于含有洞和島的多連通多邊形的三角化問題，已有很多人提出不同的算法，如陳向平等人[10]提出的橋邊算法，但在該算法中引入橋邊的技巧較難把握，實現的程序結構復雜。鄧先禮等人[11]對橋邊算法進行了改進，但時間復雜度為O（n²）。徐春蕾等人[12]提出的GTP算法，將數據形成內外環兩個鏈表，不適應于內環中還有環的情況，即不適用于帶島及內外環多級嵌套的多邊形區域。本算法充分利用多邊形的頂點、邊的拓撲關系，同時通過沿某一軸線對頂點進行排序，這樣也內含了頂點的空間關系，并采取合理的數據結構來記錄這些關系。該算法順序取出各頂點，首先通過簡單的幾何關系判斷是否是單調增長點，然后根據不同的單調增長點類型（頭單調增長點、尾單增長點、閉合點、合并點）進行不同的處理，這些處理都不需要任何計算，只需簡單邏輯比較，所以該算法的計算量較小，提高了其運行速度。對于屬于尖點的頂點，也只需計算該頂點到QP的頭邊與尾邊的方向來判斷它屬于哪種類型的尖點，而該計算較為簡單、耗時較少。該算法運行過程中會不斷產生新的QP，而當QP擴展成單調多邊形后，隨即被三角化，如果某一時刻只有一個QP，那么該算法的時間復雜度為O(n)。當有多個QP同時存在時，對于每個待加入的頂點，都需要判斷其在每個QP中的點的類型，但是對于簡單多邊形而言，每一個頂點的類型（除開閉合點）只歸宿于一個QP，所以在算法中，只要明確了一個點的類型就不再需要再與其他QP進行判斷。同時存在QP個數與多邊形的形狀及洞與島的個數及其嵌套深度、分布有關，很難用數學方式來準確表達。實驗表明當同一垂直于索引軸方向存的尖點、洞島越多，則同時存在的QP個數越多，但即使在最壞的情況下同時存在QP的個數也遠小于頂點個數，所以該算法時間復雜度遠小于O（n²），可以認為，在不考慮數據前期處理的情況下，它是一種近似線性時間復雜度的算法。

4 算法實現與實驗

通過VC++開發工具實現了該算法，運行環境為Windows 2000 操作系統，CPU為Intel Pentium4 3.00 GHz，內存512 MB。對圖6所示的數據進行三角化，并對頂點坐標進行線性插值加密頂點個數，分別得到頂點個數為17 809、35 615、53 422、71 288、89 032的區域，對其進行三角化實驗結果如表1所示，并做出頂點個數—三角化時間曲線圖，如圖7也可以看出，該算法時間復雜度近似線性。

表1 不同頂點個數的三角化耗時比較頂點個數時間/s三角形個數17 8090.03117 80535 6150.06335 61153 4220.10953 41871 2280.14171 22489 0320.18789 0285 結束語

本文提出的多邊形三角化算法充分利用多邊形的頂點、邊的拓撲關系，減少算法的計算量，降低了實現難度。該算法時間復雜度近似線性、可靠性高、通用性強，適用非自相交的各種復雜程度的多邊形區域三角化。

參考文獻：

[1]馬小虎，潘志庚，石教英.基于凹凸頂點判定的簡單多邊形Delaunay三角剖分[J]. 計算機輔助設計與圖形學學報， 1999，11 (1):1-3.

[2]GAREY M R，JOHNSON D S， PREPARATA F P， et al.Triangulating a simple polygon[J]. Information Proceeding Letters， 1978， 7 (4) : 175-179.

[3]SEIDEL R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons[J]. Comput Geom Theory Appl， 1991，1(1):51-64.

[4]CHAZELLE B. Triangulating a simple polygon in linear time[J]. Discrete Comp Geom， 1991， 6(5):485-524.

[5]WU Liang. Fast and robust simple polygon triangulation with/without holes by sweep line algorithm[EB/OL]. [2007-03-18]. http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html.

[6]李學軍，黃文清. 平面區域三角化的快速算法[J].計算機輔助設計與圖形學學報， 2003，15(2):233-238.

[7]劉海濤，張三元，葉修梓. 一種快速相容三角剖分算法[J]. 計算機應用研究，2007，24（1）:235-237.

[8]羅廣祥， 馬智民.基于單調性圖形綜合的面狀要素名稱注記定位線確定[J]. 地球科學與環境學報， 2004，26(2):75-80.

[9]SCHNEIDER P J， EBERLY D H. Geometric tools for computer graphics[M]. Beijing: Publishing House of Electronics Industry ， 2004 .

[10]陳向平，應道寧. 統一于NIP的多邊形三角剖分算法[J].計算機學報，1989 ，12(3):194-199.

[11]鄧先禮，胡達，杜小平.多連通多邊形三角化找橋算法的研究及實現[J].計算機與現代化，2004(5):4-6.

[12]徐春蕾， 李思昆. 一種適用任意平面多邊形的三角剖分算法[J]. 國防科技大學學報，2000，22(2):82-85.