[發明專利]一種非封閉圖形的三角剖分算法

有效

• 申請號: 201210538304.4
• 申請日: 2012-12-13
• 公開（公告）號: CN103020356A
• 公開（公告）日: 2013-04-03
• 發明（設計）人: 張楊;鄧兆祥;陽小光;周愷;王婷婷;李根;李泉;張梟
• 申請（專利權）人: 重慶大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 趙榮之

技術領域

本發明屬于計算機輔助設計領域，特別涉及一種針對平面上非封閉圖形的一種三角剖分算法。

背景技術

三角剖分是計算機輔助設計中的一個重要課題，它在有限元分析、信息可視化等領域有著重要的應用。對科學計算及工程分析產生的不規則復雜數據場進行模擬時，三角剖分網格比矩形剖分網格具備更強的適應能力。

Delaunay三角剖分具有最小內角最大的性質，能盡可能避免病態三角形的出現，有效地提高逼近精度，使網格的整體質量保持最優。逐點插入法作為Delaunay三角剖分的一種重要算法，思路簡單而易于編程實現，能有效實現對封閉圖形的剖分。但當點集范圍是非凸區域或存在空腔時，該算法將產生非法三角形而難以滿足剖分要求。

針對傳統Delaunay剖分并不支持非封閉圖形的問題，不少學者開始對Delaunay算法進行改進，通過引進約束邊的方式對圖形的邊界進行判別。這種改進算法雖能實現對非封閉圖形的剖分，但由于需要反復對約束邊界進行判斷和調整，占用的內存較大且算法的時間復雜度差，降低了程序的執行效率，從而影響圖形的繪制和顯示。

因此急需一種效率高且精度好的三角剖分算法。

發明內容

有鑒于此，本發明所要解決的技術問題是提供一種效率高且精度好的三角剖分算法，該算法克服了難以對非封閉圖形進行三角剖分的不足。

本發明的目的是這樣實現的：

本發明提供的一種非封閉圖形的三角剖分算法，包括以下步驟：

S1：在非封閉圖形的空腔域內引入至少一個虛擬點；

S2：將虛擬點視為普通散點參與三角剖分；

S3：將以虛擬點為頂點的所有三角形刪除，形成空腔，實現對非封閉圖形的三角剖分。

進一步，所述步驟S1中所述空腔域內為非封閉圖形的空腔域內。

進一步，所述步驟S2中的虛擬點與空腔的邊界應保持預設距離。

進一步，所述三角剖分采用Delaunay算法三角剖分。

進一步，所述三角剖分中的虛擬點分別與空腔邊界上的普通散點連接形成線段，并構建用于存放包括頂點編號和頂點坐標的頂點信息的三角形鏈表。

本發明的優點在于：本發明通過在非封閉圖形的空腔域內引入適當的虛擬點后再進行三角剖分，而后將以虛擬點為頂點的所有三角形進行刪除形成空腔的方法，有效解決了非封閉圖形的三角剖分難題，通過在空腔域內引入虛擬點，簡化了傳統的邏輯判斷思路，提高了程序的執行效率和圖形的繪制精度。本算法易于在實現的同時，對圖形的繪制精度高，能取得良好的顯示效果。

附圖說明

為了使本發明的目的、技術方案和優點更加清楚，下面將結合附圖對本發明作進一步的詳細描述，其中：

圖1為空腔內部引入虛擬點集；

圖2為算法1產生的三角剖分；

圖3為空腔清空后的三角剖分。

具體實施方式

以下將結合附圖，對本發明的優選實施例進行詳細的描述；應當理解，優選實施例僅為了說明本發明，而不是為了限制本發明的保護范圍。

實施例1

圖1為空腔內部引入虛擬點集，圖2為算法1產生的三角剖分，圖3為空腔清空后的三角剖分，如圖所示：本發明提供的一種非封閉圖形的三角剖分算法，包括以下步驟：

S1：在非封閉圖形的空腔域內引入至少一個虛擬點；虛擬點可以設置多個，兩個，三個四個等，對于多個虛擬點分別采用本發明提供的使用方法。

S2：將虛擬點視為普通散點參與三角剖分；在進行三角剖分時為保證虛擬點的加入僅對空腔域內部的三角剖分造成影響，將虛擬點與空腔的邊界應保持預設距離。虛擬點與空腔的邊界之間的距離可以根據精度的要求進行確定，所述三角剖分采用Delaunay算法三角剖分。所述三角剖分中的虛擬點分別與空腔邊界上的普通散點連接形成線段，并構建用于存放包括頂點編號和頂點坐標的頂點信息的三角形鏈表。

S3：將以虛擬點為頂點的所有三角形刪除，形成空腔，實現對非封閉圖形的三角剖分。

實施例2

下面詳細說明實現對非封閉圖形的三角剖分的具體過程：

在本發明中，通過三個簡單的步驟來實現對圖像中的非封閉圖形的進行三角剖分并輸出處理完畢后的圖像。首先在圖形的空腔域內適當引入若干個虛擬點，再將虛擬點視為普通散點參與Delaunay三角剖分，完成全部區域的剖分后，最后刪除以虛擬點為頂點的所有三角形，從而完成對非封閉圖形的三角剖分。

在引入算法前，先提出相應點集的定義：