[發明專利]面向海量點云數據的基于矩形拼合的Delaunay三角網并行構網方法

有效

• 申請號: 201310003742.5
• 申請日: 2013-01-06
• 公開（公告）號: CN103092933A
• 公開（公告）日: 2013-05-08
• 發明（設計）人: 王結臣;芮一康;伍鐘潔;陶偉東;倪皓晨
• 申請（專利權）人: 南京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京同澤專利事務所(特殊普通合伙) 32245
• 代理人: 石敏

1.一種面向海量點云數據的基于矩形拼合的Delaunay三角網并行構網方法，包括以下步驟:

第一步、對平面空間進行矩形劃分得到若干互相拼接的矩形區域，將落在同一矩形區域內的所有點作為該矩形區域的子點集合，在劃分的矩形頂點處插入角點，并將該角點添加到與其相鄰的矩形區域的子點集合內；

第二步、分別對添加角點后的子點集合構建Delaunay三角子網；

第三步、利用每個矩形區域的子點集合的四個角點將所有Delaunay三角子網進行拼接，得到整個平面空間的Delaunay三角網；

第四步、從Delaunay三角網中刪除所述第一步中添加的角點以及與所述角點相關的Delaunay三角形；

第五步、對Delaunay三角網進行優化，完成平面空間的Delaunay三角網構網；其中對Delaunay三角網進行優化的方法如下：

若刪除的角點位于Delaunay三角網內部，則尋找與所述角點組成Delaunay三角形邊的頂點，順次連接這些頂點形成封閉的多邊形，并對該多邊形進行Delaunay三角剖分；

若刪除的角點位于Delaunay三角網邊界上，按照順時針或逆時針方向依次刪除邊界上插入的角點，尋找與所述邊界插入的角點組成Delaunay三角形邊的頂點，構成待處理邊界點集，并執行以下步驟：

A、任取待處理邊界點集上的一點為起始點；

B、從起始點開始取待處理邊界點集中的連續三點；

C、若果以起始點和第二點形成的線段以及第二點和第三點形成的線段之間的夾角朝向Delaunay三角網的外側，則連接起始點和第三點，這三點形成一個Delaunay三角形，并轉至步驟D，否則執行步驟E；

D、以第三點為第二點，待處理邊界點集中的下一點為第三點，重復執行步驟C；

E、以待處理邊界點集的下一點為起始點，重復執行步驟B，直到待處理邊界點集中最后一點結束。

2.根據權利要求1所述的面向海量點云數據的基于矩形拼合的Delaunay三角網并行構網方法，其特征在于，以平面空間的矩形分片為基礎，采用主從模式，對第一步到第五步進行并行化處理，具體方法為：

①主機按照給定的分裂次數將平面空間進行矩形劃分，在劃分的矩形頂點處插入角點，并將該角點加入到與其相鄰矩形區域的子點集合內；

②對于空閑的從處理機，主機通過網絡通信為其分配一個子點集合，在從處理機上進行Delaunay子三角網的計算，主處理機監聽其運行結果；

③從處理機計算完畢，主處理機接收來自從處理機上的運算結果，若主處理機上還有未分配的子點集合，則繼續給當前從處理機分配數據處理任務；

④若所有子點集合已經分配完成，且都通過從處理機運算完畢，則主處理機進行Delaunay三角子網的合并計算。

3.根據權利要求1所述的面向海量點云數據的基于矩形拼合的Delaunay三角網并行構網方法，其特征在于，第一步中，使用基于柵格統計和二叉樹的自適應矩形分片方法對平面空間進行矩形劃分，具體方法如下：

1）把平面空間劃分為M*N的柵格，對數據點集進行遍歷，計算每個數據點所屬柵格的行列號，并統計每個柵格內的數據點的數量，如果數據點恰好落在柵格線上，則取上側相鄰柵格的行號為該數據點所屬柵格的行號，取右側相鄰柵格的列號為該數據點所屬柵格的列號；

2）若M>N，則在X方向上對列進行檢索，當前K列內的總數據點數達到平面空間點集數量的一半時，將平面空間在K列折半對分成兩個矩形，同時將M減半；若M<N，則在Y方向上對行進行檢索，當前L行內的總點數達到點集數量的一半時，將平面空間在L行折半對分成兩個矩形，同時將N減半；

3）對步驟2)折半對分后的所有矩形使用如步驟2)同樣的方法進一步折半對分，直到達到所需要的塊數。

4.根據權利要求1所述的面向海量點云數據的基于矩形拼合的Delaunay三角網并行構網方法，其特征在于，第二步中，對添加角點后的子點集合使用經典的掃描線算法構建Delaunay三角子網。