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

有效

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

技術領域

本發明涉及一種面向海量點云數據的基于矩形拼合的Delaunay三角網并行構網方法，屬于信息處理技術領域。

背景技術

二維平面域內任意離散點集的不規則三角網構建是GIS數據表達、管理、集成和可視化的一項重要內容，也是地學分析、計算機視覺等相關領域的一項重要技術。在眾多三角網中，Delaunay三角網比較特殊，具有空圓特性和最大最小角特性，保證了Delaunay三角網中不會出現過于狹長的三角形，使得三角網的構建更加合理與準確。

Delaunay三角網特有的優點使其生成算法得到了較多的研究，目前常見的構建Delaunay三角網的方法有逐點插入法、生長法及掃描線算法。逐點插入法和生長法是較早提出的Delaunay三角網算法，這兩種算法思路簡單，算法實現較為容易，但算法效率相對較低，只能滿足對算法速度要求不高的場合，這在一定程度上限制了它的應用性。掃描線算法作為較經典的Delaunay三角網生成算法，與常見插入法和生長法相比較大地提升了算法性能，一般情況下都能達到O(NlgN)的時間復雜度，由于其較高的構網效率及較好的魯棒性，在一些工程及GIS相關領域中得到了推廣應用。

分治算法作為提升構網效率的一種有效策略也被廣泛地用來生成Delaunay三角網，其基本思想是：將離散點集合按照一定的規則從空間域劃分為多個子集合，在各個子集合中生成獨立的小范圍Delaunay三角網，最后完成子網間的合并，構成整體的Delaunay三角網。

但是因為每個分組子集生成的Delaunay三角網外邊界是一個凸包，在現有的子網合并算法中，通常是基于子網間的凸包進行合并，以凸包的上頂點和下頂點為基礎，提取相鄰凸包之間的底線和頂線，即合并的起始線與終止線，合并過程中伴隨著三角形的刪除與生成。由于凸包邊界形態復雜，這類合并算法的處理需要較為細致，較容易產生裂縫和重疊三角形而導致最終構網無法順利完成。

發明內容

本發明解決的技術問題是：提出一種面向海量點云數據的基于矩形拼合的Delaunay三角網并行構網方法，可以避免三角子網拼合過程中產生裂縫和重疊三角形，簡化Delaunay三角子網的拼合過程，從而提高Delaunay三角網構網的效率。

為了解決上述技術問題，本發明提出的技術方案是：一種面向海量點云數據的基于矩形拼合的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，直到待處理邊界點集中最后一點結束。