[發(fā)明專利]一種含邊拓撲信息的不規(guī)則三角網(wǎng)弧掃式構(gòu)建方案

無效

• 申請?zhí)枺?/td>: 201110114586.0
• 申請日: 2011-05-05
• 公開（公告）號: CN102193998A
• 公開（公告）日: 2011-09-21
• 發(fā)明（設(shè)計）人: 劉永和;王燕平;馮錦明;郭維棟;趙彥琦
• 申請（專利權(quán)）人: 河南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 安陽市智浩專利代理事務所 41116
• 代理人: 張智和

技術(shù)領(lǐng)域

本發(fā)明涉及地理信息系統(tǒng)(GIS)以及激光雷達(LiDAR)數(shù)據(jù)處理所需的不規(guī)則三角網(wǎng)(TIN)的構(gòu)建技術(shù)，尤其是含有邊信息的不規(guī)則三角網(wǎng)的快速構(gòu)建技術(shù)。

背景技術(shù)

不規(guī)則三角網(wǎng)是GIS領(lǐng)域中一種重要的數(shù)字高程模型，由于它不受分辨率的限制，數(shù)據(jù)冗余度低，便于三維圖形的繪制，在地形可視化、水文模擬模型領(lǐng)域具有廣泛的應用前景。目前不規(guī)則三角網(wǎng)采用的數(shù)據(jù)結(jié)構(gòu)多為基于三角形記錄的結(jié)構(gòu)，而不直接包含有關(guān)邊的拓撲信息。這造成有關(guān)邊的拓撲信息需要通過一定的搜索和計算來得到，影響拓撲信息獲取的效率。而且，TIN的構(gòu)建是以Delaunay三角網(wǎng)的原理在采樣得到的平面上隨機分布的散點基礎(chǔ)上實現(xiàn)的。有關(guān)平面Delaunay三角網(wǎng)生成的方法較為豐富，但大多數(shù)主要為逐點插入法(增點發(fā))、三角網(wǎng)擴張法、分治法(或分塊法)以及掃描線法。現(xiàn)代測量手段不斷發(fā)展，TIN要面對海量數(shù)據(jù)的應用，如由LiDAR獲取的點云文件通常包含數(shù)百萬個采樣點。因此，Delaunay三角網(wǎng)生成方法的執(zhí)行效率是十分重要的。對數(shù)十萬至數(shù)百萬個點的應用，傳統(tǒng)的增點法、擴張法由于構(gòu)網(wǎng)效率較低而幾乎無法使用。目前，F(xiàn)ortune的掃描線法【?Fortune,?S.,?1987.?A?sweepline?algorithm?for?Voronoi?diagrams.?Algorithmica,?2(1):?153-174.】、分治法【Dwyer,?R.,?1987.?A?faster?divide-and-conquer?algorithm?for?constructing?delaunay?triangulations.?Algorithmica,?2(1):?137-151】和Zalik的掃描線法【?Zalik,?B.,?2005.?An?efficient?sweep-line?Delaunay?triangulation?algorithm.?Computer-Aided?Design,?37(10):?1027-1038.】的執(zhí)行效率最高，但這三種方法都各有不足之處，如Fortune使用拋物線邊界來隔離已掃過的點，搜索較為復雜且計算量較大，Zalik法試圖避免三角形生成過程中狹長三角形的生成以減少優(yōu)化過程中的計算量，但考慮的問題分支變得復雜，編程較難實現(xiàn)；分治法的缺限是分塊生成的各三角網(wǎng)的合并過程較為復雜，一般難以實現(xiàn)。劉永和等【劉永和,?王燕平,?齊永安,?2008.?一種快速生成平面Delaunay三角網(wǎng)的橫向擴張法.?地球信息科學,?10(1):?20-25.】提出的橫向擴張法也屬于掃描線方法，構(gòu)網(wǎng)效率較高，但該法有幾個缺點：一是每次生成一條邊后就得為查找其反向邊而遍歷整個三角網(wǎng)外側(cè)邊界上所有邊；二是三角形優(yōu)化采用的是在聯(lián)網(wǎng)結(jié)束后的多次批量優(yōu)化方式，而沒有每構(gòu)建一個三角形就進行遞歸式優(yōu)化的方式，影響構(gòu)網(wǎng)效率；三是每次向網(wǎng)絡中增加一個點時需要從整個凸包邊界中搜索邊，仍有必要加速該搜索過程。此外，國內(nèi)外都缺少有關(guān)使用掃描線方法生成三角網(wǎng)時高效維護邊拓撲信息的方法。

發(fā)明內(nèi)容

本發(fā)明的目的是為解決現(xiàn)有Delaunay三角網(wǎng)數(shù)據(jù)結(jié)構(gòu)不含有邊信息以及現(xiàn)有掃描線方法存在的不足，而提出了一種針對含有邊拓撲信息的Delaunay三角網(wǎng)的掃描線式構(gòu)建方法。該方法不僅能夠直接維護三角形與邊之間的拓撲關(guān)系，還能夠充分利用邊信息來提高構(gòu)建效率，使其成為最快的TIN構(gòu)網(wǎng)方法之一。

本發(fā)明的技術(shù)方案包括以下步驟：

(1)定義頂點、有向邊、三角形3種數(shù)據(jù)類型，分別用三個數(shù)組存放；

(2)確定一個參考中心位置，計算所有離散點相對參考中心的距離和方位角，將待構(gòu)網(wǎng)的離散點集按照該距離從小到大升序排序；

(3)建立一個存放三角網(wǎng)外邊界邊序列的雙向循環(huán)鏈表，并建立一個根據(jù)鏈表中始點的方位角存放結(jié)點的方位角存儲桶；

(4)在排序過的點集中取最初三個點按逆時針順序連成首三角形，并將三條邊的記錄以同樣的逆時針順序存入一個雙向循環(huán)鏈表中，形成初始三角網(wǎng)外邊界；

(5)從點集中按序取下一個點，按照該點的所屬方位角，從對應的方位存儲桶開始快速找出以右側(cè)面向當前點的邊，都作為與當前點連成新三角形的基邊；

(6)將第(5)步中找出的所有基邊與當前掃描過的點構(gòu)建成為三角形，將其加入到三角形數(shù)組中，同時基邊的反向邊以及另外兩條邊(分別稱為左側(cè)邊和右側(cè)邊)，更新外邊界鏈表；