基于貪心算法思想的凸多邊形最優(yōu)三角剖分算法研究

胡剛林 陶敏龍

摘要：當將多邊形分割成互不相交的三角形的弦長之和最小時，稱為最優(yōu)三角剖分。在動態(tài)規(guī)劃算法實現(xiàn)此功能的時間復(fù)雜度O（n3），空間復(fù)雜度O（n2）[1]，采用貪心算法的時間復(fù)雜度是O（n2），空間復(fù)雜度是O（n），算法效率有明顯的提升。貪心算法思想的最優(yōu)剖分算法推廣到三維空間，實現(xiàn)對多面體最優(yōu)三角形椎體的剖分能得到非?，F(xiàn)實的應(yīng)用。

關(guān)鍵詞：最優(yōu)三角剖分；最小三角弦；動態(tài)規(guī)劃算法；貪心算法；最優(yōu)三角形椎體

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）35-8555-02

Research on the Optimal Convex polygons Triangulation Algorithm Based on Greedy Aalgorithm

HU Gang-lin1， TAO Min-long 2

（1. Chongqing College of Humanities Science & Technology， Chongqing 401524， China； 2.Southwest University， Chongqing 400715， China）

Abstract：The optimal triangulation is that the length of the triangle chord is the shortest one which divides the polygon into disjoint triangle. To implement this feature， the time complexity is O （n3）， space complexity is O （n2） in the dynamic programming algorithm. But using the greedy algorithm， the time complexity is O （n2）， space complexity is O （n）. The algorithm efficiency is significantly improved. The greedy optimal split algorithm can be extended to three-dimensional space. The greedy optimal split algorithm of the optimal of split into triangular vertebral body from polyhedron can get very realistic applications.

Key words： the optimal triangulation； the shortest triangle chord； the dynamic programming algorithm； the greedy algorithm； the optimal triangular vertebral body

1 多邊形定義及性質(zhì)

多邊形是平面上一條分段線形閉曲線。也就是說，多邊形是由一系列首尾相接的直線段所組成的。組成多邊形的各個直線段稱為該多邊形的邊。連接多邊形相繼兩條邊的點稱為多邊形的頂點。若多邊形的邊除了連接頂點外沒有別的交點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內(nèi)的所有點構(gòu)成了多邊形的內(nèi)部；多邊形本身構(gòu)成了多邊形的邊界；而平面上其余包圍著多邊形的點構(gòu)成了多邊形的外部。當一個簡單多邊形及其內(nèi)部構(gòu)成閉凸集時，稱該簡單多邊形為一凸多邊形。也就是說，凸多邊形邊界上或內(nèi)部的任意兩點所連成的直線段上所有點均在凸多邊形的內(nèi)部或邊界上。

通常，用多邊形頂點的順時針序列表示凸多邊形，即P={v0，v1，…，vn-1}表示具有n條邊v0 v1，v1 v2，…，vn-1vn的凸多邊形（其中，約定v0=vn）。

若vi與vj是多邊形上不相鄰的兩個定點，則線段vivj稱為多邊形的一條弦。弦vivj將多邊形分割成兩個多邊形{vi ，vi+1，…，vj}和{vj， vj+1，…，vi}。

2 最優(yōu)三角剖分定義及性質(zhì)

多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。各弦互不相交，且集合T已達到最大，即P的任一不在T中的弦必與T中某一弦相交。在有n個頂點的多邊形的三角剖分中，恰好有n-3條弦和n-2個三角形。

凸多邊形的最優(yōu)三角剖分問題：給定凸多邊形P={ v0，v1，…，vn-1}，以及定義在由多邊形的邊和弦組成的三角形的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得該三角剖分所對應(yīng)的權(quán)，即該三角剖分中諸三角形上權(quán)之和最小。

可以定義三角形上各種各樣的權(quán)函數(shù)w。例如，

其中，vivj是點vi到vj的歐氏距離。相應(yīng)于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分[1]，也即弦長之和最小的三角剖分為最優(yōu)三角剖分。

3 最小三角弦定義及性質(zhì)

我們定義凸多邊形的三角弦：具有n條邊v0 v1，v1 v2，…，vn-1vn的凸多邊形，連接任意相鄰的兩個條邊vkvk+1， vk+1vk+2的不相交的兩個頂點vk，vk+2所得線段vkvk+2，則線段vkvk+2稱為凸多邊形的一條三角弦。

n個頂點的凸多邊形三角弦有且僅有n條，即v0v2，v1v3，v2v4，…，vn-3vn-1，vn-2v0，vn-1v1，其中值最小的弦稱為最小三角弦。

如圖1所示，凸七邊形P={v0，v1，v2 ，v3， v4， v5， v6}的七條邊分別是：v0 v1，v1 v2，v2 v3，v3 v4，v4 v5，v5 v6，v6 v0。七條三角弦分別為：v0v2，v1v3，v2v4，v3v5，v4v6，v5v0，v6v1，據(jù)觀察可知最小三角弦為v3v5。

4 基于貪心算法思想的凸多邊形最優(yōu)三角剖分算法

圖 3為凸五邊形切割后不需要更新序列S。

4.1 算法分析

基于貪心算法思想的凸多邊形最優(yōu)三角剖分算法步驟如下， 如圖2所示：

1） 令三角弦初始序列為S={ v0v2，v1v3，v2v4，…，vn-3vn-1，vn-2v0，vn-1v1}，并定義數(shù)組B[n-3]用于存儲最小三角弦，定義i為循環(huán)記數(shù)，i的初始值為1，i值的遞增序列是：1，2，3， …，n-3

2） 取序列S中最小三角弦vkvk+2，并保存此最小三角弦至數(shù)組B[i-1]

3） 切去三角弦vkvk+2所構(gòu)成的三角形vkvk+1vk+2

4） 刪去序列S中的三角弦vk+1vk+3

5） 當i

6） 如果更新后的序列S中元素個數(shù)小于等于1時退出循環(huán)（也即i>=n-3時），否則更新i值（i=i+1），返回到第2步進入下次循環(huán)

5 七邊形最優(yōu)三角剖分算法

如圖4所示，凸七邊形最優(yōu)三角剖分切割成凸六邊形算法的一次循環(huán)步驟如下：

1） 凸七邊形三角弦序列為：S={ v0v2，v1v3，v2v4，v3v5，v4v6，v5v0，v6v1}，并定義數(shù)組B[4]用于存儲最小三角弦，定義i為循環(huán)記數(shù)，設(shè)i的初始值為1，i值的遞增序列是：1，2，3， 4

2） 取序列S中最小三角弦v3v5

3） 切去三角弦v3v5所構(gòu)成的三角形v3v4v5

4） 刪去序列S中的弦v4v6

5） 當i<2時（此時i值為1） ，更新序列S中的三角弦v2v4為v2v5，v3v5為v3v6，否則刪去序列S中的三角弦v2v4，v3v5

6） 更新后的序列S的元素個數(shù)大于3（此時序列S元素個數(shù)為5） ，因此更新i值（i=i+1），返回到第2步進入下次循環(huán)（如果更新后的序列S中元素個數(shù)小于等于1時退出循環(huán)（也即i>=n-3時））

6 算法的復(fù)雜度

在每次循環(huán)中，算法第2步中序列S中元素的個數(shù)依次是：n，n-1，n-2 ，…，6，5，2。因此，經(jīng)過n-3次循環(huán)找最小三角弦，每次比較所需最大比較次數(shù)依次是：n-1，n-2，n-3 ，…，5，4，1，共比較（n+3）（n-4）/2+1次，算法的時間復(fù)雜度是O（n2），空間復(fù)雜度是O（n）。

與動態(tài)規(guī)劃算法的時間復(fù)雜度O（n3），空間復(fù)雜度O（n2）[1]相比有了顯著的提升。

7 問題的進一步拓展

凸多邊形最優(yōu)三角剖分算法是基于二維空間的一種剖分算法，雖然基于貪心算法思想的凸多邊形最優(yōu)三角剖分算法只能得到近似的最優(yōu)值，但是基于貪心算法思想的最優(yōu)剖分算法推廣到三維空間，實現(xiàn)對多面體最優(yōu)三角形椎體的剖分就能得到非?，F(xiàn)實的應(yīng)用，因為采用動態(tài)規(guī)劃算法在多數(shù)情況下要窮舉得到實心的多面體的每個任意剖面面積是比較困難的，因此，采用貪心算法思想實現(xiàn)多面體最優(yōu)三角形椎體的最優(yōu)剖分算法是一種比較現(xiàn)實的選擇。下圖三角形椎體abc為多面體的一個三角形椎體剖分。

參考文獻：

[1] 王曉東.算法設(shè)計與分析[M].2版.北京：清華大學出版社，2008.

[2] 翟仁健.基于邊優(yōu)先的任意多邊形最優(yōu)三角剖分[J].測繪科學，2008（1）.

[3] 李建平.動態(tài)規(guī)劃法解最佳三角剖分凸多邊形問題[J].擂臺賽，2000（18）.