一種快速相容三角剖分算法

摘要：提出了一種基于凹多邊形凸分解的相容三角剖分方法。先將凹邊形分解成凸多邊形，再對子多邊形進行三角剖分，即可實現相容三角剖分。在最壞的情況下添加O（jk)個輔助點，時間復雜度為O(jn+n log n+jk log n)

關鍵詞：相容三角剖分； 多邊形分解； 計算幾何

中圖法分類號：TP391文獻標識碼：A

文章編號：1001－3695(2007)01－0235－03

通常情況下P與Q之間并不總是存在相容三角剖分，為了解決這個問題，需要在多邊形內添加輔助點（Steiner Points）來實現。然而太多的輔助點會影響實際應用中的效率，所以如何使用一種有效的方法添加較少的輔助點而實現相容三角剖分成為一個重要問題。此問題最早由Goodman和Pollack在1989年提出，Aronov，Seidel和Souvaine[1]給出了一種添加O（n2)輔助點，在O(n2)的時間實現相容三角剖分算法。該算法最早解決添加輔助點能否實現相容三角剖分的問題，但是添加O(n2)個輔助點并不適合實際應用。Gupta和Wenger[3]給出了一種算法，結果將添加O（M log n+n log2n)個三角形，其中M為最優情況下產生的三角形個數。在某些不需要添加輔助點的簡單情況下，該算法也將添加大量的輔助點。算法中用到了大量的近二十年才在計算幾何中提出的算法，無法在實際應用中實現。Kranakis和Urrutia[4]給出了兩種不同的相容三角剖分方法，添加的輔助點數取決于多邊形的凹點數：①添加O（(j+k)2)個輔助點（j，k分別為兩個多邊形的凹點數），同樣因為輔助點太多而不適用。②在最壞情況下添加O(jk)個輔助點，但是會在多變形的邊界上添加輔助點，在應用中將受到限制。最近由Surazhsky和Gotsman在文獻[9]中提出了一種新的算法，該算法能添加較少的輔助點而實現相容三角剖分，但是需要耗費大量的時間O(n3log n)。本文提出的算法雖然也要少量的輔助點，但耗時將大大減少。

1算法的提出

1．1凸多邊形和凹多邊形

凸多邊形就是所有內角均小于180°的多邊形，凹多邊形則是內角至少有一個大于180°。圖1（a)是凸多邊形，圖1(b)是凹多邊形。

結論1凹多邊形不添加輔助點的任意三角剖分T，都能在頂點數相同的凸多邊形上實現，反之則不成立。

證明：因為凸多邊形的弦都在多邊形內，所以對于凹多邊形內的任意弦，凸多邊形內都有相應的弦；反之凸多邊形內的某條弦，將可能在相應的凹多邊形外。故結論成立。其實現如圖2所示。

如果兩個多邊形有一個為凸多邊形，則可以非常方便地實現無須插入輔助點的相容三角剖分；如果兩個多邊形都是凹多邊形，則只需要將其中一個分解為凸多邊形，另外一個也作相同的剖分，再對子多邊形進行三角剖分即可實現兩個多邊形的相容三角剖分。

1．2凹多邊形的凸分解

在文獻[12]中實現了一種基于頂點可見性的凹多邊形凸分解算法，但是在某些情況下需要在邊界添加輔助點。此處對算法進行改進，實現無需輔助點的凹多邊形凸分解，時間復雜 度不變。應用在相容三角剖分時需要改動剖分規則，才能添加最少的輔助點。

凹多邊形凸分解的關鍵就是對凹點進行凸分解，得到的子多邊形則都是凸多邊形。如圖3所示，對于多邊形P內某個凹點vi，設M為由vi出發，與有向線段vi-1，vi方向一致的射線；N為由vi出發，與有向線段vi+1，vi方向一致的射線，M和N所在直線將平面分為A，B，C，D四個區域。利用文獻[14]提出的可見點快速搜索算法求出視點vi的可見點串ST=(s0，s1，…，sj)，注意ST中的點并不都是P的頂點。顯然，ST中的點只可能在區域A，B，C中，并且在這三個區域中的點形成的點串在ST中是連續分布的，分別用SA，SB，SC表示這三個點串，將會出現兩種情況：圖3中，扇形區域A(不包括射線M和N)存在vi的可見點串SA；圖4中，區域A不存在vi的可見點串SA。對于圖4的情況只有一種剖分方法，在SB中選取離sk最近（小標順序）的點sb，在SC中選取離sk+1最近的點sa，然后分別連接sbvi和savi，即可剖分凹點vi；對于圖3的情況，只需要一條剖分線即可剖分凹點。但是為了達到最少輔助點的效果，需作如下選擇：

（1）當SA中有多個凹點，并且如果vi也同時位于其中某幾個凹點的區域A中，則將這些凹點放入集合SP中；

（2）否則，將SA中的所有可見點放入集合SP中；

（3）如果集合SP中的頂點只有一個，則將其作為選中的點；否則，設vj∈SP，在另一多邊形Q中找到與vi和vj相對應的點ui和uj，計算ui與uj之間的最短路徑。兩點間的最短路徑就是在多邊形內，兩點以最少的直線段能連接的路徑。本文采用的求最短路徑的方法是Suri[10]提出的算法，取uj中與ui路徑最短的點為剖分點，這樣可以添加最少的輔助點，若路徑最短的點不止一個，則選其中uj=arg max min(j-i，i-j+n)，即盡可能地均勻剖分多邊形P和Q。

圖5是上述方法剖分凹多邊形的一個示例。目標多邊形P被剖分成幾個凸多邊形，并在Q上作相應剖分，x0是剖分過程中添加的輔助點。用以上凹多邊形凸分解的方法來剖分多邊形P和Q，可以得出以下結論：

結論2凹多邊形凸分解后得到的子多邊形頂點數都不超過n。

證明：由條件可知對多邊形P作凸分解，在Q上作相容剖分后得到的子多邊形的頂點數與P中相應多邊形頂點數一樣，所以只要證明其中一個子多邊形頂點數不超過n即可。對多邊形Q內任意兩點引剖分線，所插入的剖分線是由多邊形內兩點間最短路徑得到的。該兩點沿Q的頂點也存在能相連的兩條路徑，且每條路徑的頂點數均不少于剖分線的點數。剖分線上的輔助點分別與多邊形上兩點之間的頂點構成兩個子多邊形的頂點。所以Q剖分而成的兩個子多邊形的頂點數都不大于Q的頂點數，亦可推出多邊形Q的所有子多邊形的頂點數都不超過n。

結論3Q內任意兩點間的最短路徑不超過min(n/2，k)。證明與結論2類似。

結論4添加的輔助點數目不超過2j×min(n/2，k)，即min(jn，2jk)，最多需要在多邊形內引2j條剖分線，加之結論3得出此結論。

結論5子多邊形的頂點總數不超過n+4j+min(2jn，4jk)。

證明：每添加一條剖分線后得到的子多邊形頂點總數最多增加2+2min(n/2，k)，所以最多2j條剖分線剖分后的子多邊形的頂點總數不超過n+2j×(2+2min(n/2，k))，即n+4j+min(2jn，4jk)。

雖然在原算法上進行了部分改動，但是此處凹多邊形凸分解的時間復雜度依然為O(jn)。

1.3任意多邊形三角剖分

余下只要對Q中幾個子多邊形進行三角剖分，所得到的就是多邊形P和Q的相容三角剖分了。本文采用文獻[8]中提出的掃描線算法（Sweepline Algorithm）剖分多邊形，剖分一個頂點數為n的凹多邊形所需時間為O(n log n)。圖6是對多邊形Q的子多邊形用掃描線算法進行三角剖分得到的結果。圖7是對多邊形P和Q進行相容三角剖分最終得到的結果。

2算法分析

從結果可以看出，本文所提出的算法兼顧輔助點數和運算時間，而且其中所涉及到的算法都是目前已經實現且相當成熟的，很適合在實際工程中應用。凸多邊形具有很多良好的性質，很適合在參數化映射方面進行應用，這也是筆者以后的研究方向。

參考文獻：

［1］B Aronov， R Seidel， D L Souvaine. On Compatible Triangulations of Simple Polygons[J]. Computational Geometry: Theory and Applications，1993，3(1):2735.

［2］M S Floater. Parameterization and Smooth Approximation of Surface Triangulation[J].Computer Aided Geometric Design，1997，14(3):231250.

［3］H Gupta， R Wenger. Constructing Piecewise Linear Homeomorphisms of Simple Polygons[J]. J. Algorithms， 1997，22(1):142157.

［4］E Kranakis， J Urrutia. Isomorphic Triangulations with Small Number of Steiner Points[J]. International Journal of Computational Geometry and Applications， 1999，9(2):171180.

［5］Chazelle B， Dobkin P D. Optimal Convex Decompositions[A]. Toussaint Godfried. Computational Geometry[M]. Amsterdam， Holland: North Holland，1985.63133.

［6］M Alexa， D CohenOr， D Levin. Asrigidaspossible Shape Interpolation[C]. Proceedings of SIGGRAPH， 2000.157164.

［7］V Surazhsky， C Gotsman. Controllable Morphing of Compatible Planar Triangulations[J]. ACM Transactions on Graphics， 2001， 20(4):203231.

［8］M R Garey，D S Johnson， F P Preparata，et al. Triangulating a Simple Polygon [J]. Inform.Process.Lett.，1978，7(4):175179.

［9］Vitaly Surazhsky， Craig Gotsman. High Quality Compatible Triangulations[J].Engineering with Computers， 20-04， 20(2):147156.

［10］S Suri. On Some Link Distance Problems in a Simple Polygon[J]. IEEE Journal of Robotics and Automation， 1990， 6(1):108113.

［11］肖忠暉， 盧振榮， 張謙. 簡單多邊形凸單元剖分的編碼算法[J]. 計算機學報， 1996，19(6):477481.

［12］金文華，饒上榮，等. 基于頂點可見性的凹多邊形快速凸分解算法[J].計算機研究與發展，1999，36(12):14551460.

［13］Zhou Peide. An Algorithm for Partitioning Polygons into Convex Parts[J]. Journal of Beijing Institute of Technology，1997，6(4):363368.

［14］金文華， 何濤， 唐衛清，等. 簡單多邊形可見點問題的快速求解算法[J]. 計算機學報， 1999，22(3): 275282.

［15］Keil M. Decomposing Polygons into Simpler Components[D]. University of Toronto， 1983.

［16］Schachter B. Decomposition of Polygons into Convex Sets[J]. IEEE Trans. on Computers， 1978， C27(11):10781082.

［17］MS Floater， C Gotsman. How to Morph Tilings Injectively[J]. Journal of Computational and Applied Mathematics， 1999，101（12）:117129.

［18］M L Staten， S A Canann， S J Owen. BMSweep: Locating Interior Nodes During Sweeping[C]. The 7th International Meshing Round￣table，1998.718.

［19］T W Sederberg， P Gao， G Wang， et al. 2D Shape Blending: An Intrinsic Solution to the Vertex Path Problem [C]. Computer Graphics (SIGGRAPH’93)， 1993.1518.

作者簡介：

劉海濤（1983），男，湖北黃陂人，碩士研究生，主要研究方向為計算機圖形學、制造企業信息化；

張三元(1963)，男，教授，主要研究方向為計算機輔助設計和圖形學、曲面造型、虛擬現實和圖像處理；

葉修梓（1966），男，教育部長江學者獎勵計劃特聘教授，博導，主要研究方向為CAD/CAM、計算機圖形／圖像技術、數據庫技術。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文