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

在審

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

1.一種Delaunay三角網的構建方法，其特征在于，包括：

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

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

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

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

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

2.根據權利要求1所述的Delaunay三角網的構建方法，其特征在于，所述步驟2包括：

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

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

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

3.根據權利要求1所述的Delaunay三角網的構建方法，其特征在于，所述步驟3包括：

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

4.根據權利要求1-3中任一項所述的Delaunay三角網的構建方法，其特征在于，所述步驟4包括：

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

步驟4.2：以空外接圓準則為依據，判斷共邊三角形的外接圓內是否包含其他點；若包含其他點，則將對角線進行交換，以使得生成的新三角形為Delaunay三角形。

5.根據權利要求4所述的Delaunay三角網的構建方法，其特征在于，所述步驟4.2：

步驟4.2.1：通過插入點P的位置選取點P所在的三角網中的任一三角形，記為當前三角形Ts；

步驟4.2.2：通過三角形面積坐標法求得點P與當前三角形Ts的方位類別，若為γ類，則執行步驟4.2.3；若為β類，則執行步驟4.2.4；若為α類，則執行步驟4.2.5；

步驟4.2.3：若其中某一邊的面積坐標為負，則以該邊右側的三角形Ti作為當前三角形Ts，識別點P與當前三角形Ts的位置，若P在當前三角形Ts內，則執行步驟4.2.5；若P不在當前三角形Ts內，則執行步驟4.2.2；

步驟4.2.4：先將當前三角形的頂點V₃與點P連接生成有向線段；

對有向線段V₃P進行第i次二分，得到中點Pi，找出包含點Pi且與V₃P有交點的三角形，記為先前三角形Ts’；i為大于0的自然數；

將有向線段PiP進行第i+1次二分，得到中點P_i+1，找出包含點P_i+1且與有向線段PiP相交的三角形，記為當前三角形Ts；

對比三角形Ts和三角形Ts’是否為同一個三角形，若是同一個三角形，則執行步驟4.2.5；若不是同一個三角形，則繼續朝著V₃P方向進行下一次二分，直到得到的三角形Ts和三角形Ts’為同一個三角形時，判斷插入點P是否在該三角形內，若是，則執行步驟4.2.5；若否，則繼續朝著V₃P方向進行下一次二分，直到得到的三角形Ts和三角形Ts’為同一個三角形，且插入點P在該三角形內，執行步驟4.2.5；

步驟4.2.5：找到插入點所在目標三角形，結束流程。