1、Logo2015/10/29帶內邊界約束散亂數據的Delaunay三角剖分算法研究目錄Logo中點插入恢復邊界法1具體算法2優點3Logo中點插入恢復邊界法1Logo不斷在約束邊界上插入新點（中點）進行DT剖分，直到所有約束邊界都位于剖分結果的邊界集中。算法基本思路：Logo具體算法2Logo2.1 2.1 問題描述問題描述域域D(P,Q)平面上的一個平面上的一個區域區域；P=p1,p2,p3, pr域域D內的內的r個點個點；Q=q1,q2,q3, qs域內邊界上的域內邊界上的s個頂點個頂點。要求要求：對域對域D(P，Q)實現實現Delaunay三角剖分。三角剖分。Logo2.1 2.1 問題

2、描述問題描述域D(P,Q)忽略忽略Q點集點集邊界約束邊界約束特征生成的三角形網格特征生成的三角形網格T (1) D(1) D的某些邊界的某些邊界不在不在T T的邊集中的邊集中(2) T(2) T集中的某些邊位于集中的某些邊位于區域區域D D外外2.1 問題描述Logo(2) T集中的某些邊位于區域集中的某些邊位于區域D外外域D(P,Q)Logo2.2 2.2 算法描述算法描述進行標準的進行標準的DelaunayDelaunay三角剖分三角剖分, ,即即不考慮不考慮點的性質點的性質進行剖分。進行剖分。剖分結果為剖分結果為T1T1。FIRSTT1Logo2.2 2.2 算法描述算法描述對對T1T1

3、進行追蹤分析進行追蹤分析尋找尋找約束邊界約束邊界，對對未未在剖分在剖分中的三角形中的三角形采用采用中點插中點插入算法入算法恢復約束邊界恢復約束邊界, ,結果為結果為T2T2。步驟如下：。步驟如下：SECONDLogo2.2 2.2 算法描述算法描述 在在T1T1的剖分結果中進行查詢的剖分結果中進行查詢以判斷以判斷ABAB是否在是否在T1T1的三角的三角形邊集中形邊集中已經存在，如果存已經存在，如果存在，則轉向在，則轉向(1)(1)。 依次依次取出內孔的一條約束邊取出內孔的一條約束邊界界，設為，設為ABAB，直到所有內，直到所有內孔約束邊界取完為止。孔約束邊界取完為止。SECONDABT1Log

4、o2.2 2.2 算法描述算法描述 在在T11T11的剖分結果中進行查詢的剖分結果中進行查詢ACAC，BCBC是否已經在是否已經在T11T11的三的三角形邊集中，直至角形邊集中，直至ABAB邊完全邊完全被被DTDT所包含，然后轉向所包含，然后轉向(1)(1)。 設設ABAB的的中點中點為為C C，將，將C C點作為點作為附加點附加點插入網格插入網格，重新構造新，重新構造新的的DTDT網格，結果為網格，結果為T11T11。SECONDABCT11Logo2.2 2.2 算法描述算法描述對對T2T2約束約束邊界邊界內的內的多余多余線段線段進行進行邊界邊界裁減裁減順 序順 序 取 出取 出內 約 束

5、 邊內 約 束 邊界 鏈 表 中界 鏈 表 中的 一 個 邊的 一 個 邊界 點界 點 ， 設， 設為為K1K1，如如果 邊 界 鏈果 邊 界 鏈表 為 空 ，表 為 空 ，則退出。則退出。在內約束邊在內約束邊界鏈表中取界鏈表中取出出K2K2，K2K1K2K1且且K2K2不為不為K1K1的鄰的鄰接邊界點接邊界點，如果邊界鏈如果邊界鏈表為空，則表為空，則轉向轉向( (A A) )。判斷判斷K1K2K1K2在在T2T2是否存在，如是否存在，如果存在，且過果存在，且過K1K2K1K2的中點的的中點的水平射線水平射線與與內內約束邊界約束邊界的交的交點有點有奇數奇數個，個，則從則從T2T2中中刪除刪除包含包含K1K2K1K2邊的邊的所有三角形，所有三角形，否則轉向否則轉向( (B B) )。CB BATHIRD*Logo單孔約束和多孔約束Logo優點3Logo（1）中點插入的方法可用于解決包含復雜內孔的點域的三角剖分問題。（2）在不改變內邊界約束的條件下可使全局網格滿足DT特性，內孔邊界多邊形可以是凸的，也可以是凹的。（3）可用于具有復雜內外邊界或具有特征約束區域的三角剖分，且最終剖分結果滿足Delaunay性質，具有較好的普適性。Log