本文關(guān)鍵詞：一種采用流計(jì)算的Delaunay三角網(wǎng)切塊剖分算法　出處：《武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)》2017年07期 　論文類型：期刊論文

  更多相關(guān)文章： Delaunay三角剖分 時(shí)間與空間性能 切塊 流計(jì)算 非耦合區(qū)域分解模式

【摘要】：針對(duì)海量LiDAR點(diǎn)云Delaunay三角網(wǎng)剖分的時(shí)間與空間性能的矛盾問題,提出了一種采用切塊的流計(jì)算Delaunay構(gòu)網(wǎng)算法。首先利用三角網(wǎng)墻(DeWall)從點(diǎn)云上切割特定大小與形狀的獨(dú)立數(shù)據(jù)塊,避免分治算法的深度遞歸與內(nèi)存溢出;然后運(yùn)用分治算法對(duì)切塊剖分,并給出了切塊邊界錯(cuò)誤三角形刪除算法;重復(fù)上述過程完成子網(wǎng)剖分,并依據(jù)非耦合區(qū)域分解模式合并為最終三角網(wǎng)。引入流計(jì)算的思想,以進(jìn)一步提高算法的空間性能。分析與實(shí)驗(yàn)表明:該算法占用了較低內(nèi)存,并取得了接近為O(nlg(δ))(δ為一個(gè)切塊點(diǎn)數(shù),且δ≤n)的時(shí)間復(fù)雜度。
[Abstract]:To solve the problem of contradiction between time and space performance of the mass LiDAR point cloud Delaunay triangulation, is presented with a cut flow calculation algorithm of constructing Delaunay triangulation. Firstly, the wall (DeWall) independent data block cutting specific size and shape from the point cloud, can cure the depth of memory and recursive algorithm overflow; and then use the partition algorithm to cut section, and gives the cut boundary error triangle deletion algorithm; repeat the above process to complete the subnet partition, and on the basis of non coupling region decomposition model with triangulation. Finally introduced the thought of stream computing, to further improve the performance of the algorithm. The spatial analysis and experiments show that the algorithm take a low memory, and get close to O (NLG (delta) (8) as a cut point, and delta n) time complexity.

【作者單位】： 貴州大學(xué)礦業(yè)學(xué)院;中國礦業(yè)大學(xué)(北京)地球科學(xué)與測(cè)繪工程學(xué)院;核工業(yè)北京地質(zhì)研究院;
【基金】：國家自然科學(xué)基金(41171306) 高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20130023110001)~~
【分類號(hào)】：TN958.98
【正文快照】： 激光雷達(dá)能夠在短時(shí)間內(nèi)獲取大量的點(diǎn)云,并在GIS、計(jì)算機(jī)圖形學(xué)等領(lǐng)域得到了廣泛應(yīng)用,但海量LiDAR點(diǎn)云對(duì)Delaunay三角網(wǎng)剖分算法的性能提出了更高的要求[1]。傳統(tǒng)的構(gòu)網(wǎng)算法因不能同時(shí)兼顧算法的時(shí)間與空間性能,不適合較大點(diǎn)云的三角網(wǎng)剖分。目前在PC機(jī)上實(shí)現(xiàn)千萬級(jí)以上的點(diǎn)云

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 董箭;彭認(rèn)燦;鄭義東;;利用局部動(dòng)態(tài)最優(yōu)Delaunay三角網(wǎng)改進(jìn)逐點(diǎn)內(nèi)插算法[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2013年05期

2 沈晶;劉紀(jì)平;林祥國;趙榮;;集成距離變換和區(qū)域鄰接圖生成Delaunay三角網(wǎng)的方法研究[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2012年08期

3 王磊;聶玉峰;李義強(qiáng);;Delaunay四面體網(wǎng)格并行生成算法研究進(jìn)展[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2011年06期

4 吳文周;李利番;王結(jié)臣;;平面點(diǎn)集凸包Graham算法的改進(jìn)[J];測(cè)繪科學(xué);2010年06期

5 芮一康;王結(jié)臣;;Delaunay三角形構(gòu)網(wǎng)的分治掃描線算法[J];測(cè)繪學(xué)報(bào);2007年03期

6 吳宇曉,張登榮;生成Delaunay三角網(wǎng)的快速合成算法[J];浙江大學(xué)學(xué)報(bào)(理學(xué)版);2004年03期

7 胡金星,馬照亭,吳煥萍,潘懋;基于格網(wǎng)劃分的海量數(shù)據(jù)Delaunay三角剖分[J];測(cè)繪學(xué)報(bào);2004年02期

8 劉強(qiáng),李德仁;數(shù)碼城市中建筑物三維CAFM研究[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2004年01期

9 胡金星,潘懋,馬照亭,吳煥萍;高效構(gòu)建Delaunay三角網(wǎng)數(shù)字地形模型算法研究[J];北京大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年05期

10 武曉波,王世新,肖春生;一種生成Delaunay三角網(wǎng)的合成算法[J];遙感學(xué)報(bào);2000年01期

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 曹文濤;何偉;;利用TIN和高程梯度進(jìn)行高程點(diǎn)抽稀[J];測(cè)繪通報(bào);2017年05期

2 劉洋;唐好選;;針對(duì)路面建模的Delaunay三角網(wǎng)格分治算法[J];智能計(jì)算機(jī)與應(yīng)用;2017年02期

3 陳長波;劉小丁;朱紫陽;周昆;;單波束測(cè)深數(shù)據(jù)的插值精度分析[J];測(cè)繪通報(bào);2017年03期

4 張新建;;結(jié)合GDI+對(duì)分治法生成Delaunay三角網(wǎng)的改進(jìn)[J];礦山測(cè)量;2017年01期

5 馬駿;藺東杰;凌廣明;;基于海量數(shù)據(jù)的二維凸包快速生成算法[J];計(jì)算機(jī)技術(shù)與發(fā)展;2017年02期

6 劉琴琴;;平面域Delaunay三角網(wǎng)點(diǎn)定位算法研究綜述[J];電子設(shè)計(jì)工程;2017年01期

7 張春亢;趙學(xué)勝;王洪斌;;一種采用流計(jì)算的Delaunay三角網(wǎng)切塊剖分算法[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2017年07期

8 王卓識(shí);陳根良;王皓;徐勛;孔令雨;;基于誤差區(qū)域映射的并聯(lián)機(jī)構(gòu)精度設(shè)計(jì)研究[J];機(jī)械設(shè)計(jì)與研究;2016年04期

9 李必棟;閆浩文;王中輝;劉虎林;;坐標(biāo)排序的離散點(diǎn)凸包生成算法[J];測(cè)繪科學(xué);2017年02期

10 張曉蒙;陸忠華;張鑒;;三維并行約束Delaunay網(wǎng)格生成算法及實(shí)現(xiàn)[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2016年06期

【二級(jí)參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 周元峰;孫峰;王文平;汪嘉業(yè);張彩明;;基于局部修復(fù)的移動(dòng)數(shù)據(jù)點(diǎn)Delaunay三角化快速更新方法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2011年12期

2 秦志霞;沈煒;劉文昊;;二維Voronoi圖刪除任意生成點(diǎn)算法研究[J];浙江理工大學(xué)學(xué)報(bào);2010年03期

3 童曉沖;賁進(jìn);秦志遠(yuǎn);張永生;;基于全球離散網(wǎng)格框架的局部網(wǎng)格劃分[J];測(cè)繪學(xué)報(bào);2009年06期

4 劉瑩;聶玉峰;;泡泡布點(diǎn)方法及其并行性[J];計(jì)算物理;2009年06期

5 田峰敏;徐定杰;趙玉新;;一種建立海底格網(wǎng)數(shù)字高程模型的插值方法[J];中國航海;2009年03期

6 劉學(xué)軍;張平;朱瑩;;DEM坡度計(jì)算的適宜窗口分析[J];測(cè)繪學(xué)報(bào);2009年03期

7 田峰敏;徐定杰;李寧;;Delaunay三角化中特征約束細(xì)分嵌入算法[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2009年03期

8 鄭順義;鄧德彥;;基于三角網(wǎng)無縫拼接的三維重建[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2009年01期

9 賈俊濤;翟京生;孟嬋媛;申家雙;譚冀川;;基于海量多波束數(shù)據(jù)的海底地形模型的構(gòu)建與可視化[J];測(cè)繪科學(xué)技術(shù)學(xué)報(bào);2008年04期

10 梁義;陳建軍;陳立崗;鄭耀;;并行平面Delaunay網(wǎng)格生成[J];浙江大學(xué)學(xué)報(bào)(工學(xué)版);2008年04期

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 楊雅妹,賀士娟,趙德新,王志欣;基于3D Delaunay定理重構(gòu)頭模型[J];河北工業(yè)大學(xué)學(xué)報(bào);2001年06期

2 胡金星,潘懋,馬照亭,吳煥萍;高效構(gòu)建Delaunay三角網(wǎng)數(shù)字地形模型算法研究[J];北京大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年05期

3 鄧曙光;劉剛;鄒帆;;約束數(shù)據(jù)域Delaunay算法詳述及進(jìn)展[J];沈陽航空工業(yè)學(xué)院學(xué)報(bào);2005年05期

4 ;Quick Approach to Construct Constrained Delaunay TIN for Line-Selection Design of Mountain Road[J];Computer Aided Drafting,Design and Manufacturing;2008年02期

5 梁晶晶;;Delaunay生成算法分類及研究[J];科技信息;2008年29期

6 李艷波;印桂生;張菁;朱長明;倪軍;;Delaunay四面體軟組織建模方法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2010年12期

7 呂超;劉君;劉瑜;;基于Delaunay圖的動(dòng)網(wǎng)格生成方法[J];四川兵工學(xué)報(bào);2010年12期

8 梁虎;唐玲艷;宋松和;;二維Delaunay網(wǎng)格的一個(gè)約束邊恢復(fù)算法[J];航空計(jì)算技術(shù);2011年02期

9 高遠(yuǎn);;Delaunay算法的研究與探討[J];硅谷;2011年18期

10 段碩;董慧穎;;基于Delaunay圖的移動(dòng)機(jī)器人路徑規(guī)劃方法[J];沈陽理工大學(xué)學(xué)報(bào);2008年03期

相關(guān)會(huì)議論文 前10條

1 呂超;劉君;劉瑜;;基于Delaunay圖的非結(jié)構(gòu)變形網(wǎng)格計(jì)算方法研究[A];中國航空學(xué)會(huì)第七屆動(dòng)力年會(huì)論文摘要集[C];2010年

2 李葳;林麒;周慎杰;;基于擴(kuò)展Delaunay剖分的自然單元法[A];慶祝中國力學(xué)學(xué)會(huì)成立50周年暨中國力學(xué)學(xué)會(huì)學(xué)術(shù)大會(huì)’2007論文摘要集（下）[C];2007年

3 劉巖;關(guān)振群;張洪武;張占群;;面向大規(guī)模科學(xué)計(jì)算的三維Delaunay快速插點(diǎn)算法[A];中國計(jì)算力學(xué)大會(huì)'2010（CCCM2010）暨第八屆南方計(jì)算力學(xué)學(xué)術(shù)會(huì)議（SCCM8）論文集[C];2010年

4 黃有度;蘇化明;;均勻Delaunay三角域的生成[A];中國幾何設(shè)計(jì)與計(jì)算新進(jìn)展2007——第三屆中國幾何設(shè)計(jì)與計(jì)算大會(huì)論文集[C];2007年

5 宋曉宇;王守金;王永會(huì);;一種改進(jìn)的Delaunay三角剖分快速實(shí)現(xiàn)算法[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（二）[C];2008年

6 常麗娟;劉浩宇;田歌;;基于推進(jìn)波前法和Delaunay三角法相結(jié)合的網(wǎng)格劃分方法的研究[A];北京力學(xué)會(huì)第18屆學(xué)術(shù)年會(huì)論文集[C];2012年

7 陳中貴;曹娟;楊晨暉;;構(gòu)造最優(yōu)Delaunay三角剖分的拓?fù)鋬?yōu)化方法[A];第五屆全國幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會(huì)議論文集[C];2011年

8 任振娜;楊穎;;一次性生成約束Delaunay三角網(wǎng)的算法研究[A];幾何設(shè)計(jì)與計(jì)算的新進(jìn)展[C];2005年

9 汪嘉業(yè);楊承磊;張彩明;呂琳;;一致分布點(diǎn)集Delaunay三角形化最佳期望時(shí)間算法[A];第五屆全國幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會(huì)議論文集[C];2011年

10 田歌;趙陽;張浩;應(yīng)秀梅;蔣東英;趙東;傅向榮;;基于Delaunay算法三角形網(wǎng)格劃分的角點(diǎn)優(yōu)化處理[A];北京力學(xué)會(huì)第十六屆學(xué)術(shù)年會(huì)論文集[C];2010年

相關(guān)博士學(xué)位論文 前2條

1 何香紅;液態(tài)和非晶態(tài)微觀結(jié)構(gòu)的計(jì)算機(jī)模擬研究[D];上海大學(xué);2008年

2 陳建軍;非結(jié)構(gòu)化網(wǎng)格生成及其并行化的若干問題研究[D];浙江大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

1 王倩;基于Delaunay的三維快速克里金插值[D];電子科技大學(xué);2015年

2 李程;基于Delaunay四面體剖分的面繪制算法研究[D];成都理工大學(xué);2015年

3 高莉;改進(jìn)的Delaunay三角剖分算法研究[D];蘭州交通大學(xué);2015年

4 鄭守住;改進(jìn)SURF和Delaunay三角網(wǎng)的圖像配準(zhǔn)算法研究[D];東華理工大學(xué);2014年

5 閆自庚;基于局部特征和Delaunay三角網(wǎng)格的圖像匹配及應(yīng)用[D];合肥工業(yè)大學(xué);2014年

6 李國俊;基于Delaunay細(xì)化的散亂點(diǎn)云曲面重建研究[D];解放軍信息工程大學(xué);2015年

7 童希明;熱防護(hù)軟件前后處理界面的開發(fā)[D];北京交通大學(xué);2016年

8 李永耀;高維Voronoi算法研究[D];華南理工大學(xué);2016年

9 萬雪音;基于空間不變的不規(guī)則體快速三維重建技術(shù)研究[D];東南大學(xué);2015年

10 李琳;約束Delaunay三角網(wǎng)下土地利用空間數(shù)據(jù)庫中的面狀要素合并研究[D];長安大學(xué);2016年

，

本文編號(hào)：1381539