無(wú)人機(jī)激光點(diǎn)云礦區(qū)土方量計(jì)算系統(tǒng)的設(shè)計(jì)與開(kāi)發(fā)

柳克松

（中煤科工集團(tuán)沈陽(yáng)設(shè)計(jì)研究院有限公司，遼寧 沈陽(yáng) 110000）

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

圖1 技術(shù)路線

1 系統(tǒng)設(shè)計(jì)與土方量計(jì)算

1.1 系統(tǒng)設(shè)計(jì)

在當(dāng)前的系統(tǒng)中，創(chuàng)建了格網(wǎng)模型和不規(guī)則三角網(wǎng)模型并根據(jù)設(shè)計(jì)網(wǎng)格、特征點(diǎn)展點(diǎn)圖以及測(cè)區(qū)邊界等，運(yùn)行土方量計(jì)算程序，將某個(gè)區(qū)域中的挖方及填方量算出來(lái)，同時(shí)還可根據(jù)土方量填挖平衡的相關(guān)原則計(jì)算區(qū)域內(nèi)設(shè)計(jì)的平整高程，同時(shí)生成土方計(jì)算數(shù)據(jù)文件、指定范圍總面積及挖方面積的土方量和填方面積土方量。

為了實(shí)現(xiàn)既定的系統(tǒng)功能，本軟件設(shè)計(jì)了DTM 生成邊界模塊和土方量計(jì)算模塊，而且基于2 個(gè)主模塊將一些更加具體的算法集中應(yīng)用到系統(tǒng)中，由此達(dá)到了設(shè)計(jì)目標(biāo)。系統(tǒng)從數(shù)據(jù)輸入、計(jì)算處理到結(jié)果輸出，結(jié)構(gòu)清晰、功能完善。

遍歷順序是將三角形的數(shù)據(jù)讀取后，對(duì)三角形的每個(gè)頂點(diǎn)進(jìn)行遍歷，目的是確定目前的頂點(diǎn)是否在紅黑二叉樹(shù)中，如果不在樹(shù)中，那么就將此頂點(diǎn)按照紅黑二叉樹(shù)的規(guī)則加入到二叉樹(shù)中，并按照自然數(shù)的順序?yàn)楸闅v的每個(gè)頂點(diǎn)排序，選擇紅黑二叉樹(shù)的原因?yàn)榧t黑二叉樹(shù)在存儲(chǔ)數(shù)據(jù)時(shí)不會(huì)出現(xiàn)重復(fù)。例如存入第一個(gè)三角形后，再存入第二個(gè)三角形時(shí)，第二個(gè)三角形中有2 個(gè)點(diǎn)是第一個(gè)三角形中的，這時(shí)二叉樹(shù)會(huì)放棄這2 個(gè)點(diǎn)，因此，原本需要存入6 個(gè)點(diǎn)，這時(shí)只需要存入4 個(gè)點(diǎn)就可以將三角形的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)下來(lái)，大大減少了內(nèi)存空間，加快了計(jì)算速度。

為了把邊界提取出來(lái)，需要DTM 三角網(wǎng)中每個(gè)點(diǎn)的坐標(biāo)，每個(gè)三角形和其周邊三角形的序號(hào)，將三角形中每條邊序號(hào)、三角形序號(hào)及與這條邊相鄰的三角形序號(hào)作為一組數(shù)據(jù)進(jìn)行臨時(shí)保存。因此根據(jù)這個(gè)要求，首先建立指針類型數(shù)據(jù)結(jié)構(gòu)Pointlist 用來(lái)存平面坐標(biāo)（x，y），指針類型數(shù)據(jù)結(jié)構(gòu)Pointattributrlist 用來(lái)存高程（z），指針類型數(shù)據(jù)結(jié)構(gòu)Trianglelist 用來(lái)存三角形的3 個(gè)頂點(diǎn)（由點(diǎn)在紅黑二叉樹(shù)中的序號(hào)組成），最后指針類型數(shù)據(jù)結(jié)構(gòu)neighborlist 用來(lái)存三角形每條邊的信息（由三角形頂點(diǎn)構(gòu)成，序號(hào)小的在前）。接下來(lái)再次對(duì)DTM 模型中所有三角形進(jìn)行遍歷，將每個(gè)三角形的頂點(diǎn)在紅黑二叉樹(shù)中進(jìn)行遍歷，將遍歷得到的結(jié)果作為將要存入數(shù)據(jù)結(jié)構(gòu)中的位置，分別將平面坐標(biāo)、高程、頂點(diǎn)信息存儲(chǔ)到不同的數(shù)據(jù)結(jié)構(gòu)中。

將三角形頂點(diǎn)兩兩組成一條邊，對(duì)每條邊進(jìn)行遍歷，查找所在邊的左右三角形序號(hào)，并將邊及左右三角形序號(hào)存放在之前創(chuàng)建的map 數(shù)據(jù)結(jié)構(gòu)中。這步是將每2 個(gè)點(diǎn)之間組成一條邊，遍歷每條邊是否在map中，其中map 中前一個(gè)要素edge 由邊構(gòu)成，后一要素是把這條邊的左右鄰居存入進(jìn)去，如果這條邊的左邊沒(méi)有鄰居就用﹣1 來(lái)表示。這條邊的右邊代表當(dāng)前三角形序號(hào)。將當(dāng)前三角形的序號(hào)存放進(jìn)去，這一步驟目的是將這條邊的信息及它的左右鄰居進(jìn)行存儲(chǔ)。

對(duì)存入的邊進(jìn)行遍歷，尋找除對(duì)應(yīng)邊所在頂點(diǎn)外另一頂點(diǎn)的序號(hào)，并將邊及頂點(diǎn)序號(hào)存放在最開(kāi)始定義的數(shù)據(jù)結(jié)構(gòu)中。

1.2 土方量計(jì)算

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

在利用不規(guī)則三角形模型進(jìn)行土地均衡平整及土方量計(jì)算時(shí)，要依據(jù)圈定邊界區(qū)域內(nèi)的離散點(diǎn)建立出帶約束的不規(guī)則的三角網(wǎng)（TIN），這樣能夠?qū)Φ匦芜M(jìn)行更好的反映；另一方面當(dāng)?shù)匦纬霈F(xiàn)變化時(shí)也可以第一時(shí)間進(jìn)行描述，以此提高所測(cè)土方量的精度。

以下是常見(jiàn)的不規(guī)則三角形構(gòu)建方法：約束圖法、分割-合并算法、加密算法、Shell 三角化算法、兩步法及某些算法的合成算法。此次研究所使用的方法為兩步法，首先用凸包算法快速計(jì)算出無(wú)約束條件的不規(guī)則三角形的各個(gè)頂點(diǎn)坐標(biāo)，然后逐漸向DTM 中添加約束線，構(gòu)建起約束三角網(wǎng)。使用該方法時(shí)必須保證所有的約束線的節(jié)點(diǎn)都在離散數(shù)據(jù)的初始三角網(wǎng)部分，然后根據(jù)約束線與離散點(diǎn)之間的拓?fù)潢P(guān)系將約束線逐條嵌入初始三角網(wǎng)中。

本系統(tǒng)以VS 2019 為平臺(tái)，并利用C++語(yǔ)言來(lái)進(jìn)行開(kāi)發(fā)，這樣就可以在離散點(diǎn)數(shù)據(jù)的基礎(chǔ)上，利用內(nèi)插法獲得相關(guān)的不規(guī)則三角網(wǎng)數(shù)據(jù)，從而建立不規(guī)則三角網(wǎng)（ TIN ）模型。最終利用設(shè)計(jì)標(biāo)高來(lái)確定挖方量、填方量及平整區(qū)域的土方量，完成給定區(qū)域的土地均衡平整和土方量計(jì)算。

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

設(shè)計(jì)地面的DTM 模型和參考高程土方量計(jì)算與輸入模型為設(shè)計(jì)地面的DTM 模型和原地面的DTM 模型相比，步驟①和步驟②相同，步驟③中投影后的三角形平面坐標(biāo)不變，高程由原來(lái)的設(shè)計(jì)地面高程改為輸入的參考高程，最后進(jìn)行計(jì)算。

2 工程案例

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

將數(shù)據(jù)導(dǎo)入本文研發(fā)系統(tǒng)中按照步驟進(jìn)行計(jì)算，該系統(tǒng)操作結(jié)果如圖2—圖5 所示。

圖2 導(dǎo)入數(shù)據(jù)

圖5 最終生成DTM

圖3 打開(kāi)文件

圖4 計(jì)算窗口

3 總結(jié)

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