無人機激光點云礦區土方量計算系統的設計與開發

柳克松

（中煤科工集團沈陽設計研究院有限公司，遼寧 沈陽 110000）

使用無人機獲取激光點云數據，利用開發的軟件處理點云數據同時需要應用數據庫技術，以VS 2019為開發平臺，通過C++語言，根據軟件開發設計流程做出了一個基于DTM（Digital Terrain Model）的土方量計算系統，為生產管理提供了一種有效的技術手段。在研究傳統逐點插入法的基礎上，提出了一種基于紅黑二叉樹索引的改進算法，主要包括點和線的快速定位查找等功能并將其應用于DTM 的建立。分析了傳統工程土方量計算方法的優缺點，獲得了一種能夠快速計算土方量的設計方案，這種方案的基礎是建立DTM。研究結果表明，相較于傳統的斷面法與方格網法，此方法具有刻畫地形圖整體面貌與局部細節特征更加準確、作業方法效率高、計算結果精度高等優點。其技術路線如圖1 所示。

圖1 技術路線

1 系統設計與土方量計算

1.1 系統設計

在當前的系統中，創建了格網模型和不規則三角網模型并根據設計網格、特征點展點圖以及測區邊界等，運行土方量計算程序，將某個區域中的挖方及填方量算出來，同時還可根據土方量填挖平衡的相關原則計算區域內設計的平整高程，同時生成土方計算數據文件、指定范圍總面積及挖方面積的土方量和填方面積土方量。

為了實現既定的系統功能，本軟件設計了DTM 生成邊界模塊和土方量計算模塊，而且基于2 個主模塊將一些更加具體的算法集中應用到系統中，由此達到了設計目標。系統從數據輸入、計算處理到結果輸出，結構清晰、功能完善。

遍歷順序是將三角形的數據讀取后，對三角形的每個頂點進行遍歷，目的是確定目前的頂點是否在紅黑二叉樹中，如果不在樹中，那么就將此頂點按照紅黑二叉樹的規則加入到二叉樹中，并按照自然數的順序為遍歷的每個頂點排序，選擇紅黑二叉樹的原因為紅黑二叉樹在存儲數據時不會出現重復。例如存入第一個三角形后，再存入第二個三角形時，第二個三角形中有2 個點是第一個三角形中的，這時二叉樹會放棄這2 個點，因此，原本需要存入6 個點，這時只需要存入4 個點就可以將三角形的數據結構存儲下來，大大減少了內存空間，加快了計算速度。

為了把邊界提取出來，需要DTM 三角網中每個點的坐標，每個三角形和其周邊三角形的序號，將三角形中每條邊序號、三角形序號及與這條邊相鄰的三角形序號作為一組數據進行臨時保存。因此根據這個要求，首先建立指針類型數據結構Pointlist 用來存平面坐標（x，y），指針類型數據結構Pointattributrlist 用來存高程（z），指針類型數據結構Trianglelist 用來存三角形的3 個頂點（由點在紅黑二叉樹中的序號組成），最后指針類型數據結構neighborlist 用來存三角形每條邊的信息（由三角形頂點構成，序號小的在前）。接下來再次對DTM 模型中所有三角形進行遍歷，將每個三角形的頂點在紅黑二叉樹中進行遍歷，將遍歷得到的結果作為將要存入數據結構中的位置，分別將平面坐標、高程、頂點信息存儲到不同的數據結構中。

將三角形頂點兩兩組成一條邊，對每條邊進行遍歷，查找所在邊的左右三角形序號，并將邊及左右三角形序號存放在之前創建的map 數據結構中。這步是將每2 個點之間組成一條邊，遍歷每條邊是否在map中，其中map 中前一個要素edge 由邊構成，后一要素是把這條邊的左右鄰居存入進去，如果這條邊的左邊沒有鄰居就用﹣1 來表示。這條邊的右邊代表當前三角形序號。將當前三角形的序號存放進去，這一步驟目的是將這條邊的信息及它的左右鄰居進行存儲。

對存入的邊進行遍歷，尋找除對應邊所在頂點外另一頂點的序號，并將邊及頂點序號存放在最開始定義的數據結構中。

1.2 土方量計算

在構造不規則三角形格網時需要結合實際地形地貌，此外，TIN（不規則三角形格網）的每個基本單元都是不規則三角形的一個頂點坐標[1-3]。由于采樣時選取的觀測點是由地形決定的，一般為地形坡度的變換點或平面地形的轉折點，從而使得離散點在區域中呈非規則非均勻分布。正因此，使用這種方法所構建出的三角形格網肯定是不規則的，只有通過準確計算才能夠最終確定內部不規則三角形的格網數目。依據幾何學，假設一個區域內有n個離散點，那么它們可構成的互不交叉的三角形的數目最多不超過2n－5 個。在生成TIN 的過程中，還要考慮地性線、地物等的影響。為了保證格網最大限度符合實際地形，在應用中通常把地形特征線作為TIN 中三角形的邊，并在擴展TIN 時，先從地形特征線開始。因此大比例尺數字測圖的建模中大都采用三角形格網法，它避免了為內插方格網而犧牲原始測點精度的問題，從而保證了整個模型的精度[4]。

在利用不規則三角形模型進行土地均衡平整及土方量計算時，要依據圈定邊界區域內的離散點建立出帶約束的不規則的三角網（TIN），這樣能夠對地形進行更好的反映；另一方面當地形出現變化時也可以第一時間進行描述，以此提高所測土方量的精度。

以下是常見的不規則三角形構建方法：約束圖法、分割-合并算法、加密算法、Shell 三角化算法、兩步法及某些算法的合成算法。此次研究所使用的方法為兩步法，首先用凸包算法快速計算出無約束條件的不規則三角形的各個頂點坐標，然后逐漸向DTM 中添加約束線，構建起約束三角網。使用該方法時必須保證所有的約束線的節點都在離散數據的初始三角網部分，然后根據約束線與離散點之間的拓撲關系將約束線逐條嵌入初始三角網中。

本系統以VS 2019 為平臺，并利用C++語言來進行開發，這樣就可以在離散點數據的基礎上，利用內插法獲得相關的不規則三角網數據，從而建立不規則三角網（ TIN ）模型。最終利用設計標高來確定挖方量、填方量及平整區域的土方量，完成給定區域的土地均衡平整和土方量計算。

輸入模型為設計地面的DTM 模型和原地面的DTM 模型步驟如下：①對原地面的DTM 模型中每個三角形進行搜索，尋找與三角形相交的設計地面DTM模型中所有三角形外接矩形，計算相交面積。②當2個DTM 模型相交圖形為三角形時，將設計地面DTM模型中相交三角形投影到原地面DTM 模型中；當2個DTM 模型相交圖形為多邊形時，將其分割為多個三角形，再進行投影。③投影后的三角形平面坐標不變，高程由原來的設計地面高程改為原地面高程，2 個模型可以形成平面坐標相同、高程不同的立方體，達到計算填挖方體積的目的。

設計地面的DTM 模型和參考高程土方量計算與輸入模型為設計地面的DTM 模型和原地面的DTM 模型相比，步驟①和步驟②相同，步驟③中投影后的三角形平面坐標不變，高程由原來的設計地面高程改為輸入的參考高程，最后進行計算。

2 工程案例

工程區地形以剝蝕低山丘陵地貌為主，穿插丘間溝谷地、丘間谷盆地，地形總體起伏較大，山勢陡峻，主山脈走向呈北東東向，但其山麓山坡中山脊走向呈南北向或北北西向，波狀起伏較大，地面標高在160～385 m 之間：而丘間溝谷地、丘間谷盆地地形多呈“U”字形，狹長條帶狀，溝谷走向與主體山脊直垂直，呈近南北向，地表發育淺表性軟土，地面高程隨相應的低丘山麓山坡標高變化相差較大。

將數據導入本文研發系統中按照步驟進行計算，該系統操作結果如圖2—圖5 所示。

圖2 導入數據

圖5 最終生成DTM

圖3 打開文件

圖4 計算窗口

3 總結

在本軟件開發過程中，主要應用數字建模技術、數據庫技術、系統工程理論及計算機圖形學等新技術進行研究。為了克服傳統逐點插入法所存在的問題，基于原有成果，依據紅黑二叉樹法給出了一種基于網格索引的可快速定位插入點并確定影響域的改進算法設計。對于地測系統來說，驗收是其主要功能，其中包括填挖方的驗收，此外還有露天采場的驗收及掘進工程的驗收等，這些都需進行土方工程量的計算。在總結傳統工程土方量計算方法的基礎上，給出了基于DTM 的工程土方量計算方法設計，該方法主要包括生成邊界與計算土方量。由于三角網的點的檢索比矩形格網的檢索具有更高的復雜性，為了使效率得到進一步提升，提出了以網格作為其基礎的點的快速搜索算法，同時給出了相應的計算算法；在研究已有生成邊界的基礎上，給出了一種新算法，它使交點計算法得到顯著的簡化，進而使效率得到顯著提高，而且，它無需對一些特殊情況進行專門處理。其開發平臺為Visual Studio 2019，并嵌套C++編程語言，嚴格按照軟件工程技術進行了開發，最終開發出此系統用于計算工程土方量。