基于逐點插入法的定尺度三角剖分算法研究

葉震 卞超杰 梅雨晴 儲賽

摘 要：在三角網剖分過程中，三角形是否均勻是決定三角網是否高質量的重要因素，在構網中形狀不規則的三角形被稱為病態三角形。為了減少構網中病態三角形的數量，本研究在傳統逐點插入法的基礎上，對凸包邊界進行細化，生成邊界精度較高的新凸包。運用定尺度剖分法對整體三角網進行篩選，對篩選出不符合尺度的三角形進行合并，生成較為均勻的三角網。試驗表明，與未設定剖分尺度的圖形相比，經過設定尺度后生成的三角網更均勻，所以通過設置剖分尺度能夠有效地減少構網中的病態三角形數量。

關鍵詞：精細化凸包;逐點插入;定尺度剖分;三角剖分;算法

中圖分類號：TG333 ? 文獻標志碼：A ? 文章編號：1003-5168（2022）6-0011-05

DOI：10.19968/j.cnki.hnkj.1003-5168.2022.06.002

Research on Scaling Triangulation Algorithm Based on Point by Point Insertion Method

YE Zhen ? ?BIAN Chaojie ? ?MEI Yuqing ? ?CHU Sai

（School of Geographic Information and Tourism，Chuzhou University，Chuzhou 239000，China）

Abstract：In the triangulation process，whether the triangles are uniform or not is an important factor to determine whether the triangulation is of high quality.In the network construction，the irregular triangles are called ill conditioned triangles.In order to reduce the ill conditioned triangles in the network construction，this research refines the convex hull boundary based on the traditional point by point insertion method，and generates a new convex hull with high boundary accuracy.The overall triangulation is screened by using fixed-scale triangulation，and the triangles that do not meet the scale are obtained，which are combined in the next step to generate a more uniform triangulation.The experiment shows that the triangulation network generated after setting the scale is more uniform than the graphics without setting the division scale.Therefore，by setting the partition scale，the number of ill conditioned triangle in network construction is effectively reduced.

Keywords：fine convex package;point by point insertion;fixed scale section; triangulation;algorithm

0 引言

三角網剖分是計算幾何中一種重要的幾何算法。在所有三角網剖分算法中，Delaunay三角網的分析與應用更加方便[1]。Delaunay三角網具有以下三個特征。①唯一性。Delaunay三角網是唯一的。②最大化最小角特性。由Delaunay三角剖分算法所形成的三角形的最小角最大[2]。③空外接圓特性。Delaunay三角剖分所形成的三角網中任意三角形的外接圓不包含其他離散點。Delaunay三角網算法在地理信息系統、測繪和城市規劃等領域被大量使用。目前，Delaunay三角網的生成算法有很多，比較常見的算法有三種：逐點插入法、生長法和分治算法[3]。毛克樂[4]對逐點插入法提出了一種改進方法;毛文山等對生長法進行了相應的改進并探討其應用[5];徐旭等探討了如何在三角網中建立索引[6];吳芬提出了一種加密網格的生成方法[7];Ahmed等在2021年也曾提出運用約束調整的方法來調整三角網[8];Marsh等曾提出在格網生成的同時，可以進行重要特征的約束[9];田家恒提出在構建格網的同時，加入限制條件可以提高構網效率[10];史曉楠等利用逐點插值法、可變尺度加密算法、生長法和分治法四種方法解決了斷層線段合理插入問題，有效地提高了構網的質量和效率[11];王漢財等提出自動消除平三角的方法，用來提高效率[12];鄧曙光等提出上下掃線的Delaunay算法，減少了構網中的病態三角形（狹長三角形）[13]。

本研究在逐點插入法的基礎上引入網格索引，探討如何均勻地實現三角網剖分。首先使用逐點插入法對三角網進行剖分，然后再進行定尺度剖分，減少狹長三角形的出現，通過設置剖分尺度能夠有效減少構網中的病態三角形數量。

1 三角網構建理論分析

三角網構建是先建立網格索引，在網格基礎上讀取數據形成的凸包。接著使用逐點插入法進行三角網剖分，由于直接使用逐點插入法生成的三角網中會產生部分不規則的三角形，采用定尺度法對不均勻三角形進行合并，最終實現減少狹長三角形的目標。算法流程圖如圖1。

2 算法設計

2.1 構建三角網格

2.1.1 構建網格索引。將所有離散點都放入網格中，設在同一水平范圍內的離散點數量為N，規定格網的閾值為n，保證每個網格內離散點的數量在n個左右，所以N/n為一個方向上格網的個數。將網格內的離散點沿X軸方向由小到大排序，得到最小值和最大值Xmin和Xmax，Y軸也同樣進行排序，得到最小值和最大值Ymin和Ymax。XS為X軸方向算出的網格長度理論值，YS為Y軸方向算出的網格長度理論值。XS、YS的表達式如式（1）、式（2）所示，最終網格的長度S的表達式如式（3）所示。

[XS=Xmax?XminNn] ? ? ?（1）

[YS=Ymax?YminNn] ? ? ?（2）

[S=XS+YS2] ? ? ? （3）

隨后規劃出標準的網格，使所有的離散點均勻地分布在網格中，如圖2所示。

2.1.2 建立區域凸包。先將格網中的網格進行標記，沿X軸方向由左到右依次標記為X1、X2、X3、...、XN，沿Y軸方向由下到上依次標記為Y1、Y2、Y3、...、YN。取格網最外圈的一圈網格X1Y1、X1Y2、X1Y3、...、X1YN;YNX2、YNX3、YNX4、...、YNXN;XNYN-1、XNXN-2、XNXN-3、...、XNY1;X2Y1、X3Y1、X4Y1、...、XN-1Y1。對這些網格依次進行查詢，若存在離散點P在此網格中，則依次記為P1、P2、P3、...、Pn，將P1、P2、P3、...、Pn依次連接得到初始凸包。如圖3所示。

按上述方法進行取點，若網格中沒有存在離散點，則跳過此網格;若在兩個網格的交界處存在一個離散點，且兩個網格中只存在這一點，則只取此點;若存在兩個或多個點，按式（4）取L值最小的點。

[L=a2+b2] ? ? ?（4）

其中，a為離散點P距離上邊界或者下邊界的距離（上下距離主要看此網格在格網中所處的位置，若在上邊界則直接取離上邊界的距離為a，若在下邊界則直接取離下邊界的距離為a，若在兩側則將上下距離進行對比取短的距離為a），b為離散點P距離左邊界或者右邊界的距離（左右距離主要看此網格在格網中所處的位置，若在左邊界則直接取離左邊界的距離為b，若在右邊界則直接取離右邊界的距離為b，若在兩側則將上下距離進行對比取短的距離為b）。

2.1.3 提高凸包邊界的精度。在提取離散點P時，某些網格不存在離散點，則將邊緣的網格向內部推進一格，若還不存在離散點則再向內部推進一格，直到找到存在離散點的網格為止。向內部推進的格子最多為M（M為此處橫向或縱向連續不存在離散點網格的個數）。找到存在于網格中的離散點Pn+1，將其納入凸包的邊界點中生成新的凸包。若存在離散點在凸包外，可以直接將其納入凸包的邊界點中，生成新凸包。如圖4所示。

2.1.4 初始三角剖分。任取凸包內一點與凸包點進行連接，構成最初的三角網（見圖5）。

2.1.5 逐點插入法構建三角網。

①在所有離散點中隨機選取一個點，依次連接該點和圖中所有的點。

②隨機選取最初三角形，開始檢索。

③將剩余的點依次插入，在插入過程中需要判斷該點的位置，找出包含此點的三角形T，刪除T的公共邊;假設插入的點為D點，判斷三角形T中是否包含點D（見圖6）。設三角形的三個頂點為A、B、C。S1為三角形ABD的面積，S2為三角形ACD的面積，S3為三角形BCD的面積，如果點D在三角形T中，則3個三角形的面積S1、S2、S3之和等于三角形T的面積;如果點D不在三角形T中，則3個三角形的面積S1、S2、S3之和大于三角形T的面積。如果3個三角形的面積S1、S2、S3有一個為0，則表示D點在三角形T的一個邊上。如果S1為0，則表示D點在AB邊上;如果S2為0，則表示D點在AC邊上;如果S3為0，則表示D點在BC邊上。

找到D點之后，形成3個新的三角形（見圖7）。

④利用Lawson提出的局部優化算法，對所有三角形逐個更新[14-15]。

⑤重復步驟②③，直到插入所有的離散點。

逐點插入法的流程如圖8所示，采用逐點插入法直接生成的三角網如圖9所示。

2.2 設置剖分尺度

由于使用逐點插入法所構造的三角網中間部分的網格雜亂無章，為了使三角網剖分所得到的三角網更加均勻，需要對三角網進行進一步的處理。本研究提出了定尺度處理的方案，將格網設置為規定的尺度，進一步規格化格網。

搜索形成的三角形網格，只要三角形的高度小于分割尺度H，將接近于H的三角形中的小三角形刪除，保留最外圈的大三角形。具體流程如下。

①采用定尺度算法，先設定某個分割尺度H。

②最初用高度為H，對比格網中所有的三角形，篩選出高度小于H的三角形。

③在篩選出來的三角形中找到存在于同一個大三角形中的多個三角形，然后對小三角形進行合并。

得到的成果如圖10所示。

3 試驗結果對比

在上述兩個試驗中，圖9是直接采用逐點插入法進行網格構建，圖10則是在此基礎上設定了一個規定的尺度，利用該尺度對三角網內部的三角形進行篩選，隨后對小三角形進行合并。

通過對上述兩個試驗的結果進行對比，可以看出，只通過逐點插入法構建的三角網中存在著較多的不規則三角網，但是經過定尺度處理后，三角網將變得更加均勻。

4 結語

本研究通過設置剖分尺度，有效地改進了在三角網剖分過程中存在不規則三角網的問題，對傳統的逐點插入法進行了改良，設定一個分割尺度，對三角形進行篩選，對篩選出的三角形進行合并處理，處理后的三角網將更加均勻，方便貼合實際的鉆孔數據處理。

參考文獻：

[1] LINGAS A.The Greedy and Delaunay triangulations are not bad in the average case[J].Information Processing Letters，1986（1）：25-31.

[2] BERG M D，KREVELD M V，OVERMARS M，et al.Computational geometry algorithms and applications[M].2nd ed.Berlin：Springer-Verlag，2000.

[3] SLOAN S W.A fast algorithm for constructing Delaunay triangulations in the plane[J].Advanced Engineering Software，1987（1）：34-55.

[4] 毛克樂.改進SURF和Delaunay三角網在圖像匹配中應用[J].沈陽工業大學學報，2021（4）：432-438.

[5] 毛文山，劉濤，杜萍.約束Delaunay三角剖分的“島嶼”類圖斑符號填充[J].測繪通報，2020（6）：32-38，44.

[6] 徐旭，李源，陳學工.一種基于插入法的 Delaunay三角網生成算法[J].電腦與信息技術，2010（4）：29-44.

[7] 吳芬.平面域Delaunay三角剖分新加密算法[J].計算機與現代化，2007（7）：19-22，33.

[8] AHMED A，MUBARAK M.Horizontal displacement of control points using GNSS differential positioning and network adjustment[J].Measurement，2021.

[9] MARSH C B，SPITERI R J，POMEROY J W，et al.Multi-objective unstructured triangular mesh generation for use in hydrological and land surface models[J].Computers and Geosciences，2018（119）：49-67.

[10] 田家恒.關于優化三角網算法的地形建模BIM技術研究[J].四川建筑，2021（S1）：69-72.

[11] 史曉楠，王夢凡，王子童.一種含斷層數據的變尺度加密三角剖分算法[J].計算機應用與軟件，2019（12）：239-244.

[12] 王漢財，劉書華，金銀玉.DEM制作中基于ArcGIS平臺處理平三角的方法探究[J].長春工程學院學報（自然科學版），2021（3）：52-55，103.

[13] 鄧曙光，鄭智華，敖四芽，等.上下掃描線的Delaunay三角剖分算法[J].測繪科學，2019（2）：122-127.

[14] ZHANG Y H，ZHENG J Q，SUN W，et al.Image recognition method of building wall cracks based on feature distribution[J].Soft Computing，2020（24）：8285–8294.

[15] 尤磊，唐守正，宋新宇.以優先點為中心的 Delaunay三角網生長算法[J].中國圖象圖形學報，2016（1）：60-68.