葉震 卞超杰 梅雨晴 儲(chǔ)賽

摘 要：在三角網(wǎng)剖分過(guò)程中，三角形是否均勻是決定三角網(wǎng)是否高質(zhì)量的重要因素，在構(gòu)網(wǎng)中形狀不規(guī)則的三角形被稱(chēng)為病態(tài)三角形。為了減少構(gòu)網(wǎng)中病態(tài)三角形的數(shù)量，本研究在傳統(tǒng)逐點(diǎn)插入法的基礎(chǔ)上，對(duì)凸包邊界進(jìn)行細(xì)化，生成邊界精度較高的新凸包。運(yùn)用定尺度剖分法對(duì)整體三角網(wǎng)進(jìn)行篩選，對(duì)篩選出不符合尺度的三角形進(jìn)行合并，生成較為均勻的三角網(wǎng)。試驗(yàn)表明，與未設(shè)定剖分尺度的圖形相比，經(jīng)過(guò)設(shè)定尺度后生成的三角網(wǎng)更均勻，所以通過(guò)設(shè)置剖分尺度能夠有效地減少構(gòu)網(wǎng)中的病態(tài)三角形數(shù)量。

關(guān)鍵詞：精細(xì)化凸包;逐點(diǎn)插入;定尺度剖分;三角剖分;算法

中圖分類(lèi)號(hào)：TG333 ? 文獻(xiàn)標(biāo)志碼：A ? 文章編號(hào)：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 引言

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

本研究在逐點(diǎn)插入法的基礎(chǔ)上引入網(wǎng)格索引，探討如何均勻地實(shí)現(xiàn)三角網(wǎng)剖分。首先使用逐點(diǎn)插入法對(duì)三角網(wǎng)進(jìn)行剖分，然后再進(jìn)行定尺度剖分，減少狹長(zhǎng)三角形的出現(xiàn)，通過(guò)設(shè)置剖分尺度能夠有效減少構(gòu)網(wǎng)中的病態(tài)三角形數(shù)量。

1 三角網(wǎng)構(gòu)建理論分析

三角網(wǎng)構(gòu)建是先建立網(wǎng)格索引，在網(wǎng)格基礎(chǔ)上讀取數(shù)據(jù)形成的凸包。接著使用逐點(diǎn)插入法進(jìn)行三角網(wǎng)剖分，由于直接使用逐點(diǎn)插入法生成的三角網(wǎng)中會(huì)產(chǎn)生部分不規(guī)則的三角形，采用定尺度法對(duì)不均勻三角形進(jìn)行合并，最終實(shí)現(xiàn)減少狹長(zhǎng)三角形的目標(biāo)。算法流程圖如圖1。

2 算法設(shè)計(jì)

2.1 構(gòu)建三角網(wǎng)格

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

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

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

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

隨后規(guī)劃出標(biāo)準(zhǔn)的網(wǎng)格，使所有的離散點(diǎn)均勻地分布在網(wǎng)格中，如圖2所示。

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

按上述方法進(jìn)行取點(diǎn)，若網(wǎng)格中沒(méi)有存在離散點(diǎn)，則跳過(guò)此網(wǎng)格;若在兩個(gè)網(wǎng)格的交界處存在一個(gè)離散點(diǎn)，且兩個(gè)網(wǎng)格中只存在這一點(diǎn)，則只取此點(diǎn);若存在兩個(gè)或多個(gè)點(diǎn)，按式（4）取L值最小的點(diǎn)。

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

其中，a為離散點(diǎn)P距離上邊界或者下邊界的距離（上下距離主要看此網(wǎng)格在格網(wǎng)中所處的位置，若在上邊界則直接取離上邊界的距離為a，若在下邊界則直接取離下邊界的距離為a，若在兩側(cè)則將上下距離進(jìn)行對(duì)比取短的距離為a），b為離散點(diǎn)P距離左邊界或者右邊界的距離（左右距離主要看此網(wǎng)格在格網(wǎng)中所處的位置，若在左邊界則直接取離左邊界的距離為b，若在右邊界則直接取離右邊界的距離為b，若在兩側(cè)則將上下距離進(jìn)行對(duì)比取短的距離為b）。

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

2.1.4 初始三角剖分。任取凸包內(nèi)一點(diǎn)與凸包點(diǎn)進(jìn)行連接，構(gòu)成最初的三角網(wǎng)（見(jiàn)圖5）。

2.1.5 逐點(diǎn)插入法構(gòu)建三角網(wǎng)。

①在所有離散點(diǎn)中隨機(jī)選取一個(gè)點(diǎn)，依次連接該點(diǎn)和圖中所有的點(diǎn)。

②隨機(jī)選取最初三角形，開(kāi)始檢索。

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

找到D點(diǎn)之后，形成3個(gè)新的三角形（見(jiàn)圖7）。

④利用Lawson提出的局部?jī)?yōu)化算法，對(duì)所有三角形逐個(gè)更新[14-15]。

⑤重復(fù)步驟②③，直到插入所有的離散點(diǎn)。

逐點(diǎn)插入法的流程如圖8所示，采用逐點(diǎn)插入法直接生成的三角網(wǎng)如圖9所示。

2.2 設(shè)置剖分尺度

由于使用逐點(diǎn)插入法所構(gòu)造的三角網(wǎng)中間部分的網(wǎng)格雜亂無(wú)章，為了使三角網(wǎng)剖分所得到的三角網(wǎng)更加均勻，需要對(duì)三角網(wǎng)進(jìn)行進(jìn)一步的處理。本研究提出了定尺度處理的方案，將格網(wǎng)設(shè)置為規(guī)定的尺度，進(jìn)一步規(guī)格化格網(wǎng)。

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

①采用定尺度算法，先設(shè)定某個(gè)分割尺度H。

②最初用高度為H，對(duì)比格網(wǎng)中所有的三角形，篩選出高度小于H的三角形。

③在篩選出來(lái)的三角形中找到存在于同一個(gè)大三角形中的多個(gè)三角形，然后對(duì)小三角形進(jìn)行合并。

得到的成果如圖10所示。

3 試驗(yàn)結(jié)果對(duì)比

在上述兩個(gè)試驗(yàn)中，圖9是直接采用逐點(diǎn)插入法進(jìn)行網(wǎng)格構(gòu)建，圖10則是在此基礎(chǔ)上設(shè)定了一個(gè)規(guī)定的尺度，利用該尺度對(duì)三角網(wǎng)內(nèi)部的三角形進(jìn)行篩選，隨后對(duì)小三角形進(jìn)行合并。

通過(guò)對(duì)上述兩個(gè)試驗(yàn)的結(jié)果進(jìn)行對(duì)比，可以看出，只通過(guò)逐點(diǎn)插入法構(gòu)建的三角網(wǎng)中存在著較多的不規(guī)則三角網(wǎng)，但是經(jīng)過(guò)定尺度處理后，三角網(wǎng)將變得更加均勻。

4 結(jié)語(yǔ)

本研究通過(guò)設(shè)置剖分尺度，有效地改進(jìn)了在三角網(wǎng)剖分過(guò)程中存在不規(guī)則三角網(wǎng)的問(wèn)題，對(duì)傳統(tǒng)的逐點(diǎn)插入法進(jìn)行了改良，設(shè)定一個(gè)分割尺度，對(duì)三角形進(jìn)行篩選，對(duì)篩選出的三角形進(jìn)行合并處理，處理后的三角網(wǎng)將更加均勻，方便貼合實(shí)際的鉆孔數(shù)據(jù)處理。

參考文獻(xiàn)：

[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] 毛克樂(lè).改進(jìn)SURF和Delaunay三角網(wǎng)在圖像匹配中應(yīng)用[J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2021（4）：432-438.

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

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

[7] 吳芬.平面域Delaunay三角剖分新加密算法[J].計(jì)算機(jī)與現(xiàn)代化，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] 田家恒.關(guān)于優(yōu)化三角網(wǎng)算法的地形建模BIM技術(shù)研究[J].四川建筑，2021（S1）：69-72.

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

[12] 王漢財(cái)，劉書(shū)華，金銀玉.DEM制作中基于ArcGIS平臺(tái)處理平三角的方法探究[J].長(zhǎng)春工程學(xué)院學(xué)報(bào)（自然科學(xué)版），2021（3）：52-55，103.

[13] 鄧曙光，鄭智華，敖四芽，等.上下掃描線的Delaunay三角剖分算法[J].測(cè)繪科學(xué)，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] 尤磊，唐守正，宋新宇.以優(yōu)先點(diǎn)為中心的 Delaunay三角網(wǎng)生長(zhǎng)算法[J].中國(guó)圖象圖形學(xué)報(bào)，2016（1）：60-68.