李學(xué)相　彭崇高

摘要： 為有效解決激光盤煤中三維建模的算法效率問題，提出一種基于Delaunay三角剖分的改良算法。該算法在處理離散點(diǎn)生成凸殼和形成三角網(wǎng)時(shí)的方法，凸殼生成采用最高點(diǎn)相連的辦法，三角網(wǎng)的形成采用延伸法，使得生成凸殼所需遍歷點(diǎn)的個(gè)數(shù)和三角網(wǎng)生成所需時(shí)間減少，并找到該算法的不足之處。最后介紹了改進(jìn)的算法在激光盤煤系統(tǒng)中的應(yīng)用，通過改進(jìn)的算法建立的模型計(jì)算煤堆的體積。通過實(shí)驗(yàn)結(jié)果分析表明，改進(jìn)的算法執(zhí)行的效率有了很大的提升。

關(guān)鍵詞：激光盤媒；三維模型；三角剖分；延伸法；凸殼

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）28-0174-03

Research on 3D Modeling Algorithm Based On Laser Coal Stocktaking

LI Xue-xiang， PENG Chong-gao

（College of Software Technology， Zhengzhou University， Zhengzhou Henan 450000， China）

Abstract： To solve the problem of the efficiency of three-modeling in laser disc coal effectively， put forward an improved algorithm based on Delaunay triangle subdivision. The algorithm in dealing with discrete points generated convex hull and formation of triangulation method， convex hull generated the highest point is linked together， the formation of the triangulation using extension method， decreases the number of traverse points needed for generating convex hull and time needed for triangular mesh generation， and find the shortcoming of the algorithm. Finally introduces the improved algorithm in the application of laser disc coal system， by improving the algorithm model of calculating the volume of the coal. By analyzing the experimental results show that the improved algorithm execution efficiency has a great improvement.

Key words： Laser coal stocktaking； three-dimensional model； triangulation； extension method； convex hull

1 前言

把Delaunay三角網(wǎng)的特性應(yīng)用到實(shí)際環(huán)境中是當(dāng)今社會(huì)各行各業(yè)的熱潮。但是由于該算法易于實(shí)現(xiàn)，且時(shí)間復(fù)雜度高，所以還是有很多改良版的三角網(wǎng)出現(xiàn)。在此算法的基礎(chǔ)上，產(chǎn)生很多種新算法：基于文獻(xiàn)[1]Sloan算法的效率是比較高的，但是該算法僅對(duì)于處理平面散亂的點(diǎn)集，且處理的程序比較復(fù)雜。再后來Huang和Sihih對(duì)Sloan算法進(jìn)行了改進(jìn)文獻(xiàn)[2]；Guibas也對(duì)進(jìn)行改進(jìn)，即DAG（directed acyclic graph）此算法可以實(shí)現(xiàn)對(duì)點(diǎn)在幾何圖形中的定位搜索，時(shí)間復(fù)雜度達(dá)到[Ologn]，但由于數(shù)據(jù)占用了大量的存儲(chǔ)空間，算法也不夠簡(jiǎn)潔。還有一些相關(guān)算法，如金字塔算法文獻(xiàn)[3]、基于Voronoi圖的新型幾何插值文獻(xiàn)[4]的等都是非常有效的。在此基礎(chǔ)上，本文提出了一種改進(jìn)的算法，并介紹改算法激光盤煤系統(tǒng)中得以應(yīng)用。傳統(tǒng)的激光盤煤系統(tǒng)：以激光掃描儀配以角度測(cè)量實(shí)現(xiàn)煤堆表面有限點(diǎn)的二維空間位置坐標(biāo)的測(cè)量。此后改進(jìn)的設(shè)備中，我們還必須用編碼器和PLC數(shù)據(jù)采集機(jī)同激光掃描儀一起使用，才可以得到點(diǎn)的三維空間坐標(biāo)信息。最后以空間點(diǎn)信息建模，并計(jì)算出煤堆的體積，并可以對(duì)煤堆進(jìn)行一些分割、合并的操作。以此方便對(duì)煤的使用進(jìn)行調(diào)配。

算法的基本思想是，先通過處理得到的點(diǎn)云數(shù)據(jù)，通過點(diǎn)數(shù)據(jù)建立三維模型，再對(duì)模型進(jìn)行一些相對(duì)以實(shí)際工作中的一些操作。而算法實(shí)現(xiàn)的核心都是在于尋找形成三角形的第三點(diǎn)做工作。

2 點(diǎn)集的處理

初始化的點(diǎn)云數(shù)據(jù)A數(shù)組PAY、點(diǎn)云A的鏈表存放PLT、生成的三角形鏈表存放TLT、Delaunay三角剖分后點(diǎn)A的鏈表PLT、三角形數(shù)TCT=0。

2.1凸殼的生成

生成簡(jiǎn)單的凸殼如圖1所示。改進(jìn)的凸殼生成算法最高點(diǎn)相連的方法步驟如下：

步驟1. 先在點(diǎn)云數(shù)據(jù)A中，求出橫坐標(biāo)最大和最小值與縱坐標(biāo)最大和最小值，分別為[xmax]、 [xmin] 、[ymax]、 [ymin]。如圖1.所示可有[p0（xmin，y0）]，[p4（xmax，y4）]，由線段[p0p4]作為劃分線，上下部分又分為[K]個(gè)小區(qū)間，并從左到右編號(hào)從1到[K]，[K]的取值為取整（是一個(gè)由經(jīng)驗(yàn)決定大小的數(shù)）。

步驟2. 判斷點(diǎn)是否在線段[p0p4]上。在圖1中可以得到[S?=p5，p6，p7，p8，p9，p13，p14]。從左和右雙向判斷每個(gè)小區(qū)間的點(diǎn)[y]坐標(biāo)的最大值[pymax]，（這里只描述從左方向開始）并連接點(diǎn)[p0pymax]。由兩點(diǎn)之間的線段公式

可判斷點(diǎn)是否在線段[p0pymax]之上，如不在則此小區(qū)間判斷完畢。

步驟 3. 如步驟2中存在點(diǎn)在線段之上，則把線段[p0pymax]之上的點(diǎn)從新找出縱坐標(biāo)[y]最大點(diǎn)并連接點(diǎn)，此時(shí)用連接線段的點(diǎn)作為起點(diǎn)。，重新開始步驟2和步驟3，直到?jīng)]點(diǎn)在[p0pymax]線段之上。重復(fù)操作直到判斷到點(diǎn)集的最高點(diǎn)完畢如圖2。

步驟 4. 在線段[p0p4]下方的點(diǎn)，[S?=p1，p2，p3，p10，p11，p12，p15]從左和右雙向同時(shí)判斷每個(gè)小區(qū)間[y]坐標(biāo)的最小值[pymin]。（這里只描述從左方向開始）并連接[p0pymin]。判斷點(diǎn)是否在[p0pymin]之下，如不在則此小區(qū)間判斷完畢。

步驟 5. 如步驟4中存在點(diǎn)在線段之下，則把線段[p0pymin]之下的點(diǎn)從新找出縱坐標(biāo)[y]最小的點(diǎn)并連接，此時(shí)用線段的端點(diǎn)作為起點(diǎn)。重新開始步驟4和步驟5，直到?jīng)]有點(diǎn)在線段[p0pymin]之下。每個(gè)小區(qū)間重復(fù)操作到點(diǎn)集的最低點(diǎn)完畢。

步驟 6. 以上步驟連成的點(diǎn)就是凸殼的邊界點(diǎn)，邊成線就是凸殼。按以上步驟順時(shí)針將邊存到數(shù)組PLT中。

該算法存在如果在點(diǎn)數(shù)比較少的時(shí)候，形成凸殼的時(shí)間也不會(huì)有很大的減少，甚至有可能會(huì)增加。但當(dāng)點(diǎn)數(shù)達(dá)到一定量時(shí)候，形成的時(shí)間肯定會(huì)減少。

2.2 Delaunay三角網(wǎng)生成

形成三角網(wǎng)的延伸法，以凸殼上的邊為種子邊，尋找第三點(diǎn)以邊形成三角形，將所有的邊同時(shí)判斷產(chǎn)生三角形，生成三角形所構(gòu)成的邊，再同時(shí)進(jìn)行下一個(gè)三角形的判斷，以此循環(huán)，直到最后一個(gè)點(diǎn)。步驟如下：

步驟 1. 以生成凸殼的邊為種子擴(kuò)展邊，將所有的邊并行判斷。以一條邊為例，如圖3中的[p0p7]，在鏈表PAY中尋找點(diǎn)[p13]，使角[p0p13p7]最大，此時(shí)生成三角形[p0p13p7]。以此類推，逆時(shí)針遍歷完整個(gè)凸殼的邊。得到的三角形存放在TLT.

步驟 2. 邊的使用。在完成步驟1時(shí)，將鏈表PLT清空，把構(gòu)成三角形所形成的新邊加入鏈表。

步驟3擴(kuò)展三角形。重新以邊鏈表為起始開始以步驟1方法判斷。如圖3所示：以[p1p13]為一邊，在鏈表PAY中尋找點(diǎn)[p16]，以此類推，直至最后一點(diǎn)。在第二步驟形成的邊鏈表中，尋找第三點(diǎn)的過程，需要把形成邊的邊界點(diǎn)加入到第三點(diǎn)的尋找過程中，如邊[p7p8]與邊界點(diǎn)[p13]。最后得到的三角形存放在TLT。

新三角形生成需加入到三角形鏈表TLT中，并且TCT次數(shù)加1。當(dāng)點(diǎn)成為封閉點(diǎn)和半封閉點(diǎn)時(shí)候。刪除封閉點(diǎn)和半封閉點(diǎn)，可加快第三點(diǎn)的搜索。

由文獻(xiàn)[5]和[6]可以判斷封閉點(diǎn)和半封閉邊界點(diǎn)。判斷構(gòu)成三角形的點(diǎn)，如果沒有凸殼上的點(diǎn)，則該點(diǎn)是封閉點(diǎn)。如圖3中的[p11]。當(dāng)該點(diǎn)構(gòu)成三角形，如該點(diǎn)在凸殼上時(shí)候，則該點(diǎn)是半封閉點(diǎn)，如圖3中的[p1]、[p2]。

步驟 4. 三角形鏈表TLT即為所求的三角剖分。

由文獻(xiàn)[7的知Delaunay三角網(wǎng)的判斷方法：

1）在形成的三角網(wǎng)格中，任意一個(gè)三角形的外接圓都不包含任何其他的點(diǎn)。如圖4。

2）在構(gòu)成的三角網(wǎng)格的所有點(diǎn)，Delaunay三角剖分所形成的三角形有最小角最大的特性。就是指一種相鄰的兩個(gè)三角形形成凸四邊形的時(shí)候，在對(duì)角線交換時(shí)六個(gè)內(nèi)角的最小角不再增大。如圖5.

判斷三角形鏈表TLT中的三角形的特性，是符合上述的條件。

2.3三維重建

煤堆體積分析的是一種空間三維分析，一般情況下，對(duì)三維模型的分析，都是在數(shù)字高程模型（Digital Elevation Model 簡(jiǎn)稱DEM）上進(jìn)行的。如果生成的DEM在精度和密度上都符合生產(chǎn)時(shí)的要求，這樣對(duì)具體事務(wù)的三維分析便可很容易的實(shí)現(xiàn)。而最常用的一種DEM是TIN DEM。

所謂的TIN結(jié)構(gòu)的三角形在平面結(jié)構(gòu)的投影是不規(guī)則，然而它在不規(guī)則的基礎(chǔ)上它也有一定的規(guī)則可循：它是一個(gè)非重疊覆蓋的區(qū)域，且每一個(gè)三角形的形成必定有其特在的特點(diǎn)和符合構(gòu)建時(shí)候的要求。

由煤場(chǎng)的掃描的點(diǎn)數(shù)據(jù)，通過上述的算法進(jìn)行計(jì)算，我們可以得到在三維空間的一個(gè)煤堆的模型，在通過對(duì)煤堆的一些處理，就可以得到準(zhǔn)確的煤堆模型。并且這個(gè)算法處理的模型中的構(gòu)建也是符合Delaunay剖分的所以特性的。

而在煤場(chǎng)的建模中，計(jì)算體積時(shí)，因?yàn)榛鶖?shù)都是以噸位單位的，故不需要涉及太精密的計(jì)算，有這種精度的模型，完全可以符合對(duì)煤的調(diào)度。

2.4 體積計(jì)算

改進(jìn)的算法形成的三角網(wǎng)格的體積，可以由單個(gè)三菱柱體積計(jì)算累加所得。三菱柱的投影面積（是指三菱柱在水平面投影成三角形的面積）[Si]，可計(jì)算此面積的海倫計(jì)算公式為：

其中[p]為投影三角形的周長(zhǎng)，[ΔX]、[ΔY]是兩頂點(diǎn)之間[X]、[Y]方向的坐標(biāo)差。

現(xiàn)由單個(gè)三菱柱體積可得，進(jìn)行體積求和，則可以求出整個(gè)圖形的體積。

計(jì)算公式為：

[Zi1]、[Zi2]、[Zi3]表示第i個(gè)TIN的規(guī)則格網(wǎng)的點(diǎn)的高程。[Si]為第i個(gè)三角形或規(guī)則格網(wǎng)的投影面積。

3 在激光盤煤系統(tǒng)中的應(yīng)用

隨著科技的進(jìn)步，大型電力集團(tuán)公司對(duì)能耗低，污染控制管理水平提高有了更高的認(rèn)識(shí)，但還遠(yuǎn)遠(yuǎn)沒達(dá)到對(duì)資源利用最大化的標(biāo)準(zhǔn)。且時(shí)至今日， 大多數(shù)火力發(fā)電集團(tuán)公司對(duì)料場(chǎng)存料的管理，仍然沿襲百年的傳統(tǒng)--人工盤存。故而急需一種現(xiàn)代化的激光盤煤工具，來實(shí)現(xiàn)對(duì)煤的更好調(diào)配使用。

激光盤煤的種類眾多。由于具體配置和激光盤煤的原理不同，可分為幾大類，十多種具體的模式。比如：全自動(dòng)、斗輪機(jī)（固定式）、多功能等。

我們?cè)谕ㄟ^設(shè)備得到煤堆的點(diǎn)數(shù)據(jù)后，通過上述的改良算法，創(chuàng)建一個(gè)煤堆的三維模型和計(jì)算模型的體積，進(jìn)而配以煤堆的密度求出煤的質(zhì)量；從上面描述，我們可以看到，在影響最后結(jié)果的準(zhǔn)確性有以下幾個(gè)因素：點(diǎn)測(cè)量的精度，創(chuàng)建模型的精度。我們?cè)u(píng)價(jià)一款現(xiàn)代化的激光盤煤系統(tǒng)好壞的標(biāo)準(zhǔn)就是以此為依據(jù)。當(dāng)然，設(shè)備可靠穩(wěn)定，使用的方便，效率也必須提前考慮。還有最后得到煤堆體積的誤差大小也應(yīng)該考慮其中，一般我們有一個(gè)可接受的誤差范圍5%左右，這個(gè)也是一個(gè)重要評(píng)判的標(biāo)準(zhǔn)。

通過數(shù)據(jù)采集，將數(shù)據(jù)轉(zhuǎn)換成三維坐標(biāo)形式的數(shù)據(jù)。處理生成好的三維坐標(biāo)數(shù)據(jù)，首先把三維點(diǎn)投影到二維上，即此時(shí)先不管Z軸坐標(biāo)，然后通過上面描述的Delaunay算法，得到一系列三角形。此時(shí)便可以得到在平面的三角網(wǎng)。

由這些三角網(wǎng)關(guān)系，再構(gòu)建體積計(jì)算模型。網(wǎng)格中的三角形，每個(gè)頂點(diǎn)與其相應(yīng)的空間三維點(diǎn)，即此時(shí)要處理Z軸坐標(biāo)，構(gòu)成三菱柱體。故由平面的三角網(wǎng)，可得到以其對(duì)應(yīng)的三菱柱體群，便可構(gòu)成三維圖形。所有的三菱柱體的體積便可以看成煤場(chǎng)體積的一個(gè)近似結(jié)果。

這就是激光盤煤系統(tǒng)中對(duì)一煤堆的三維建模并且求得體積的應(yīng)用。

4 實(shí)例

通過在煤場(chǎng)中取得的一些點(diǎn)數(shù)據(jù)，用于建立模型，通過生成時(shí)所需要的時(shí)間如表格1可以得出，改進(jìn)的算法可以相對(duì)的節(jié)約時(shí)間，大大提高了運(yùn)行的效率。

5結(jié)語

本文提出了一種改良的三維建模算法。通過該算法在激光盤煤系統(tǒng)中的應(yīng)用，可建立煤堆的三維模型，和需要的煤堆體積和質(zhì)量并可對(duì)煤堆進(jìn)行分割、合并等操作。這樣具體應(yīng)用中好方便對(duì)煤的調(diào)配。

同時(shí)該算法也存在不足，對(duì)煤堆掃描得到的點(diǎn)數(shù)據(jù)，要求比較嚴(yán)格。并且存在著一些影響計(jì)算結(jié)果準(zhǔn)確性的因數(shù)。同時(shí)體積的計(jì)算跟掃描點(diǎn)有關(guān)，點(diǎn)越多體積得到的越精確。這樣也增加了計(jì)算量，影響計(jì)算速度，并且增加的掃描儀的工作。

在實(shí)際應(yīng)用中，還存在一些有光線產(chǎn)生的一些問題，如反射性不均勻、物面傾斜、機(jī)械掃描誤差、現(xiàn)場(chǎng)大功率環(huán)境等等因數(shù)的影響。

因此，隨著科技的進(jìn)步，激光盤煤系統(tǒng)還需進(jìn)一步的研究和改進(jìn)。

參考文獻(xiàn)：

[1] 楊欽.限定Delaunay三角網(wǎng)剖分技術(shù)[M].北京：電子工業(yè)出版社，2005.

[2]Sloan S W.A fast algorithm constructing Delaunay triangulations in the plane[J]. Adv Eng Softw Workstat， 1987，9（1）；34-35

[3] 張忠武，吳信才.平面海量散亂點(diǎn)集凸殼算法[J].計(jì)算機(jī)工程，2009，35（9）：43-45.

[4] 周小平，周瑞忠.基于Voronoi圖的新型幾何插值及其與傳統(tǒng)代數(shù)插值方法的比較[J].巖石力學(xué)與工程學(xué)報(bào)，2005（1）.

[5] 孫繼忠，胡艷，馬永強(qiáng) ，基于Delaunay三角解剖分生成Voronoi圖算法[J].計(jì)算機(jī)應(yīng)用，2010，30（1）.

[6] 凌海濱， 吳兵. 改進(jìn)的自連接Delaunay三角網(wǎng)生成算法[J].計(jì)算機(jī)應(yīng)用，1999，19（12）：10-12.

[7] 袁洋.激光盤煤系統(tǒng)的研究[D]. 北京： 華北電力大學(xué)， 2009.