[發明專利]Delaunay三角網的構建方法

在審

• 申請號: 202011299407.0
• 申請日: 2020-11-18
• 公開（公告）號: CN112530017A
• 公開（公告）日: 2021-03-19
• 發明（設計）人: 馮帥杰;周蘭鳳
• 申請（專利權）人: 上海應用技術大學
• 主分類號: G06T17/20
• 分類號: G06T17/20
• 代理公司: 上海漢聲知識產權代理有限公司 31236
• 代理人: 胡晶

本發明提供了一種Delaunay三角網的構建方法，該方法包括：讀取離散的二維數據；遍歷離散的二維數據，將包含所有離散點的動態矩形包圍盒作為凸殼，構建初始三角網；對離散點進行排序，刪除重復的離散點；基于插入點混合定位算法，在排序后的離散點中輪流取點插入到初始三角網中，構建不斷優化的三角網；在所有離散點插入完畢之后，刪除與動態矩形包圍盒頂點相關的三角形，得到目標Delaunay三角網。從而可以明顯提高插入點定位的效率，不易受到數據點的增加而影響效率，快速穩定將插入點定位到所在的目標三角形，大大提升構建Delaunay三角網的速度。

技術領域

本發明涉及信息技術處理領域，具體地，涉及Delaunay三角網的構建方法。

背景技術

三角剖分是計算幾何領域的重要研究內容之一，而其中三角剖分由于數據結構簡單且冗余小、效率高的優點，以及最大化最小角和空外接圓的性質，在地理信息系統、數字高程插值、幾何重構等領域有著廣泛的應用。

Delaunay三角剖分現主要用的是直接剖分算法。直接三角剖分算法相比更加簡便，內存占用少，更適合大量數據的三角網構建。對于直接Delaunay三角剖分算法，主要有三種：靜態的三角網生長法和分治算法、動態的逐點插入法。其中逐點插入法相比其他算法占用內存小，效率高，對于大規模數據適應性高，其在很多領域有更廣泛的應用。

點定位算法在路徑規劃等多種領域都是不可或缺的一種算法，在進行Delaunay三角剖分過程中也往往是關鍵性問題。因為Delaunay三角剖分算法使用逐點插入法，該算法會判斷插入點與當前三角形的位置關系，不斷搜索達到目標三角形，而隨著點數的增加，點定位速度會受到很大影響。

通過對現有的插入點定位算法研究分析，發現有些算法沒有對大量數據點進行預處理，整體定位效率不是很高；當插入點位于兩邊延長線交叉區域時，由于進行插入點定位要頻繁地計算三角形的重心，造成了一定程度的時間消耗；有些算法搜索路徑不唯一，有些算法雖然解決了路徑不唯一的情況但不是最佳路徑。

發明內容

針對現有技術中的缺陷，本發明的目的是提供一種Delaunay三角網的構建方法。

本發明提供一種Delaunay三角網的構建方法，包括：

步驟1：讀取離散的二維數據；

步驟2：遍歷所述離散的二維數據，將包含所有離散點的動態矩形包圍盒作為凸殼，構建初始三角網；

步驟3：對所述離散點進行排序，刪除重復的離散點；

步驟4：基于插入點混合定位算法，在排序后的離散點中輪流取點插入到所述初始三角網中，構建不斷優化的三角網；

步驟5：在所有離散點插入完畢之后，刪除與所述動態矩形包圍盒頂點相關的三角形，得到目標Delaunay三角網。

可選地，所述步驟2包括：

遍歷所述離散的二維數據，尋找到離散點中X軸坐標最大的點Xmax、X軸坐標最小的點Xmin、Y軸坐標最大的點Ymax、Y軸坐標最小的點Ymin；

根據Xmax、Xmin、Ymax和Ymin，來建立包含所有離散點的動態矩形包圍盒；

基于所述動態矩形包圍盒，構建初始三角網。

可選地，所述步驟3包括：

采用快速排序算法，將所述離散點按X坐標從小到大排序，其中，X坐標相同的離散點按Y坐標從小到大排序。

可選地，所述步驟4包括：

步驟4.1：基于插入點混合定位算法，在排序后的離散點中輪流取點插入到所述初始三角網中，并將插入的點與其所在目標三角形的頂點分別連接，得到新的三角網；