平面點(diǎn)集Delaunay三角剖分的分治算法

謝增廣

（華北計(jì)算技術(shù)研究所，北京100083）

0 引 言

三角剖分是計(jì)算幾何中領(lǐng)域的重要課題之一。平面點(diǎn)集Delaunay三角剖分與該點(diǎn)集的Voronoi圖是對(duì)偶圖，具有許多優(yōu)良性質(zhì)，在圖形網(wǎng)格化技術(shù)領(lǐng)域有著廣泛應(yīng)用。三角剖分算法理論研究已經(jīng)相當(dāng)成熟，已經(jīng)能夠證明算法時(shí)間復(fù)雜度的上界和下界［1］，然而由于區(qū)域拓?fù)鋭澐謫?wèn)題，算法在實(shí)際工程中應(yīng)用的難易程度有所不同。根據(jù)實(shí)現(xiàn)過(guò)程，Delaunay三角剖分的算法可以分為逐點(diǎn)插入法、三角網(wǎng)生長(zhǎng)法，分治算法等，其中分治算法最適合實(shí)際工程應(yīng)用。

論文引入了一種數(shù)據(jù)結(jié)構(gòu)——雙鏈接邊表 （doublyconnected edge list，DCEL），利用該數(shù)據(jù)結(jié)構(gòu)可以方便地對(duì)平面區(qū)域進(jìn)行劃分；引入了3個(gè)工具算法，簡(jiǎn)化了Delaunay三角剖分算法分治的實(shí)現(xiàn)過(guò)程；另外對(duì)特殊退化情況進(jìn)行分類(lèi)處理，增強(qiáng)了該算法的實(shí)用性。

1 算法設(shè)計(jì)與實(shí)現(xiàn)

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

雙鏈接 邊 表 （doubly－connected edge，DCEL）［4－5］是 用來(lái)表示平面圖拓?fù)湫畔⒌囊环N數(shù)據(jù)結(jié)構(gòu)，如圖1所示。

在DCEL中，將每條邊的兩端分別作為一條半邊。半邊有方向性，由起點(diǎn)出發(fā)，指向另一個(gè)端點(diǎn)。一條邊的兩條半邊互為孿生半邊。

DCEL由三組記錄構(gòu)成，分別存儲(chǔ)頂點(diǎn)、面、半邊的信息。

（1）在頂點(diǎn)V的記錄中，除了存儲(chǔ)點(diǎn)的坐標(biāo)信息，還有一個(gè)指向半邊的指針，指向以V為起點(diǎn)的某一條半邊。

（2）在面f的記錄中，只存儲(chǔ)了一個(gè)指向半邊的指針，指向該面邊界上的某一條半邊。

圖1 DCEL數(shù)據(jù)結(jié)構(gòu)

（3）在半邊edge的記錄中，存儲(chǔ)了半邊的起點(diǎn)，一個(gè)半邊的指針指向其孿生半邊，一個(gè)面指針指向位于半邊左側(cè)的面face。此外還有2個(gè)半邊指針，分別指向沿著face邊界方向的前一條半邊和后一條半邊。

根據(jù)DCEL提供的信息，可以很方便地對(duì)平面進(jìn)行子區(qū)域劃分。為了簡(jiǎn)化分治Delauany三角剖分算法實(shí)現(xiàn)過(guò)程，不必存儲(chǔ)面的信息。

1.2 預(yù)備工具算法

介紹分治Delauany三角剖分算法之前，先引入3個(gè)預(yù)備工具算法：判斷點(diǎn)是否在指定三點(diǎn)外接圓內(nèi)，判斷夾角不大于π，求不相交的2個(gè)凸多邊形的上下公切線。

1.2.1 判斷點(diǎn)是否在指定三角形的外接圓內(nèi)

設(shè)不共線三點(diǎn)a，b，c構(gòu)成的三角形記作△ （a，b，c），點(diǎn)的d｛a，b，c｝。判斷d是否在△ （a，b，c）外接圓內(nèi)的方法是［6］：記ret＝，ret＜0，d在△ （a，b，c）外接圓外部；ret＝0，d在△ （a，b，c）外接圓邊界上；ret＞0，d在△ （a，b，c）外接圓內(nèi)部。

定義操作inCircle（a，b，c，d），如果d在a，b，c確定的三角形外接圓內(nèi)，返回TRUE；否則，返回FALSE。顯然地，inCircle（a，b，c，d）的時(shí)間復(fù)雜度為O （1）。

1.2.2 判斷夾角不大于π

設(shè)不共線三點(diǎn)為a，b，c，記逆時(shí)針?lè)较驃A角∠abc為θ，θ與π大小關(guān)系判斷方法是［6］：記ret＝，假定人沿著方向行走，如果c在其左側(cè)，ret＞0，θ＜π；如果c在其右側(cè)，ret＜0，θ＞π；如果c在方向上，ret＝0，θ＝π。

1.2.3 求不相交的2個(gè)凸多邊形的上下公切線

設(shè)左邊的凸多邊形為L(zhǎng)P，右邊的凸多邊形為RP，如圖2所示。記L為L(zhǎng)P邊界上的最右邊的頂點(diǎn)，R為RP邊界上的最左邊的頂點(diǎn)；記LP和RP的上公切線是tct（top common tangent），TL在LP的邊界上，為tct的左端點(diǎn)，TR在RP的邊界上，為tct的右端點(diǎn)；記LP和RP的下公切線是bct（bottom common tangent），BL在LP的邊界上，為bct的左端點(diǎn)，BR在RP的邊界上，為bct的右端點(diǎn)。為上公切線，當(dāng)且僅當(dāng)LP邊界上的點(diǎn)和RP邊界上的點(diǎn)均不在的左側(cè)；同理，為下公切線，當(dāng)且僅當(dāng)LP邊界上的點(diǎn)和RP邊界上的點(diǎn)均在的左側(cè)。

圖2 求2個(gè)不相交凸多邊形的上下公切線

為了更好地說(shuō)明該算法，設(shè)點(diǎn)V為凸多邊形P邊界上的一點(diǎn)，定義下面2個(gè)操作：①ccw （V，P），V沿著P邊界逆時(shí)針?lè)较蛞苿?dòng)到達(dá)的第一個(gè)點(diǎn)；②cw （V，P），V沿著P邊界順時(shí)針?lè)较蛞苿?dòng)到達(dá)的第一個(gè)點(diǎn)。

zig－zag算法

輸入：左側(cè)凸多邊形LP，右側(cè)凸多邊形RP。LP和RP不相交。

輸出：LP和RP的上下公切線。

Begin

步驟1 L為L(zhǎng)P邊界上的最左點(diǎn)，R為RP邊界上的最右點(diǎn)。L1＝L，R1＝R，L2＝L，R2＝R。

步驟2 若toLeft（L1，R1，cw （R1，RP））為真，R1＝cw （R1，RP）；若toLeft（L1，R1，ccw （L1，LP））為真，L1＝ccw （L1，LP）。迭代這一過(guò)程，直至LP邊界上的點(diǎn)和RP邊界上的點(diǎn)均不在的左側(cè)。

步驟3 若toLeft（L2，R2，ccw （R2，RP））為假，R2＝ccw （R2，RP）；若toLeft （L2，R2，cw （L2，LP））為假，L2＝cw （L2，LP）；迭代這一過(guò)程，直至LP邊界上的點(diǎn)和RP邊界上的點(diǎn)均在的左側(cè)。

End

zig－zag算法執(zhí)行的次數(shù)只與LP的右半邊界上的點(diǎn)和RP的左半邊界上的點(diǎn)規(guī)模有關(guān)。設(shè)點(diǎn)集規(guī)模為N，zigzags算法時(shí)間復(fù)雜度不超過(guò)O （N）。

定義操作zig－zag（LP，RP），得到LP和RP的上公切線為tct，下公切線為bct。

1.3 分治Delauany三角剖分算法

分治Delauany三角剖分算法的基本步驟如下：

（1）點(diǎn)集初始化：將點(diǎn)集以橫坐標(biāo)為主，縱坐標(biāo)為輔按升序排序。

（2）將點(diǎn)集劃分為近似相等的兩個(gè)子點(diǎn)集。

（3）分別對(duì)兩個(gè)子點(diǎn)集進(jìn)行Delauany三角剖分。

（4）合并兩個(gè)子點(diǎn)集的Delauany三角網(wǎng)。

（5）遞歸執(zhí)行步驟 （2）到步驟 （4），直至點(diǎn)集的所有點(diǎn)都參加了Delauany三角網(wǎng)的構(gòu)造。

由排序算法時(shí)間復(fù)雜度可知，點(diǎn)集初始化算法時(shí)間復(fù)雜度為O （N＊logN）。點(diǎn)集初始化之后，將點(diǎn)集合劃分，直至每個(gè)子點(diǎn)集合的規(guī)模不超過(guò)3個(gè)；對(duì)這些子點(diǎn)集三角化，得到點(diǎn)、線段或者三角形，如圖3所示。

圖3 點(diǎn)集初始化和點(diǎn)集合劃分

點(diǎn)集初始化后，設(shè)點(diǎn)集存儲(chǔ)為數(shù)組P［］。定義以下2個(gè)操作：

（1）Merge （LDT，RDT）：LDT 為 左 側(cè) 子 點(diǎn) 集Delauany三角剖分后得到的結(jié)果，RDT為右側(cè)子點(diǎn)集Delauany三角剖分后得到的結(jié)果，Merge是合并操作。該操作返回合并LDT和RDT之后得到的Delauany三角剖分后的結(jié)果DT。合并是分治Delauany三角剖分算法的核心，會(huì)在下一節(jié)合詳細(xì)闡述。

（2）Delauany＿Triangulate（start，end）：start為點(diǎn)集的起始點(diǎn)編號(hào)，end為點(diǎn)集的終結(jié)點(diǎn)編號(hào)，Delauany＿Triangulate是分治操作。該操作將點(diǎn)集劃分為若干子點(diǎn)集，使得每個(gè)子點(diǎn)集的數(shù)量不超過(guò)3個(gè)，并對(duì)子點(diǎn)集進(jìn)行三角化；對(duì)相鄰的點(diǎn)集構(gòu)成的簡(jiǎn)單凸多邊形迭代地進(jìn)行Merge操作合并，直至得到點(diǎn)集的Delauany三角剖分的結(jié)果。該操作返回點(diǎn)集的Delauany三角剖分的結(jié)果，設(shè)為DT。

分治算法偽代碼如下：

Delauany＿Triangulate（start，end）

｛

if（1＝＝end－start＋1）//只有1個(gè)點(diǎn)

｛

將Pstart放入DT，return DT；

｝

else if（2＝＝end－start＋1）//只有2個(gè)點(diǎn)

｛

｝

esle if（3＝＝end－start＋1）//只有3個(gè)點(diǎn) （3點(diǎn)共線為退化情況，暫不考慮）

｛

｝

else //多于3個(gè)點(diǎn)，進(jìn)行分治

｛

mid＝ （start＋end）/2；

//LDT表示左邊點(diǎn)子集Delauany＿Triangulate后得到的結(jié)果

LDT＝ Delauany＿Triangulate（start，mid）；

//RDT表示右邊點(diǎn)子集Delauany＿Triangulate后得到的結(jié)果

RDT＝ Delauany＿Triangulate（mid＋1，end）；

//合并LDT和RDT，得到結(jié)果DT

DT＝ Merge（LDT，RDT）；

｝

return DT；

｝

1.3.1 合并算法

設(shè)DT是合并LDT和RDT的結(jié)果。如圖4所示，DT中的邊分為3類(lèi)：

（1）LL－edge：在Delauany三角剖分左子點(diǎn)集結(jié)束得到LDT時(shí)，LL－edge已經(jīng)被創(chuàng)建，且LL－edge∈LDT；顯然的，LL－edge的兩個(gè)端點(diǎn) ∈LDT。

（2）RR－edge：在Delauany三角剖分右子點(diǎn)集結(jié)束得到RDT時(shí)，RR－edge已經(jīng)被創(chuàng)建，且RR－edge∈RDT；顯然的，RR－edge的兩個(gè)端點(diǎn)∈RDT。

（3）LR－edge：LL－edge是在合并LDT和 RDT過(guò)程中被新創(chuàng)建的，且LR－edge∈DT；在DT中，LR－edge是Delauany邊；在創(chuàng)建LR－edge之前，LR－edge的左端點(diǎn) ∈LDT，LR－edge的右端點(diǎn)∈RDT。

在合并過(guò)程中，由于創(chuàng)建LR－edge，可能會(huì)刪除若干LL－edge和 RR－edge，且已經(jīng)刪除的 LL－edge或 RR－edge不會(huì)再生成；合并過(guò)程中，不會(huì)創(chuàng)建新的LL－edge和RR－edge。

對(duì)圖3中劃分的點(diǎn)集合進(jìn)行合并，得到圖4。由于劃分的各個(gè)子點(diǎn)集三角化后，得到最簡(jiǎn)單的凸多邊形 （點(diǎn)，線段，三角形），此次合并并沒(méi)有刪除LL－edge和RR－edge。

圖4 合并后的邊分為L(zhǎng)L－edge，RR－edge，LR－Edge

為了詳細(xì)闡述合并算法且不失一般性，下面對(duì)圖4的左子點(diǎn)集Delauany三角剖分和右子點(diǎn)集Delauany三角剖分進(jìn)行合并。

合并算法初始化時(shí)記DT＝LDT∪RDT。Delauany三角剖分得到的閉合邊界就是點(diǎn)集構(gòu)成的凸包，因此LDT和RDT的上下公切線在DT中。

記下公切線形成的LR－edge為Base LR－edge，上公切線形成的LR－edge為Roof LR－edge，如圖5所示。

圖5 合并初始化，Base LR－Edge和Roof LR－edge

合并算法的核心是從Base LR－edge向上搜索LR－edge，將其加入到DT中，直至到達(dá)Roof LR－edge為止。在這一過(guò)程 中，可能使 LL－edge或 RR－edge不 再 是 DT 中 的Delauany邊，因此這樣的LL－edge或RR－edge需要從DT中刪除。

為了闡述合并算法，記DT為平面點(diǎn)集的Delauany三角剖分，定義以下5個(gè)操作：

根據(jù)DCEL數(shù)據(jù)結(jié)構(gòu)的特性，以上5個(gè)操作可以在O（1）時(shí)間完成。

記New LR－edge的左端點(diǎn)為L(zhǎng)，右端點(diǎn)為R。初始化時(shí)，L為下公切線的左端點(diǎn)，R為下公切線的右端點(diǎn)。New LR－edge從Base LR－edge開(kāi)始向上尋找下一個(gè)LR－edge，記為Next LR－edge。Next LR－edge的一個(gè)端點(diǎn)是L或R，另一個(gè)端點(diǎn)記為V。因此根據(jù)LR－edge定義，只需要確定端點(diǎn) V （VNew LR－edge），就可以確定Next LR－edge。

可以證明，V是L或R的鄰點(diǎn)。所謂L的鄰點(diǎn)，也稱(chēng)作LDT關(guān)于L的候選點(diǎn)，是指該點(diǎn)和L為端點(diǎn)的線段是LL－edge；同理，所謂R的鄰點(diǎn)，也稱(chēng)作RDT關(guān)于R的候選點(diǎn)，是指該點(diǎn)和R為端點(diǎn)的線段是RR－edge。否則，如果V不是L或R的鄰點(diǎn)，則New LR－edge會(huì)與LL－edge，或RR－edge，或其它的LR－edge相交，這不符合三角剖分的基本性質(zhì)。

為了進(jìn)一步確定V的搜索范圍，V只能在2個(gè)點(diǎn)之間選擇，一個(gè)是L的某個(gè)鄰點(diǎn)，也稱(chēng)為L(zhǎng)DT關(guān)于L的最終候選點(diǎn) （final candidate）；另一個(gè)是R的某個(gè)鄰點(diǎn)，也稱(chēng)為RDT關(guān)于R的最終候選點(diǎn)。

1.3.2 選取候選點(diǎn)

為了詳細(xì)闡述尋找V的過(guò)程且不失一般性，先尋找RDT中關(guān)于R的最終候選點(diǎn)。記RDT中關(guān)于R的第一潛在候選點(diǎn) （first potential candidate）R1，R1是R鄰點(diǎn)Ri中與線段以R為軸點(diǎn)順時(shí)針?lè)较驑?gòu)成夾角∠LRRi最小的點(diǎn)；記RDT中關(guān)于R的次潛在候選點(diǎn) （next potential candidate）R2，R2是R鄰點(diǎn)Ri中與線段以R為軸點(diǎn)順時(shí)針?lè)较驑?gòu)成夾角∠LRRi次小的點(diǎn)。如圖6所示。

第一潛在候選點(diǎn)是否是最終候選點(diǎn)，需要經(jīng)過(guò)以下2條判定規(guī)則檢驗(yàn)：

（1）向上搜索判定：第一潛在候選點(diǎn)R1與邊順時(shí)針?lè)较驃A角∠LRRi＜π。向上搜索判定保證尋找LR－edge的過(guò)程是從下公切線逐點(diǎn)向上，直至到達(dá)上公切線為止。

圖6 RDT關(guān)于R的最終候選點(diǎn)的選取

（2）外接圓判定：由第一潛在候選點(diǎn)R1，New LR－edge的左右端點(diǎn)L，R三點(diǎn)確定的外接圓不包含次級(jí)潛在候選點(diǎn)R2。外接圓判定保證Delaunay剖分的正確性。

如果 （1）和 （2）都滿足，則R1是RDT關(guān)于R的最終候選點(diǎn)；如果 （1）不滿足，則搜索LR－edge過(guò)程已經(jīng)達(dá)到了Roof LR－edge的右端點(diǎn)，RDT中關(guān)于R的候選點(diǎn)不必考慮，即沒(méi)有可以選擇的候選點(diǎn)；如果 （1）滿足，而 （2）不滿足，則從DT中刪除線段所表示的 RR－edge，R1＝R2，即次潛在候選點(diǎn)作為第一候選點(diǎn)，迭代這一處理過(guò)程直至找到最終候選點(diǎn)或者沒(méi)有可以選擇的候選點(diǎn)結(jié)束，如圖6所示。尋找RDT候選點(diǎn)的算法描述如下：

Begin

步驟1 R1＝cw＿rotate（R，L，RDT），若toLeft（L，R，R1）為真，執(zhí)行步驟2；否則執(zhí)行步驟3。

步驟2 R2＝cw＿rotate（R，R1，RDT），若inCircle（L，R，R1，R2）為真為RR－edge，需要從DT中刪除，delete＿RR （R，R1，DT），R1＝R2，R2＝cw＿rotate（R，R1，RDT）；迭代這一過(guò)程，直至inCircle （L，R，R1，R2）為假。R1是RDT最終候選點(diǎn)。

步驟3 RDT中沒(méi)有候選點(diǎn)

End

同理，鏡像地可得到LDT中關(guān)于L的最終候選點(diǎn)，如圖7所示。

圖7 找到LDT關(guān)于L的最終候選點(diǎn)

尋找LDT候選點(diǎn)的算法描述如下：

Begin

步驟1 L1＝ccw＿rotate（L，R，LDT），若toLeft（L，R，L1）為真，執(zhí)行步驟2；否則執(zhí)行步驟3。

步驟2 L2＝ccw＿rotate（L，L1，LDT），若inCircle（L，R，L1，L2）為真，為L(zhǎng)L－edge，需要從DT中刪除，delete＿LL （L，L1，DT），L1＝L2，L2＝ccw＿rotate（L，L1，LDT）；迭代這一過(guò)程，直至inCircle（L，R，L1，L2）為假。L1是LDT最終候選點(diǎn)。

步驟3 LDT中沒(méi)有候選點(diǎn)

End

1.3.3 確定LR－edge

根據(jù)LDT關(guān)于L的最終候選點(diǎn)和RDT中關(guān)于R的最終候選點(diǎn)的存在性，分以下4種情況確定LR－edge：

（1）如果RDT中關(guān)于R沒(méi)有可以選擇的候選點(diǎn)，且LDT中關(guān)于L沒(méi)有可以選擇的候選點(diǎn)，則線段表示的LR－edge為Roof LR－edge，合并過(guò)程結(jié)束。

（2）如果RDT中關(guān)于R的最終候選點(diǎn)是R1，且LDT中關(guān)于L沒(méi)有可以選擇的候選點(diǎn)，則V＝R1，邊是LR－edge，需要加入到DT中。

（3）如果RDT中關(guān)于R沒(méi)有可以選擇的候選點(diǎn)，且LDT中關(guān)于L的最終候選點(diǎn)是L1，則V＝L1，邊是LR－edge，需要加入到DT中。

（4）如果RDT中關(guān)于R的最終候選點(diǎn)是R1，且LDT中關(guān)于L的最終候選點(diǎn)是L1，則需要對(duì)L，R，L1，R1這4個(gè)點(diǎn)進(jìn)行Delaunay三角形測(cè)試，如圖8所示。如果L1在△ （L，R，R1）外接圓的外部，則 V＝L1，邊是LR－edge，需要加入到DT中；否則 V＝R1，邊是LR－edge，需要加入到DT中。

由此LR－edge向上尋找下一個(gè)LR－edge，迭代上述合并處理流程，在到達(dá)Roof LR－edge時(shí)合并結(jié)束，得到點(diǎn)集的Delauany三角剖分，如圖9所示。

1.3.4 合并算法偽代碼及算法復(fù)雜度分析

綜上所述，合并算法偽代碼如下：

Merge（LDT，RDT）

｛

DT＝LDT∪RDT；//初始化操作

zig－zag （LDT，RDT）得上公切線Roof＿LR－edge，下公切線Base＿LR－edge；

點(diǎn)L＝Base＿LR－edge的左端點(diǎn)，點(diǎn)R＝Base＿LR－edge的右端點(diǎn)；

insert＿LR （L，R，DT）；//將Base＿LR－edge加入到DT中

while（不是 Roof＿LR－edge）//向上搜索LR－edge，在到達(dá)Roof＿LR－edge時(shí)終止

｛

分別尋找LDT和RDT候選點(diǎn)L1，R1；

根據(jù)左右候選點(diǎn)L1，R1的存在性確定新的LR－edge并刪除無(wú)效的LR－edge，搜索向上進(jìn)一步；

｝//end while

Merge結(jié)束，得到得到點(diǎn)集的Delauany三角剖分，return DT；

｝

Merge算法的執(zhí)行分為以下3種操作：

（1）Merge初始化。用zig－zag算法尋找上下公切線，算法復(fù)雜度不超過(guò)O （N）。

（2）刪除LL－edge或RR－edge。在搜索LR－edge過(guò)程中刪除的LL－edge或RR－edge的數(shù)量為常數(shù)。

（3）加入LR－edge。Merge生成 LR－edge的過(guò)程與zigzag類(lèi)似。記點(diǎn)集U＝左Delauany三角剖分右邊界上的點(diǎn)∪右Delauany三角剖分的左邊界上的點(diǎn)。U的規(guī)模不超過(guò)N，而建立LR－edge的次數(shù)與點(diǎn)集U的規(guī)模是線性關(guān)系，所以加入LR－edge的次數(shù)不超過(guò)N。

綜上所述，Merge算法的時(shí)間復(fù)雜度為O （N），分治的復(fù)雜度為O（1）。設(shè)分治Delauany三角剖分算法的總的時(shí)間復(fù)雜度為T(mén) （N），則T （N）＝2T （N/2）＋O （N）。根據(jù)主定理［9］，分治Delaunay三角剖分算法的時(shí)間復(fù)雜度為O （N＊LogN）。

1.3.5 退化情況處理

一般地，退化情況在邊界值判斷時(shí)候出現(xiàn)。

（1）對(duì)于toLeft（A，B，C）操作，A，B，C三點(diǎn)共線是退化情況。為此，增加一個(gè)判斷共線的操作coLine（A，B，C）操作。在點(diǎn)集合劃分子點(diǎn)集時(shí)，如果子點(diǎn)集的規(guī)模是3，且這三點(diǎn)共線，則此子點(diǎn)集三角化應(yīng)該得到2條邊。在此基礎(chǔ)上，三點(diǎn)共線的退化情況不會(huì)影響算法的正確性。

（2）對(duì)于inCircle（A，B，C，D）操作，A，B，C，D四點(diǎn)共圓是退化情況。在合并過(guò)程中，四點(diǎn)共圓形的退化情況不會(huì)影響整個(gè)算法的正確性。

2 實(shí)驗(yàn)與結(jié)果分析

針對(duì)不同點(diǎn)集規(guī)模，每個(gè)數(shù)量級(jí)進(jìn)行5次運(yùn)算，算法運(yùn)行的平均時(shí)間見(jiàn)表1，根據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行曲線擬合如圖10所示。

表1 實(shí)驗(yàn)結(jié)果數(shù)據(jù)

圖10 時(shí)間復(fù)雜度曲線擬合

頂部實(shí)線表示由公式0.0005＊ N＊LOG （N）得到的曲線，而虛線表示實(shí)際中測(cè)得的平均運(yùn)行時(shí)間。從圖中實(shí)際數(shù)據(jù)擬合曲線與標(biāo)準(zhǔn)曲線的接近程度，表明程序運(yùn)行時(shí)間的變化規(guī)律符合O （N＊logN）這一趨勢(shì)，與算法的復(fù)雜度為O （N＊logN）的理論結(jié)果相一致。

中間的實(shí)線是經(jīng)典分治算法實(shí)驗(yàn)者測(cè)得的平均運(yùn)行時(shí)間。因?yàn)椴捎昧藌ig－zag算法，簡(jiǎn)化了求不想交凸多邊形上下公切線的過(guò)程，并且DCEL數(shù)據(jù)結(jié)構(gòu)特性使合并算法中的若干操作都是O （1），從而整個(gè)算法的效率較經(jīng)典算法提升了約5%。

3 結(jié)束語(yǔ)

本文使用DCEL數(shù)據(jù)結(jié)構(gòu)表示平面點(diǎn)集Delaunay三角剖分的結(jié)果；闡述了分治Delaunay三角剖分算法，并利用zig－zag算法尋找不相交凸包上下公切線簡(jiǎn)化了算法的實(shí)現(xiàn)。并且對(duì)退化情況進(jìn)行分類(lèi)處理，增強(qiáng)了算法的實(shí)用性。

在實(shí)際工程中，Delauany三角剖分的模型會(huì)更復(fù)雜，實(shí)現(xiàn)難度大，其中具有代表性的模型有平面點(diǎn)集含特征約束的Delauany三角剖分和三維空間的Delauany三角剖分，值得進(jìn)一步深入研究。

由于DCEL數(shù)據(jù)結(jié)構(gòu)不僅能有效地對(duì)平面點(diǎn)集進(jìn)行子區(qū)域劃分，而且可以存儲(chǔ)三維空間的拓?fù)湫畔?，本論文為?fù)雜的問(wèn)題模型研究與實(shí)際應(yīng)用奠定了基礎(chǔ)。

［1］Mark de Berg，Otfried Cheong，Marc van Kreveld，et al，Computational Geometry：Algorithm and Applications ［M］.3rd ed.DENG Junhui，transl.New York：Springer－Verlag Berlin Heidelberg，2008：197－218 （in Chinese）. Mark de Berg，Otfried Cheong，Marc van Kreveld，等.計(jì)算幾何—算法與應(yīng)用 ［M］.3版.鄧俊輝，譯.北京：清華大學(xué)出版社，2009：250－285.

［2］ZHOU Jia－wen，XUE Zhi－xin，WAN Shi.Survey of triangulation methods ［J］.Computer and Modernization，2010，26（7）：75－78 （in Chinese）.［周佳文，薛之昕，萬(wàn)施.三角剖分綜述 ［J］.計(jì)算機(jī)與現(xiàn)代化，2010，26 （7）：75－78.］

［3］Doubly－connected edge list ［EB/OL］. ［2011－04－18］.http：//en.wikipedia.org/wiki/Doubly＿connected＿edge＿list.

［4］Ryan Holmes.The DCEL data structure for 3Dgraphics［EB/OL］.［2009－09－27］.http：//www.holmes3d.net/graphics/dcel/.

［5］Max McGuire.The half－edge data structure ［EB/OL］.［2000－08－07］.http：//www.flipcode.com/archives/The ＿ Half－Edge ＿Data＿Structure.shtml.

［6］Guibas L，Stolfi J.Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams ［J］.ACM Transactions on Graphics，1985，4 （2）：75－123.

［7］Rex A Dwyer.A faster divide－and conquer algorithm for constructing Delaunay triangulations［J］.Algorithmica，1987，2（2）：137－151.

［8］Lee D T，Schachter B J.Two algorithms for constructing a Delaunay triangulation ［J］.International Journal of Computer and Information Sciences，1980，9 （3）：219－242.

［9］Thomas H Cormen，Charles E Leiserson，Ronald L Rivest，et al.Introduction to algorithms［M］.PAN Jingui，GU Tiecheng，LI Chengfa，et al transl.2nd ed.MIT Press，2001：43－49 （in Chinese）.Thomas H Cormen，Charles E Leiserson，Ronald L Rivest，等.算法導(dǎo)論 ［M］.2版.潘金貴，顧鐵成，李成法，等譯.北京：機(jī)械工業(yè)出版社，2011：43－49.

［10］WANG Li.Research on triangulation algorithm ［D］.Shanghai：Shanghai Jiaotong University，2010 （in Chinese）. ［王力.三角剖分算法研究 ［D］.上海：上海交通大學(xué)，2010.］