Delaunay三角网动态更新算法的研究进展
作者:
基金项目:

福建省科技计划重点项目(2014Y0032)


Research Progress on Delaunay Triangulation Dynamic Updating Algorithm
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [53]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    通过对Delaunay三角网动态更新算法进行研究, 综述了Delaunay三角网中插入和删除点、约束线算法以往研究. 详细介绍点定位、LOP优化、对角线交换等关键技术的研究进展, 并对比各种方法的优缺点, 分析已解决的问题和仍存在的问题. 最后对更新算法研究不足之处进行总结, 并提出若干可能的研究方向.

    Abstract:

    Based on the study of delaunay triangulation dynamic updating algorithm, this paper reviews the earlier researches about inserting points and constrained edges into an existed Delaunay Triangulation, or deleting points and constrained edges from the Delaunay Triangulation. This paper describes a series of key techniques in detail, such as point location, LOP principle, diagonal exchanging etc., and also compares the advantages and disadvantages of these algorithms, furthermore analyses the solved problems and existing problems. Finally the problems existing in the delaunay triangulation dynamic updating algorithms are summarized, and some suggestions about future work are proposed in the end.

    参考文献
    1 Lawson CL. Generation of a triangular grid with applications to contour plotting. Jet Pollution Laboratory, 1972, 299: 2.
    2 Tsai VJD. Delaunay triangulations in TIN creation:an overview and a linear-time algorithm. International Journal of Geographical Information Science, 1993, 7(6): 501-524.
    3 Schrijvers. Insertions and deletions in Delaunay triangulations using guided point location[Ph.D.Thesis]. Netherlands, Eindhoven: Eindhoven University of Technology, 2012.
    4 Liu JF, Yan JH, Lo SH. A new insertion sequence for incremental Delaunay triangulation. Acta Mechanica Sinica, 2013, 29(1): 99-109.
    5 Devillers O. Delaunay triangulations,theory vs practice. In: Didimo W, Liotta G, eds. 28th European Workshop on Computational Geometry. Assisi, Italy. Bas Nieuwenhuizen. 2012. 1-7.
    6 贾晓林,吴立新,王彦兵.二维Delaunay 三角网局部更新:点插入与点删除.地理与地理信息科学,2004,20(5):28-31.
    7 陈楚江,王德峰.海量数据CDT快速建立及其实时更新.测绘学报,2002,31(3):262-265.
    8 Aggarwal A, Guibas LJ, Saxe J, Shor PW. A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete & Computational Geometry, 1989, 4(1): 591-604.
    9 Heller M. Triangulation algorithms for adaptive terrain modeling. Proc. 4th Internat Sympos Spatial Data Handling. 1990. 163-174.
    10 Devillers O. On deletion in Delaunay triangulations. International Journal of Computational Geometry & Applications, 2002, 12(03): 193-205.
    11 Devillers O. Vertex removal in two-dimensional Delaunay triangulation: Speed-up by low degrees optimization. Computational Geometry, 2011, 44(3): 169-177.
    12 Mostafavi MA, Gold C, Dakowicz M. Delete and insert operations in Voronoi/Delaunay methods and applications. Computers & Geosciences, 2003, 29(4): 523-530.
    13 孟亮,方金云,唐志敏.Delaunay 三角网表示和点删除方法.计算机工程与设计,2008,29(3):738-740.
    14 Faugeras O. Three-dimensional computer vision:a geometric viewpoint. Cambridge: MIT press, 1993.
    15 卢朝阳,吴成柯.满足全局Delaunay 特性的带特征约束的散乱数据最优三角部分.计算机学报,1997,20(2):118-124.
    16 易法令,韩德志.带特征线约束的Delaunay 三角剖分最优算法的研究及实现.计算机工程,2001,27(6):32-34.
    17 Sloan SW. A fast algorithm for constructing Delaunay triangulations in the plane. Advances in Engineering Software (1978), 1987, 9(1): 34-55.
    18 Choi BK, Shin HY, Yoon YI. Triangulation of scattered date in 3D space. Computer -aided design, 1988, 20(5): 239-248.
    19 卢朝阳,吴成柯.任意多边形内带特征约束的散列数据的最优三角剖分.计算机辅助设计与图形学学报,1997, 9(4):302-308.
    20 蒲浩,詹振炎,宋占峰.约束Delaunay 三角化在路线设计中的应用及其生成算法研究.中国公路学报,2002,15(2): 22-27.
    21 宋占峰,詹振炎.Delaunay 三角网剖分中嵌入约束边的局部调整算法.西南交通大学学报,2002,37(4):399-402.
    22 Lu YZ. Dynamic Constrained Delauney Triangulation and Application To Multichip Module Layout [Ph.D. Thesis]. USA: University of California at Santa Cruz, 1991.
    23 刘学军,龚健雅.约束数据域的Delaunay 三角剖分与修改算法.测绘学报,2001,30(1):82-88.
    24 刘学军,赵吉先.三角网数字地面模型的动态修改与编辑.中国公路学报,2000,13(4):16-20.
    25 王彦兵,吴立新,史文中.基于虚点影响域重构的CD-TIN约束线删除算法.武汉大学学报(信息科学版),2005, 30(10):5.
    26 王彦兵,吴立新,贾晓林,史文中.约束 Delaunay 三角网点删除的一体化凸耳消元法.地理与地理信息科学,2004, 20(6):31-34.
    27 蒲浩,宋占峰.快速构建三角网数字地形模型方法的研究.中国铁道科学,2001,22(6):100-105.
    28 胡金星,马照亭,吴焕萍,潘懋.基于格网划分的海量数据 Delaunay 三角剖分.测绘学报,2004,33(2):163-167.
    29 吴宇晓,张登荣.生成Delaunay 三角网的快速合成算法.浙江大学学报(理学版),2004,31(3):343-348.
    30 邹永贵,张涛.改进的平面域Delaunay 三角网生成算法.计算机工程与应用,2013,49(20): 171-174.
    31 宋占峰,蒲浩.基于三角网数字地面模型快速定位算法的研究.中国铁道科学,2002,23(1):63-66.
    32 刘少华,程朋根,况化智,陈红华.Delaunay 三角网嵌入约束线段算法的研究及三维可视化.华东地质学院学报,2003,26(1):82-86.
    33 刘学军,符锌砂.三角网数字地面模型快速构建算法研究.中国公路学报,2000,13(2):31-36.
    34 郭兆胜,张登荣.一种改进的高效Delaunay 三角网的生成算法.遥感信息,2005,(1):15-17.
    35 许建中,马利庄.改进的 Delaunay 三角网渐次插入生成算法.计算机工程,2008,34(17):254-256.
    36 李小秋,许民献,尹志永.Delaunay 三角网关键技术探讨.测绘工程,2011,20(6):61-63.
    37 Chew LP. Constrained delaunay triangulations. Algorithmica, 1989, 4(1-4): 97-108.
    38 张咏,刘长星,董汉军,赵奋军.二维Delaunay 三角网的任意点删除算法研究.地理与地理信息科学,2009,24(6):50-53.
    39 卢朝阳,吴成柯,陆心如.简单多边形的优化三角剖分.电子学报,1991,19(2):82-87.
    40 周晓云,何大曾.实现平面上散乱数据点三角剖分的算法.计算机辅助设计与图形学学报,1994,6(4):256-259.
    41 Bern M, Eppstein D. Mesh generation and optimal triangulation. Computing in Euclidean Geometry, 1992, 1: 23-90.
    42 李立新,谭建荣.约束 Delaunay 三角剖分地嵌入约束边的多对角线交换算法.计算机学报,1999,22(10):1114-1118.
    43 章孝灿.快速高精度 DEM生成技术研究[博士学位论文].杭州:浙江大学,2002.
    44 徐道柱,刘海砚.大量约束边条件下 Delaunay 三角网的快速生成.测绘工程,2007,16(3):6-10.
    45 蒋红斐,詹振炎.约束边强行嵌入三角网的算法研究.华中科技大学学报(自然科学版),2001,(7):104-105.
    46 陈学工,黄晶晶.Delaunay 三角网剖分中的约束边嵌入算法.计算机工程,2007,33(16):56-58.
    47 宋晓眉,张晓东,李建林.一种高准确度的约束Delaunay三角网生成算法研究.地理与地理信息科学,2009,25(1): 99-102.
    48 陈学工,李源,曹建,肖克炎.Delaunay 三角网剖分的约束边嵌入改进算法.计算机工程与应用, 2009,45(24):235-237.
    49 Hjelle Y, Dahlen M. Constrained Delaunay Triangulation. Triangulations and Applications. Berlin Heidelberg: Springer, 2006: 113-129.
    50 王永会,吴刚.大量约束边条件下构建约束Delaunay三角网的研究.测绘科学,2009,34(10):117-118.
    51 宋占峰,詹振炎,蒲浩.约束Delaunay三角剖分动态算法研究.中国公路学报,2002,15(3):18-22.
    52 宋晓宇,戚爰伟,王永会.基于最大外接圆的约束Delaunay 三角剖分算法.沈阳建筑大学学报(自然科学版),2009, 24(6):1094-1098.
    53 卢扣,李明峰,管莉莉,陈春晖.基于最小正切值的约束 Delaunay三角剖分.南京工业大学学报(自然科学版), 2010,32(5):96-99.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李娜. Delaunay三角网动态更新算法的研究进展.计算机系统应用,2015,24(2):14-21

复制
分享
文章指标
  • 点击次数:1364
  • 下载次数: 6535
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2014-06-10
  • 最后修改日期:2014-07-07
  • 在线发布日期: 2015-03-04
文章二维码
您是第11199554位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号