三角剖分

三角剖分是代數拓撲學里最基本的研究方法。 以曲面為例， 我們把曲面剖開成一塊塊碎片，要求滿足下麵條件： （1）每塊碎片都是曲邊三角形； （2）曲面上任何兩個這樣的曲邊三角形，要么不相交，要么恰好相交於一條公共邊（不能同時交兩條或兩條以上的邊)。

基本介紹

• 中文名：三角剖分
• 外文名：Delaunay triangulated graph
• 釋義：代數拓撲學里最基本的研究方法
• 滿足條件：每塊碎片都是曲邊三角形；

定義

拓撲學的一個已知事實告訴我們：任何曲面都存在三角剖分。

假設曲面上有一個三角剖分， 我們把所有三角形的頂點總個數記為p(公共頂點只看成一個，下同),邊數記為a,三角形的個數記為n,則e=p-a+n是曲面的拓撲不變數。 也就是說不管是什麼剖分， e總是得到相同的數值。 e被稱為稱為歐拉示性數。

假設g是曲面上洞眼的個數（比如球面沒有洞，故g=0;又如環面有一個洞，故g=1），那么e=2-2g。

g也是拓撲不變數，稱為曲面的虧格(genus)。

上面例舉曲面的情形。對一般的拓撲對象（復形），我們有類似的剖分，通常成為單純剖分。 分割出的每塊碎片稱為單純形（簡稱單形）。

相關概念

拓撲圖

是圖論的一個重要概念，能夠嵌入在某一拓撲空間T中的圖G稱為拓撲圖，即,圖G的頂點為拓撲空間T中的點，邊為連結其兩端點的簡單曲線,且任意兩邊除端點可能公共外無其他公共點。若拓撲空間T為曲面S且S\G的每個連通片都是單連通區域,則稱G為曲面S上的地圖，記為M。用G(M)表示由M的頂點和邊所構成的圖，地圖M的可定向性是由曲面S的可定向性確定的。即,若S為可定向的，則稱M為可定向地圖，否則稱M為不可定向的，曲面S的虧格稱為地圖M的虧格。若記v,ε和φ分別為M的頂點數、邊數和面數，則

(p為M的可定向虧格；q為M的不可定向虧格)

事實上，這個公式是於1812-1813年間由呂里爾(Lhuilier,S.J.)給出的.因為歐拉(Euler,L.)第一個注意到這類關係，這個公式仍稱為歐拉公式。其中E(M)稱為地圖M的歐拉示性數。

對於地圖M，在其每一面的內部選取一點作為頂點，對於每條邊e，將與其關聯的兩面中選定的頂點用一條簡單曲線e′連結，使得e′除與e有一個公共點外不與M的其他任何邊有公共點。這樣得到的地圖M′稱為M的對偶地圖，這裡的對偶性也是對稱的，即,若M′為M的對偶地圖,則M也為M′的對偶地圖，若(不)可定向地圖M對於任何虧格小於M的虧格的(不)可定向地圖M′,G(M)與G(M′)是不同構的，則稱M是(不)可定向的最大地圖。因為在所有那些與G(M)同構的地圖中，這個M的面數最多。若M是曲面S上的地圖,且M的每個面都是三角形，則稱M是S的一個三角剖分。凡三角剖分都是最大地圖,但反之則不然，另一方面,若(不)可定向地圖M，對於任何虧格大於M的(不)可定向地圖M′，G(M)與G(M′)不同構，則稱M為最小地圖，因為在所有與G(M)同構的地圖中以這個M的面數為最少，若一個地圖僅有一個面,則稱它為單面地圖，凡單面地圖均是最小地圖，但反之則不然。

復形的多面體

亦稱復形的基礎空間，一類特殊的拓撲空間.復形是代數拓撲中的基本概念，以它作為工具進行研究，而最終目的是得出它所給出的拓撲空間，也就是多面體的拓撲性質，若K是n維歐氏空間R中的復形,則K中全體單形的所有點組成的集合

作為R的子空間稱為K的多面體，記為|K|，K稱為多面體|K|的一個單純剖分或三角剖分。一般地，多面體可以有不同的單純剖分.有限復形的多面體是緊緻空間。

分類

二維區域的三角剖分

在二維場問題中，涉及的區域是以Γ為邊界的平面區域Ω，三角剖分是常用的形式，它適用於各種幾何形狀的區域和非均勻介質的情況。其剖分原則是：

1.將Ω劃分為若干三角形單元，三角形的頂點稱為節點，用相鄰邊界節點連成的折線及其圍成的區域近似代替曲線邊界Γ和區域Ω，如圖1。

圖1

2.每個單元的頂點只能是相鄰單元的頂點，不能是相鄰單元邊上的內點，圖2的情況是不容許的。

3.在u(x，y)變化可能劇烈的地方，格線要密，變化較小的地方格線可稀一些。

圖2

圖3

4.如果域內有不同介質，則不同介質的分界線為劃分單元的分割線。

5.從收斂角度考慮，任一單元的三個邊長度不可相差懸殊。

6.將所有單元和節點逐一編號，其方式和次序可以任意，不影響計算結果，但節點編號的次序對求解有限元法方程的工作量有重大影響。一般應將待定參數的節點集中在小號區，將節點參數已知的集中在大號區，而其中的零值節點則集中到最後。此外，要求兩個相鄰節點編號之差的絕對值中的最大者愈小愈好，例如，圖3區域的三角剖分，(a)的編號方式形成的帶狀總體系數矩陣的頻寬要比(b)的小，從而更節約存儲和計算量。

簡單多邊形三角剖分

1.簡單多邊形的概念

三維地質建模中不僅會遇到平麵點集的三角剖分，還會遇到多邊形的剖分問題。這裡主要介紹簡單多邊形的三角剖分問題。簡單多邊形具有以下幾何特徵：

(1)多邊形的邊界是由若干個結點順序連線而成的閉合環，任意相鄰兩個結點對定義了一條有向邊；

(2)任意兩條有向邊的交要么為多邊形的邊界上的一個結點，要么為空；

(3)經過多邊形的邊界上的任一個結點，有且僅有兩條有向邊。圖4(a)中的多邊形不滿足上述條件(1)，圖4(b)不滿足上述條件(2)，圖4(c)中的多邊形不滿足上述條件(3)，圖4(d)中多邊形屬簡單多邊形。

圖4

圖4

2.簡單多邊形剖分問題

簡單多邊形的三角剖分問題是指將簡單多邊形劃分成若干三角形的集合，即將簡單多邊形所圍區域劃分成二維單純復形，而且，任意三角形的頂點均為簡單多邊形的邊界結點。

3.簡單多邊形三角剖分的對角線法

由於簡單多邊形的三角剖分格線中，三角形的頂點均為簡單多邊形的邊界結點，因此，所有三角形的邊只能來自簡單多邊形的邊與對角線。根據這個特點，我們可以採用對角線法進行簡單多邊形的三角剖分，算法過程如下：

(1)計算任意兩非相鄰結點之間的距離，即對角線長度，並存儲到數組T中；

(2)根據對角線長短對T進行排序；

(3)按照對角線從短到長順序從T中提取對角線t，並從T中刪除t，如果t不與其他邊相交且位於多邊形內，則t定是三角剖分的一條邊；

(4)如果t是三角剖分的一條邊，則判斷t是否構成某個三角形的邊；

(5)重複執行步驟(3)直到T為空。

空間點的三角剖分

對於一些簡單的模型重建出來的點比較少，可視性差，有圖1所示的兩幅從不同角度拍攝的圖像，重建的離散的點數據不能直觀地反映物體的結構，而且為了生成照片級別的具有真實感的模型或場景，先要對這些離散的點進行三角剖分。

圖5

進行空間點的三角剖分可以有兩種方法：一種是直接對空間中的點進行三角剖分，另一種是把空間中的點映射到平面中，對二維的點進行三角剖分，然後反映射到三維空間中。後一種方法相對比較簡單，這裡就採用後一種方法。

圖6

通過三角剖分算法對二維圖像中的特徵點進行三角剖分(Shewehuk，1995)，然後由於空間中的三維點是由特徵點計算出來的，所以根據這個映射關係，把剖分的二維點映射到三維空間中去，就實現了空間點的三角剖分，如圖6所示。