[發(fā)明專利]針對海量地形大數(shù)據(jù)點云的總分式三角網(wǎng)多線程并行生成方法

有效

• 申請?zhí)枺?/td>: 201410624511.0
• 申請日: 2014-11-07
• 公開（公告）號: CN104318035A
• 公開（公告）日: 2015-01-28
• 發(fā)明（設(shè)計）人: 韓元利;鄧振林;陳燕平;劉云東;王海松
• 申請（專利權(quán)）人: 中鐵第四勘察設(shè)計院集團有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06T17/20
• 代理公司: 武漢開元知識產(chǎn)權(quán)代理有限公司 42104
• 代理人: 黃行軍;李滿

1.一種針對海量地形大數(shù)據(jù)點云的總分式三角網(wǎng)生成方法，其特征在于，它包括如下步驟：

步驟1：對海量點云數(shù)據(jù)進行給定規(guī)模的自適應(yīng)網(wǎng)格劃分，使得每一網(wǎng)格內(nèi)的點數(shù)限定在預設(shè)的數(shù)量LN內(nèi)，LN表示網(wǎng)格的限制點數(shù)，即網(wǎng)格之間無縫無疊地覆蓋整個點云數(shù)據(jù)空間；

步驟2：對每一個網(wǎng)格內(nèi)的點按點距離網(wǎng)格中央的距離，由遠及近地進行排序，這樣網(wǎng)格內(nèi)點隊列的最后一個點就一定是距離網(wǎng)格中央最近的點，稱為中央點；將中央點移動至網(wǎng)格點隊列的最前面；

步驟3：按網(wǎng)格里包含點的數(shù)量從小到大對所有網(wǎng)格進行排序，同時標注各個網(wǎng)格中待構(gòu)模點數(shù)RN為點列隊中點的數(shù)量；

步驟4：從網(wǎng)格隊列中第一個待構(gòu)模點數(shù)RN>0的網(wǎng)格開始，依次從每一個網(wǎng)格的點隊列中取出第i個點，其中0≤i<LN，用查找插入法構(gòu)建初級的均衡的三角網(wǎng)，當網(wǎng)格中的一個點參加構(gòu)模后，該網(wǎng)格的待構(gòu)模點數(shù)RN減1；如此對所有網(wǎng)格重復操作K次，完成各個網(wǎng)格前K個點的插入法構(gòu)模，其中，1≤K<LN；

步驟5：在每一個網(wǎng)格中完成第K個點的查找插入法構(gòu)模時，同時在插入法新增加的三角形中找到一個以該網(wǎng)格中央點為頂點的三角形，作為該網(wǎng)格進行拓撲檢索的起始三角形予以記錄；

步驟6：對網(wǎng)格隊列中余下第i個點的插入，其中K<i≤LN構(gòu)模，根據(jù)標記的起始三角形，利用既有三角網(wǎng)的拓撲關(guān)系采用重心趨近方向搜索方法定位點所對應(yīng)的三角形，按插入法構(gòu)模，單個點插入后同樣在新生成的三角形中找到一個以網(wǎng)格中央點為頂點的三角形作為新的起始三角形，這樣能夠保證后續(xù)點的插入構(gòu)模效率不會因為三角網(wǎng)的增加而變低；依次對每一個網(wǎng)格完成第i點的插入構(gòu)模后再次循環(huán)完成i＝i+1個點的構(gòu)模，直至所有網(wǎng)格的所有點均參與構(gòu)模，主線程算法完成。

2.一種針對海量地形大數(shù)據(jù)點云的總分式三角網(wǎng)多線程并行生成方法，其特征在于，在權(quán)利要求1所述步驟6中，安插影響域閉合檢測機制，可適時啟動獨立線程對子網(wǎng)格進行并行構(gòu)模，包括如下步驟：

步驟7：在步驟6網(wǎng)格的第i點插入過程完成后，對該網(wǎng)格進行影響域閉合檢測判斷，判斷方法為：

檢索以網(wǎng)格中央點為頂點的所有三角形，如果三角形鄰接三角形的所有頂點均位于本網(wǎng)格內(nèi)，可認為后續(xù)插值點，即i＝i+1個點的影響域在網(wǎng)格區(qū)域內(nèi)閉合，且不存在與其它網(wǎng)格三角形的共享并發(fā)沖突，因而可以采用一個獨立的線程對余下所有插值點進行獨立插入法構(gòu)網(wǎng),進入步驟8啟動一個新線程對網(wǎng)格余下點進行獨立構(gòu)模；

步驟8：將以中央點為頂點的所有三角形及其鄰接三角形，作為網(wǎng)格的私有初始三角形，連同后續(xù)插值點交由獨立的插入法構(gòu)網(wǎng)程序完成建模操作，獨立線程的數(shù)據(jù)來源均由網(wǎng)格私有，外圍拓撲三角形以共享訪問方式共享給所有獨立線程，獨立線程起動后，待構(gòu)模點數(shù)RN＝0，不再同時參加步驟6的檢索插值過程；

步驟9：針對海量地形大數(shù)據(jù)點云的總分式三角網(wǎng)多線程并行生成算法處理結(jié)束的標志為步驟6的所有網(wǎng)格中的所有點均插入處理完成并多線程隊列同時為空。

3.根據(jù)權(quán)利要求1所述的針對海量地形大數(shù)據(jù)點云的總分式三角網(wǎng)多線程并行生成方法，其特征在于：步驟6中重心趨近方向搜索的方法為，從網(wǎng)格的起始三角形出發(fā)，對臨接的三角形，分別判斷其重心到插值點的距離，選擇距離最近的三角形作為新的出發(fā)三角形，如此類推反復進行，直至該最近距離最小并維持不變時，可認定最終得到的三角形就是包含插值點的三角形，作為拓撲檢索影響域的起始三角形。

4.根據(jù)權(quán)利要求1所述的針對海量地形大數(shù)據(jù)點云的總分式三角網(wǎng)多線程并行生成方法，其特征在于：所述步驟4中的K的取值為4或5或6。