一種基于單調(diào)多邊形的三角剖分算法

徐 敏， 朱二喜, ， 何援軍

（1. 江蘇信息職業(yè)技術(shù)學(xué)院，江蘇 無錫 214153；2. 上海交通大學(xué)計算機工程系，上海 200240）

三角剖分是計算機輔助幾何設(shè)計、幾何造型及計算機圖形學(xué)中研究的重要內(nèi)容之一，在有限元分析、幾何重構(gòu)、數(shù)字地形分析、計算機圖形學(xué)及機器人等領(lǐng)域有重大應(yīng)用。

Chazelle[1]證明了多邊形的三角剖分可以在O(n)時間復(fù)雜度內(nèi)完成，但算法實現(xiàn)非常困難。肖忠暉等[2]以切耳算法[3]為基礎(chǔ)，實現(xiàn)簡單多邊形的三角化。馬小虎[4]等人提出的一種基于凹凸頂點判定的簡單多邊形Delaunay三角剖分算法，思路清晰，程序?qū)崿F(xiàn)簡單，剖分質(zhì)量高，且計算效率相對較高。李學(xué)軍等人[5]提出的快速算法，先將多邊形分割成多個單調(diào)多邊形，然后對單調(diào)多邊形進行三角化，不過該算法只是在單調(diào)多邊形三角化時的時間復(fù)雜度為O(n)，而在多邊形單調(diào)化時復(fù)雜度比O(n)要高。畢林等提出的快速三角化算法[6]，在不考慮前期處理的情況下時間復(fù)雜度近似O(n)的多邊形三角化算法，適用于帶內(nèi)孔的任意簡單多邊形，實現(xiàn)較為簡單，計算量較少。

對于含有內(nèi)孔的多邊形（多連通多邊形），可以通過引入橋邊將其外輪廓線與內(nèi)孔連接起來轉(zhuǎn)化為退化的多邊形。這種加入橋邊運算復(fù)雜，程序結(jié)構(gòu)也復(fù)雜，同時需要處理掛邊現(xiàn)象。如陳向平等人[7]提出的橋邊算法，鄧先禮等人[8]對陳向平等人的算法進行改進。徐春蕾等人[9]提出的 GTP算法，將數(shù)據(jù)形成內(nèi)外環(huán)兩個鏈表，不適應(yīng)于內(nèi)環(huán)中還有環(huán)的情況。

本文提出的算法適用于含有任意個內(nèi)孔的多邊形，先根據(jù)邊界y向局部極值頂點作出水平分割線，將多邊形劃分成單連通y單調(diào)多邊形，然后再對單調(diào)多邊形進行三角剖分，最終完成對初始多邊形的三角剖分。

1 幾何理論

定義1[10]邊界頂點排序 多邊形每一邊界（外邊界及內(nèi)孔）的頂點按下列原則排序：當人順著多邊形邊界行走時，他的左手指向多邊形的內(nèi)部。

按照定義1，對于凸多邊形，這個原則意味著：多邊形的外邊界為逆時針走向，內(nèi)邊界為順時針走向。而多邊形的每一條邊界均為一個向量，這個要求并不苛刻。

定義2[10]兩向量交點的特征值 兩向量交點的特征值由其矢量積的方向定義，特征值的絕對值取為 1。因此，兩個向量交點的特征值有 2個，分別對應(yīng)于求交的兩個向量，且這2個特征值的符號相反，其代數(shù)和為0。如圖1所示，兩向量各種交點特征值的情況（其中的“＋”“－”符號是相對于中間水平直線的）。特別考慮了兩向量間各種特殊位置的情況，這些特殊位置造成了幾何奇異。

根據(jù)定義1和定義2，如果有任一向量與多邊形的邊界向量相交，則相對于該向量，若交點的特征值為-1，就意味從此交點開始，該向量進入多邊形內(nèi)部，稱為“入點”，反之，該向量從此點離開多邊形，稱為“出點”。

圖1 兩向量交點特征值的各種情況

定義3單調(diào)多邊形 一個簡單多邊形關(guān)于某條直線L單調(diào)，如果對任何一條垂直于L的直線L'，L'與多邊形交都是連通的，即它們的交可能是一條線段，或者是一個點，或者是空集。

例如，一個多邊形基于y坐標軸單調(diào)則稱它是y單調(diào)多邊形，它的一個鮮明幾何意義是：從最高頂點沿著多邊形的（左/右）邊界走向最低頂點的過程中，始終是向下（或水平）的，即y坐標值最大和最小兩個頂點可以將它的邊分成兩個單調(diào)邊序列，如圖2所示。

圖2 y單調(diào)多邊形及其三角化

一個單調(diào)多邊形的“最高點”與“最低點”將單調(diào)多邊形分成2個鏈，可以從上至下根據(jù)高度相鄰原則連接兩鏈間的頂點實現(xiàn)可三角化。圖2給出y單調(diào)多邊形的三角化的例子。

一般多邊形不是y單調(diào)的原因是因為存在一些局部y極值點，如果排除這些y極值點，多邊形就成為y單調(diào)的了。既然，最終的目的是將多邊形三角化，因此，如果能在y極值點處將多邊形分割，使形成y極值點的2條邊分屬于兩個多邊形，那么，在新的兩個多邊形中，該y極值點處y坐標就是單調(diào)的了。

2 算法描述

2.1 算法基本原理

本文算法先將一般多邊形分割為y單調(diào)多邊形，再將y單調(diào)多邊形劃分成三角形。所處理的圖形可以有任意個外邊界，每個外邊界可以含有0到多個內(nèi)孔。

一個y極值點（Ymax和Ymin點）與左右相鄰邊界頂點不是單調(diào)的，因此，一個簡單的思想是在y極值點處分割圖形就能達到極值點兩邊的邊界成為y向單調(diào)。本算法的基本原理就是依據(jù)這個原理。先通過一個簡單的例子闡述算法的基本思想。

如圖3所示，圖形含有1個外邊界和2個內(nèi)孔。找出所有邊界中的局部y極值點（Ymax和Ymin點），此圖中外邊界為凸多邊形，只需考慮內(nèi)邊界的y極值點，有2+2個。通過這些y極值點作水平線，一個極值點形成一條水平分割線。一般情況下水平分割線與圖形的邊界有很多交點，用于劃分圖形成y單調(diào)多邊形的分割線的端點由這些交點中離極值點最近的左右2個交點構(gòu)成，這樣分割線就能有效地將圖形劃分的區(qū)域即為y單調(diào)多邊形，如圖3中4條分割線將原多邊形分成7個y單調(diào)多邊形。

圖3 多邊形的y單調(diào)劃分

2.2 y極值點分割線的算法

衡量一個算法的穩(wěn)定性就是看它處理奇異情況的能力，本算法充分利用邊界的方向性及交點特征值可以方便快捷解決這個問題。基本原則是：如果水平分割線與圖形邊界的交點是一個重交點，則利用定義2，把交點特征值代數(shù)和的符號作為重交點特征值的符號，當2個重交點的特征值代數(shù)和不為零時，保留其中一個交點，特征值絕對值仍取為 1，符號不變；2個重交點的特征值代數(shù)和為零時，取消重交點，如圖 4、圖 5所示。

y極值點分割線的算法課簡述如下：

1） 對圖形中每一局部極值點作自左至右的水平向量（該向量的左端點和右端點均需超越整個圖形以保證與所有邊界均能求交）；

2） 求取該分割線向量與圖形各邊界的邊向量的交點及交點相對于該分割線向量的特征值（圖4中標有“○-”、“○+”的交點）；

3） 對所有交點（及其附帶的特征值）自左至右（即按水平方向的x值從小到大）排序；

4） 處理重交點，如果水平分割線通過圖形邊界的頂點（此時2個交點的x值相同，圖4中7、8），就形成重交點。當重交點特征值代數(shù)和不為零時，保留其中一個交點，特征值絕對值仍取為1，符號不變；重交點的特征值代數(shù)和為零時，取消重交點；

5） 處理重邊交點，如果水平分割線與圖形某邊界重合（此時2個交點的x值不相同）就形成重邊交點。此時如果重交點的2個特征值均為“+”，取消后一個重交點（圖4中1、2取1），如果 2個特征值均為“-”，取消前一個重交點（圖4中3、4取4）；

6） 如果有交點，則取y極值點左面最近的“-”特征交點與右面最近的“+”特征交點作為該y極值點分割線的端點。否則，該y極值點分割線不計（圖4中①、②）。

圖4 帶有幾何奇異的圖形

2.3 y單調(diào)多邊形劃分算法

一般多邊形轉(zhuǎn)化成y單調(diào)多邊形的基本原理很簡單，實施卻很復(fù)雜，因為算法將處理含有內(nèi)孔的多邊形，且包含復(fù)雜的奇異狀況。下面的算法將任意的多邊形區(qū)域劃分成若干個y單調(diào)多邊形。算法可分成兩部分：（1）求取分割線；（2）對y單調(diào)多邊形（參閱圖4）。

2.3.1 邊界頂點排序

對多邊形的每一邊界頂點按照定義2排序，邊界前進方向的左側(cè)為內(nèi)部。

2.3.2 求局部極值點

求取所有邊界頂點鉛垂方向的局部極值點（Ymax和Ymin點）（圖4中局部最低頂點以“●”表示，局部最高頂點以“⊙”表示）。

2.3.3 作水平分割線

對每一局部極值點，執(zhí)行“y極值點分割線的算法”。

2.3.4 建立“標記點”

建立下列點作為“標記點”：

1） “節(jié)點點”：將所有負交點（“○-”點）及局部最低頂點（“●”）作“節(jié)點點”標記。從每個節(jié)點點出發(fā)就可搜索到一個 y單調(diào)多邊形，即“節(jié)點點”數(shù)就是劃分的總y單調(diào)多邊形個數(shù)。其中，如果負交點不在任何邊界的頂點上，則需將其插入到所在邊界的頂點隊列中。

2）“上變向點”：將所有正交點（“○+”點）作“上變向點”標記。如果正交點不在任何邊界的頂點上，則需將其插入到所在邊界的頂點隊列。

3） “下變向點”：對所有在分割線上的局部極大點（“⊙”）作標記，記為“下變向點”。即每條分割線段的左端點為“節(jié)點點”，右端點為“上變向點”，位于分割線段上的局部極大點為“下變向點”。

2.3.5 標記點連接關(guān)系

對每一非退化成一個點的分割線段執(zhí)行下列操作：

1） 對每一分割線段，從左至右，對“節(jié)點點”和“上變向點”排序，建立后序關(guān)系。

2） 對每一分割線段，從右至左，對“上變向點”、“下變向點”和“節(jié)點點”排序，建立前序關(guān)系。

2.3.6 執(zhí)行“單調(diào)多邊形構(gòu)建算法”

按照下面流程完成單調(diào)多邊形。

N1【開始一個新節(jié)點】：依次取一“節(jié)點點”，F(xiàn)lag←1，記錄該點為“首點”，并開始一個新節(jié)點。

N2【取下一點】：如果Flag＝1，取下一個“標記點”，否則取下一個“邊界頂點”。

N3【回到首點？】：如果是“首點”，則已找到一個封閉單調(diào)多邊形。對該單調(diào)多邊形做三角化。記錄三角化數(shù)據(jù)，“首點”作已用標記，轉(zhuǎn)N5。

N4【到標記點？】：如果是“標記點”，F(xiàn)lag←1-Flag，轉(zhuǎn) N2。

N5【結(jié)束？】：如果“節(jié)點點”完，則算法結(jié)束，否則轉(zhuǎn)N1。

這樣整個多邊形被分割線分為多個y單調(diào)多邊形。

圖5是水平分割線劃分圖4的結(jié)果。

圖5 通過水平分割線分割以后形成的節(jié)點區(qū)域

3 數(shù)據(jù)結(jié)構(gòu)

算法的數(shù)據(jù)結(jié)構(gòu)包括：多邊形的數(shù)據(jù)結(jié)構(gòu)、劃分節(jié)點水平分割線的數(shù)據(jù)結(jié)構(gòu)、y單調(diào)多邊形的數(shù)據(jù)結(jié)構(gòu)。這里沿用何援軍教授在文獻[10]中定義的3種數(shù)據(jù)結(jié)構(gòu)。

4 算法實例

通過VC6.0開發(fā)工具實現(xiàn)該算法，并運行在XP系統(tǒng)上，對多個任意形狀的多邊形進行測試，如圖6所示，選取具有代表性的4個例子，分別列出水平分割線將原圖形分割之后的結(jié)構(gòu)，以及分割之后對分割出來的y單調(diào)多邊形進行三角化的結(jié)果。

圖 6 三角化例子

由圖6的案例可以看出，該算法采用分割線很好的將任意的多邊形劃分為多個單調(diào)多邊形，從而快速實現(xiàn)三角化，同時對含有島的多邊形也有較好的處理。算法實現(xiàn)的過程稍微復(fù)雜，是因為考慮到在用分割線分割圖形時，水平向量與多邊形相交時的一些奇異情況，但運用交點的特征值，很好的處理了這些奇異情況，并取得較好的效果，因此，具有更廣泛的應(yīng)用價值。另外對原有圖形中重點重邊問題也有一定解決。如圖7所示，圖7(b)中的A點是內(nèi)孔與外邊界的重點，也可以是原圖形的自交點，并且又是局部極值點，對A點處理應(yīng)該有一條水平分割線。圖7(a)中A點同圖7(b)一樣，但該點的性質(zhì)如圖4中的②情況一樣，對此點應(yīng)沒有分割線；但AB又是內(nèi)孔與外邊界的重邊，在進行水平分割線分割之后，形成3個單調(diào)多邊形和AB線段。圖7(c)中的A、B兩點與圖7(a)圖的A點一樣，處理時應(yīng)沒有分割線。

圖 7 對奇異情況的處理

5 總 結(jié)

本文提出的算法可用于帶0個或多個的內(nèi)環(huán)任意平面多邊形區(qū)域的三角化，也可以擴展到含有島的任意多邊形三角化，因此,是一個通用的三角化算法。本算法先對邊界走向進行定義，通過邊界y軸（或x軸）方向的局部極值點的分割線將多邊形從上向下（或是從左到右）進行分割，采用交點的特征值比較徹底地解決了分割時的重點問題，將多邊形區(qū)域準確地劃分成若干個y單調(diào)多邊形（或x單調(diào)多邊形）。本算法原理簡單易實施，適合于任意復(fù)雜的多邊形，因而具有很好的魯棒性。

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

[2]肖忠暉, 盧振榮, 張 謙. 簡單多邊形凸單元剖分的編碼算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報,1996, 8(增刊): 120-127.

[3 ]Kong X S, Everett H, Toussaint G T. The grahams can triangulates simple polygons [J]. Pattern Recognition Letters, 1990, 11(11): 713-716.

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

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

[6]畢 林, 王李管, 陳建宏, 馮興隆. 快速多邊形區(qū)域三角化算法與實現(xiàn)[J]. 計算機應(yīng)用研究, 2008, (10):3030-3033.

[7]陳向平, 應(yīng)道寧. 統(tǒng)一于NIP的多邊形三角剖分算法[J]. 計算機學(xué)報, 1989, 12(3): 194-199.

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

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

[10]何援軍, 孫承山, 曹金勇. 繡花縫針軌跡問題[J].計算機學(xué)報, 2003, 26(9): 1211-1216.