[科普中國(guó)]-三角剖分

定義

拓?fù)鋵W(xué)的一個(gè)已知事實(shí)告訴我們：任何曲面都存在三角剖分。1

假設(shè)曲面上有一個(gè)三角剖分， 我們把所有三角形的頂點(diǎn)總個(gè)數(shù)記為p(公共頂點(diǎn)只看成一個(gè)，下同),邊數(shù)記為a,三角形的個(gè)數(shù)記為n,則e=p-a+n是曲面的拓?fù)洳蛔兞俊?也就是說(shuō)不管是什么剖分， e總是得到相同的數(shù)值。 e被稱(chēng)為稱(chēng)為歐拉示性數(shù)。

假設(shè)g是曲面上洞眼的個(gè)數(shù)（比如球面沒(méi)有洞，故g=0;又如環(huán)面有一個(gè)洞，故g=1），那么e=2-2g。

g也是拓?fù)洳蛔兞?，稱(chēng)為曲面的虧格(genus)。

上面例舉曲面的情形。對(duì)一般的拓?fù)鋵?duì)象（復(fù)形），我們有類(lèi)似的剖分，通常成為單純剖分。 分割出的每塊碎片稱(chēng)為單純形（簡(jiǎn)稱(chēng)單形）1。

相關(guān)概念拓?fù)鋱D是圖論的一個(gè)重要概念，能夠嵌入在某一拓?fù)淇臻gT中的圖G稱(chēng)為拓?fù)鋱D，即,圖G的頂點(diǎn)為拓?fù)淇臻gT中的點(diǎn)，邊為連結(jié)其兩端點(diǎn)的簡(jiǎn)單曲線(xiàn),且任意兩邊除端點(diǎn)可能公共外無(wú)其他公共點(diǎn)。若拓?fù)淇臻gT為曲面S且S\G的每個(gè)連通片都是單連通區(qū)域,則稱(chēng)G為曲面S上的地圖，記為M。用G(M)表示由M的頂點(diǎn)和邊所構(gòu)成的圖，地圖M的可定向性是由曲面S的可定向性確定的。即,若S為可定向的，則稱(chēng)M為可定向地圖，否則稱(chēng)M為不可定向的，曲面S的虧格稱(chēng)為地圖M的虧格。若記v,ε和φ分別為M的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，則

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

事實(shí)上，這個(gè)公式是于1812-1813年間由呂里爾(Lhuilier,S.J.)給出的.因?yàn)闅W拉(Euler,L.)第一個(gè)注意到這類(lèi)關(guān)系，這個(gè)公式仍稱(chēng)為歐拉公式。其中E(M)稱(chēng)為地圖M的歐拉示性數(shù)。

對(duì)于地圖M，在其每一面的內(nèi)部選取一點(diǎn)作為頂點(diǎn)，對(duì)于每條邊e，將與其關(guān)聯(lián)的兩面中選定的頂點(diǎn)用一條簡(jiǎn)單曲線(xiàn)e′連結(jié)，使得e′除與e有一個(gè)公共點(diǎn)外不與M的其他任何邊有公共點(diǎn)。這樣得到的地圖M′稱(chēng)為M的對(duì)偶地圖，這里的對(duì)偶性也是對(duì)稱(chēng)的，即,若M′為M的對(duì)偶地圖,則M也為M′的對(duì)偶地圖，若(不)可定向地圖M對(duì)于任何虧格小于M的虧格的(不)可定向地圖M′,G(M)與G(M′)是不同構(gòu)的，則稱(chēng)M是(不)可定向的最大地圖。因?yàn)樵谒心切┡cG(M)同構(gòu)的地圖中，這個(gè)M的面數(shù)最多。若M是曲面S上的地圖,且M的每個(gè)面都是三角形，則稱(chēng)M是S的一個(gè)三角剖分。凡三角剖分都是最大地圖,但反之則不然，另一方面,若(不)可定向地圖M，對(duì)于任何虧格大于M的(不)可定向地圖M′，G(M)與G(M′)不同構(gòu)，則稱(chēng)M為最小地圖，因?yàn)樵谒信cG(M)同構(gòu)的地圖中以這個(gè)M的面數(shù)為最少，若一個(gè)地圖僅有一個(gè)面,則稱(chēng)它為單面地圖，凡單面地圖均是最小地圖，但反之則不然。2

復(fù)形的多面體亦稱(chēng)復(fù)形的基礎(chǔ)空間，一類(lèi)特殊的拓?fù)淇臻g.復(fù)形是代數(shù)拓?fù)渲械幕靖拍?，以它作為工具進(jìn)行研究，而最終目的是得出它所給出的拓?fù)淇臻g，也就是多面體的拓?fù)湫再|(zhì)，若K是n維歐氏空間R中的復(fù)形,則K中全體單形的所有點(diǎn)組成的集合

作為R的子空間稱(chēng)為K的多面體，記為|K|，K稱(chēng)為多面體|K|的一個(gè)單純剖分或三角剖分。一般地，多面體可以有不同的單純剖分.有限復(fù)形的多面體是緊致空間。2

分類(lèi)二維區(qū)域的三角剖分在二維場(chǎng)問(wèn)題中，涉及的區(qū)域是以Γ為邊界的平面區(qū)域Ω，三角剖分是常用的形式，它適用于各種幾何形狀的區(qū)域和非均勻介質(zhì)的情況。其剖分原則是：3

1.將Ω劃分為若干三角形單元，三角形的頂點(diǎn)稱(chēng)為節(jié)點(diǎn)，用相鄰邊界節(jié)點(diǎn)連成的折線(xiàn)及其圍成的區(qū)域近似代替曲線(xiàn)邊界Γ和區(qū)域Ω，如圖1。

2.每個(gè)單元的頂點(diǎn)只能是相鄰單元的頂點(diǎn)，不能是相鄰單元邊上的內(nèi)點(diǎn)，圖2的情況是不容許的。

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

4.如果域內(nèi)有不同介質(zhì)，則不同介質(zhì)的分界線(xiàn)為劃分單元的分割線(xiàn)。

5.從收斂角度考慮，任一單元的三個(gè)邊長(zhǎng)度不可相差懸殊。

6.將所有單元和節(jié)點(diǎn)逐一編號(hào)，其方式和次序可以任意，不影響計(jì)算結(jié)果，但節(jié)點(diǎn)編號(hào)的次序?qū)η蠼庥邢拊ǚ匠痰墓ぷ髁坑兄卮笥绊?。一般?yīng)將待定參數(shù)的節(jié)點(diǎn)集中在小號(hào)區(qū)，將節(jié)點(diǎn)參數(shù)已知的集中在大號(hào)區(qū)，而其中的零值節(jié)點(diǎn)則集中到最后。此外，要求兩個(gè)相鄰節(jié)點(diǎn)編號(hào)之差的絕對(duì)值中的最大者愈小愈好，例如，圖3區(qū)域的三角剖分，(a)的編號(hào)方式形成的帶狀總體系數(shù)矩陣的帶寬要比(b)的小，從而更節(jié)約存儲(chǔ)和計(jì)算量。

簡(jiǎn)單多邊形三角剖分

1.簡(jiǎn)單多邊形的概念

三維地質(zhì)建模中不僅會(huì)遇到平面點(diǎn)集的三角剖分，還會(huì)遇到多邊形的剖分問(wèn)題。這里主要介紹簡(jiǎn)單多邊形的三角剖分問(wèn)題。簡(jiǎn)單多邊形具有以下幾何特征：4

(1)多邊形的邊界是由若干個(gè)結(jié)點(diǎn)順序連接而成的閉合環(huán)，任意相鄰兩個(gè)結(jié)點(diǎn)對(duì)定義了一條有向邊；

(2)任意兩條有向邊的交要么為多邊形的邊界上的一個(gè)結(jié)點(diǎn)，要么為空；

(3)經(jīng)過(guò)多邊形的邊界上的任一個(gè)結(jié)點(diǎn)，有且僅有兩條有向邊。圖4(a)中的多邊形不滿(mǎn)足上述條件(1)，圖4(b)不滿(mǎn)足上述條件(2)，圖4(c)中的多邊形不滿(mǎn)足上述條件(3)，圖4(d)中多邊形屬簡(jiǎn)單多邊形。

2.簡(jiǎn)單多邊形剖分問(wèn)題

簡(jiǎn)單多邊形的三角剖分問(wèn)題是指將簡(jiǎn)單多邊形劃分成若干三角形的集合，即將簡(jiǎn)單多邊形所圍區(qū)域劃分成二維單純復(fù)形，而且，任意三角形的頂點(diǎn)均為簡(jiǎn)單多邊形的邊界結(jié)點(diǎn)。

3.簡(jiǎn)單多邊形三角剖分的對(duì)角線(xiàn)法

由于簡(jiǎn)單多邊形的三角剖分網(wǎng)格中，三角形的頂點(diǎn)均為簡(jiǎn)單多邊形的邊界結(jié)點(diǎn)，因此，所有三角形的邊只能來(lái)自簡(jiǎn)單多邊形的邊與對(duì)角線(xiàn)。根據(jù)這個(gè)特點(diǎn)，我們可以采用對(duì)角線(xiàn)法進(jìn)行簡(jiǎn)單多邊形的三角剖分，算法過(guò)程如下：

(1)計(jì)算任意兩非相鄰結(jié)點(diǎn)之間的距離，即對(duì)角線(xiàn)長(zhǎng)度，并存儲(chǔ)到數(shù)組T中；

(2)根據(jù)對(duì)角線(xiàn)長(zhǎng)短對(duì)T進(jìn)行排序；

(3)按照對(duì)角線(xiàn)從短到長(zhǎng)順序從T中提取對(duì)角線(xiàn)t，并從T中刪除t，如果t不與其他邊相交且位于多邊形內(nèi)，則t定是三角剖分的一條邊；

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

(5)重復(fù)執(zhí)行步驟(3)直到T為空。4

空間點(diǎn)的三角剖分對(duì)于一些簡(jiǎn)單的模型重建出來(lái)的點(diǎn)比較少，可視性差，有圖1所示的兩幅從不同角度拍攝的圖像，重建的離散的點(diǎn)數(shù)據(jù)不能直觀(guān)地反映物體的結(jié)構(gòu)，而且為了生成照片級(jí)別的具有真實(shí)感的模型或場(chǎng)景，先要對(duì)這些離散的點(diǎn)進(jìn)行三角剖分。5

進(jìn)行空間點(diǎn)的三角剖分可以有兩種方法：一種是直接對(duì)空間中的點(diǎn)進(jìn)行三角剖分，另一種是把空間中的點(diǎn)映射到平面中，對(duì)二維的點(diǎn)進(jìn)行三角剖分，然后反映射到三維空間中。后一種方法相對(duì)比較簡(jiǎn)單，這里就采用后一種方法。

通過(guò)三角剖分算法對(duì)二維圖像中的特征點(diǎn)進(jìn)行三角剖分(Shewehuk，1995)，然后由于空間中的三維點(diǎn)是由特征點(diǎn)計(jì)算出來(lái)的，所以根據(jù)這個(gè)映射關(guān)系，把剖分的二維點(diǎn)映射到三維空間中去，就實(shí)現(xiàn)了空間點(diǎn)的三角剖分，如圖6所示。5