-
三角剖分
鎖定
三角剖分定義
假設曲面上有一個三角剖分, 我們把所有三角形的頂點總個數記為p(公共頂點只看成一個,下同),邊數記為a,三角形的個數記為n,則e=p-a+n是曲面的拓撲不變量。 也就是説不管是什麼剖分, e總是得到相同的數值。 e被稱為稱為歐拉示性數。
假設g是曲面上洞眼的個數(比如球面沒有洞,故g=0;又如環面有一個洞,故g=1),那麼e=2-2g。
三角剖分相關概念
拓撲圖
是圖論的一個重要概念,能夠嵌入在某一拓撲空間T中的圖G稱為拓撲圖,即,圖G的頂點為拓撲空間T中的點,邊為連結其兩端點的簡單曲線,且任意兩邊除端點可能公共外無其他公共點。若拓撲空間T為曲面S且S\G的每個連通片都是單連通區域,則稱G為曲面S上的地圖,記為M。用G(M)表示由M的頂點和邊所構成的圖,地圖M的可定向性是由曲面S的可定向性確定的。即,若S為可定向的,則稱M為可定向地圖,否則稱M為不可定向的,曲面S的虧格稱為地圖M的虧格。若記v,ε和φ分別為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的面數為最少,若一個地圖僅有一個面,則稱它為單面地圖,凡單面地圖均是最小地圖,但反之則不然。
[2]
復形的多面體
亦稱復形的基礎空間,一類特殊的拓撲空間.復形是代數拓撲中的基本概念,以它作為工具進行研究,而最終目的是得出它所給出的拓撲空間,也就是多面體的拓撲性質,若K是n維歐氏空間R中的復形,則K中全體單形的所有點組成的集合
三角剖分分類
二維區域的三角剖分
1.將Ω劃分為若干三角形單元,三角形的頂點稱為節點,用相鄰邊界節點連成的折線及其圍成的區域近似代替曲線邊界Γ和區域Ω,如圖1。
2.每個單元的頂點只能是相鄰單元的頂點,不能是相鄰單元邊上的內點,圖2的情況是不容許的。
3.在u(x,y)變化可能劇烈的地方,網格要密,變化較小的地方網格可稀一些。
4.如果域內有不同介質,則不同介質的分界線為劃分單元的分割線。
5.從收斂角度考慮,任一單元的三個邊長度不可相差懸殊。
6.將所有單元和節點逐一編號,其方式和次序可以任意,不影響計算結果,但節點編號的次序對求解有限元法方程的工作量有重大影響。一般應將待定參數的節點集中在小號區,將節點參數已知的集中在大號區,而其中的零值節點則集中到最後。此外,要求兩個相鄰節點編號之差的絕對值中的最大者愈小愈好,例如,圖3區域的三角剖分,(a)的編號方式形成的帶狀總體系數矩陣的帶寬要比(b)的小,從而更節約存儲和計算量。
簡單多邊形三角剖分
1.簡單多邊形的概念
(1)多邊形的邊界是由若干個結點順序連接而成的閉合環,任意相鄰兩個結點對定義了一條有向邊;
(2)任意兩條有向邊的交要麼為多邊形的邊界上的一個結點,要麼為空;
(3)經過多邊形的邊界上的任一個結點,有且僅有兩條有向邊。圖4中(a)中的多邊形不滿足上述條件(1),圖4中(b)不滿足上述條件(2),圖4中(c)中的多邊形不滿足上述條件(3),圖4中(d)中多邊形屬簡單多邊形。
2.簡單多邊形剖分問題
簡單多邊形的三角剖分問題是指將簡單多邊形劃分成若干三角形的集合,即將簡單多邊形所圍區域劃分成二維單純復形,而且,任意三角形的頂點均為簡單多邊形的邊界結點。
3.簡單多邊形三角剖分的對角線法
由於簡單多邊形的三角剖分網格中,三角形的頂點均為簡單多邊形的邊界結點,因此,所有三角形的邊只能來自簡單多邊形的邊與對角線。根據這個特點,我們可以採用對角線法進行簡單多邊形的三角剖分,算法過程如下:
(1)計算任意兩非相鄰結點之間的距離,即對角線長度,並存儲到數組T中;
(2)根據對角線長短對T進行排序;
(3)按照對角線從短到長順序從T中提取對角線t,並從T中刪除t,如果t不與其他邊相交且位於多邊形內,則t定是三角剖分的一條邊;
(4)如果t是三角剖分的一條邊,則判斷t是否構成某個三角形的邊;
空間點的三角剖分
對於一些簡單的模型重建出來的點比較少,可視性差,有圖5所示的兩幅從不同角度拍攝的圖像,重建的離散的點數據不能直觀地反映物體的結構,而且為了生成照片級別的具有真實感的模型或場景,先要對這些離散的點進行三角剖分。
[5]
進行空間點的三角剖分可以有兩種方法:一種是直接對空間中的點進行三角剖分,另一種是把空間中的點映射到平面中,對二維的點進行三角剖分,然後反映射到三維空間中。後一種方法相對比較簡單,這裏就採用後一種方法。