Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2015, Vol. 55 Issue (8): 895-899,905    
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
分治法重建数字地形的子网凸包合并算法
郑辑涛1,2, 何红红2, 张涛2, 朱纪洪1
1. 清华大学 计算机科学与技术系, 北京 100084;
2. 北京航空气象研究所, 北京 100085
Subnet convex hull merging algorithm for reconstructing digital terrain models
ZHENG Jitao1,2, HE Honghong2, ZHANG Tao2, ZHU Jihong1
1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
2. Beijing Aviation Meteorological Institute, Beijing 100085, China
全文: PDF(1809 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 该文深入研究了以往基于分治策略的数字地形重建方法,在实践基础上分析了参与合并的两个子网凸包的各种可能情况,针对传统合并算法的局限性和弊端,给出了一个子网凸包合并算法。该算法根据公共支撑线的性质,通过判断凸包顶点投影位置的关系确定公共支撑线和支撑点,然后在确保合理的前提下,在两个凸包之间交替生成新三角形完成两子网凸包的合并。实验结果表明: 该算法稳定可靠,能够实现各种复杂情况下两子网凸包的成功合并。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
郑辑涛
何红红
张涛
朱纪洪
关键词 子网凸包合并数字地形重建    
Abstract:There are many digital terrain reconstructing methods based on divide and conquer. This study analyzes all possible cases of the merging of two subnet convex hulls. A subnet merging algorithm is then developed to overcome the limitations and drawbacks of traditional algorithms. The public support line and support points are found from the projection position of the vertices of the convex hulls. Then, the convex hull vertices between the support points are linked to generate new triangles so that no two triangles are intersect. Tests show that the algorithm is stable and reliable and that any two subnet convex hulls can be successfully merged.
Key wordssubnet    convex hull    merge    digital terrain model    Reconstruction
收稿日期: 2014-05-07      出版日期: 2015-09-30
ZTFLH:  TP391  
通讯作者: 朱纪洪,教授,E-mail:jhzhu@tsinghua.edu.cn     E-mail: jhzhu@tsinghua.edu.cn
引用本文:   
郑辑涛, 何红红, 张涛, 朱纪洪. 分治法重建数字地形的子网凸包合并算法[J]. 清华大学学报(自然科学版), 2015, 55(8): 895-899,905.
ZHENG Jitao, HE Honghong, ZHANG Tao, ZHU Jihong. Subnet convex hull merging algorithm for reconstructing digital terrain models. Journal of Tsinghua University(Science and Technology), 2015, 55(8): 895-899,905.
链接本文:  
http://jst.tsinghuajournals.com/CN/  或          http://jst.tsinghuajournals.com/CN/Y2015/V55/I8/895
  图1 子网凸包与凸包合并示意图
  图2 2个凸包位置关系
  图3 支撑点与半链之间的关系
  图4 矢量上的投影位置关系
  图5 支撑线检测示意图
  图5 支撑线检测示意图
  图7 四叉树组织的地形节点合并过程
  图8 某地形数字地形重建结果
  表1 不同阈值分割后的合并次数与耗时
  表2 不同地形分治法测试结果
[1] 袁正午, 侯林, 彭军还. 点集收集分配的 Delaunay 三角网快速生成算法及实现 [J]. 测绘科学, 2011, 36(5): 223-225.YUAN Zhengwu, HOU Lin, PENG Junhuan. A fast algorithm of Delaunay triangulation generation based on collecting and distributing points [J]. Science of Surveying and Mapping, 2011, 36(5): 223-225. (in Chinese)
[2] 王龙浩, 王解先. 基于逐点插入法的 Delaunay 三角网快速生成算法 [J]. 工程勘察, 2013, 10: 75-79.WANG Longhao, WANG Jiexian. Fast Delaunay triangulation generation algorithm based on incremental insertion method [J]. Geotechnical Investigation and Surveying, 2013, 10: 75-79. (in Chinese)
[3] 詹曦, 张建生. 点云边界提取及三角网格生成的集成算法研究 [J]. 计算机仿真, 2013, 30(11): 272-275.ZHAN Xi, ZHANG Jiansheng. Research on algorithm of integrating boundary extraction and triangle mesh generation of point cloud [J]. Computer Simulation, 2013, 30(11): 272-275. (in Chinese)
[4] 刘永和, 王燕平, 齐永安. 一种快速生成平面Delaunay三角网的横向扩张法 [J]. 地球信息科学, 2008, 10(1): 20-25.LIU Yonghe, WANG Yanping, QI Yongan. Horizontal expanding method: A quick algorithm for generating Delaunay triangulation from points in the plane [J]. Geo-Information Science, 2008, 10(1): 20-25. (in Chinese)
[5] 武晓波, 王世新, 肖春生. 一种生成Delaunay三角网的合成算法 [J]. 遥感学报, 2000, 4(1): 32-35.WU Xiaobo, WANG Shixin, XIAO Chunsheng. A hybridized method for building Delaunay triangulation [J]. Journal of Remote Sensing, 2000, 4(1): 32-35.(in Chinese)
[6] 吴宇晓, 张登荣. 生成Delaunay三角网的快速合成算法 [J]. 浙江大学学报: 理学版, 2004, 31(3): 343-348.WU Yuxiao, ZHANG Dengrong. Improved algorithm for building Delaunay triangulation [J]. Journal of Zhejiang University: Science Edition, 2004, 31(3): 343-348. (in Chinese)
[7] 徐青, 常歌, 杨力. 基于自适应分块的TIN三角网建立算法 [J]. 中国图像图形学报, 2000, 5A(6): 461-465. (in Chinese)XU Qing, CHANG Ge, YANG Li. The algorithm of TIN generation based on self-adapt clump organization [J], Journal of Image and Graphics, 2000, 5A(6): 461-465. (in Chinese)
[8] 芮一康, 王结臣. Delaunay三角形构网的分治扫描线算法 [J]. 测绘学报, 2007, 36(3): 358-362.RUI Yikang, WANG Jiechen. A new study of compound algorithm based on sweepline and divide-and-conquer algorithms for constructing Delaunay triangulation [J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 358-362. (in Chinese)
[9] Shamos M I, Hoey D. Closest-point problems [C]// Proceedings of the 16th IEEE Symposium on Foundations of Computer Science. Washinghon, USA: IEEE, 1975: 151-162.
[10] Lewis B A, Robinson J S. Triangulation of planar regions with application [J]. The Computer Journal, 1978, 21(4): 324-332.
[11] Lee D T, Schachter B J. Two algorithms for constructing a Delaunay triangulation [J]. International Journal of Computer and Information Sciences, 1980, 9(3): 219-242.
[12] 谢传节, 万洪涛. 基于四叉树结构的数字地表模型快速生成算法设计 [J]. 中国图像图形学报, 2002, 7A(4): 394-399.XIE Chuanjie, WAN Hongtao. Algorithm for rapidly generating digital terrain model based on quad-tree [J]. Journal of Image and Graphics, 2002, 7A(4): 394-399. (in Chinese)
[13]胡金星, 潘懋, 马照亭, 等. 高效构建Delaunay三角网数字地形模型算法研究 [J].北京大学学报, 2003, 39(5): 736-741. HU Jinxing, PAN Mao, MA Zhaoting, et al. Study on faster algorithm for constructing Delaunay triangulations DTM [J]. Scicentiarum Naturalum Universitis Pekinesis, 2003, 39(5): 736-741. (in Chinese)
[14]罗胜, 王 鑫, 孙玉平. 机载LiDAR点云的Delaunay三角网快速生成算法 [J]. 海洋测绘, 2014, 34(2): 18-21.LUO Sheng, WANG Xin, SUN Yuping. An algorithm for quick generation of Delaunay triangular net for airborne LiDAR point cloud [J]. Hydrographic Surveying and Charting, 2014, 34(2): 18-21. (in Chinese)
[15]刘合辉, 罗勇军. 基于等高线的三角网快速构建与处理 [J]. 测绘工程, 2009, 18(2): 55-58.LIU Hehui, LUO Yongjun. Speedy constructing and processing TIN based on contours [J]. Engineering of Surveying and Mapping, 2009, 18(2): 55-58. (in Chinese)
[16]刘永和, 王燕平, 齐永安. 一种简单快速的Delaunay三角网逐块生成算法 [J]. 测绘科学, 2008, 33(6): 133-135.LIU Yonghe, WANG Yanping, QI Yongan. A simple and quick block-by-block generating method for generating delaunay triangulation from points in the plane [J]. Science of Surveying and Mapping, 2008, 33(6): 133-135. (in Chinese)
[1] 万欣, 刘锡明, 苗积臣, 吴志芳. 改进的多层螺旋CT线性插值算法[J]. 清华大学学报(自然科学版), 2016, 56(12): 1346-1351.
[2] 刘春, 殷君君, 杨健. 基于岸线特征点合并的极化SAR图像小型港口检测[J]. 清华大学学报(自然科学版), 2015, 55(8): 849-853.
[3] 杜乙,王贤刚,向新程. 一种用于CT偏置扫描重建的指数型加权函数[J]. 清华大学学报(自然科学版), 2015, 55(1): 115-121.
[4] 王梦蛟,丁辉,王广志. 基于相机模型的锥束CT重建误差校正[J]. 清华大学学报(自然科学版), 2015, 55(1): 122-127.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn