首页 | 本学科首页   官方微博 | 高级检索  
     

平面点集Delaunay三角剖分的分治算法
引用本文:谢增广. 平面点集Delaunay三角剖分的分治算法[J]. 计算机工程与设计, 2012, 33(7): 2652-2658
作者姓名:谢增广
作者单位:华北计算技术研究所,北京,100083
基金项目:国家自然科学基金,民航局科技基金
摘    要:为发展图形网格化技术,研究了平面点集的三角剖分算法.根据经典算法中在实际应用中遇到的共性问题,提炼了3个工具算法;为了更好地表示平面区域划分的拓扑信息,引入了双链接边表(DCEL)的数据结构.在此基础上,设计并实现了平面集Delaunay三角剖分分治算法,并对特殊退化情况进行了处理,通过计算表明了该算法时间复杂度为0(N* logN).实验数据结果验证了该算法的正确性、健壮性.

关 键 词:平面点集Delaunay三角剖分  双链接边表  分治策略  计算几何

Divide-and-conquer algorithm for constructing Delaunay triangulation of planar points
XIE Zeng-guang. Divide-and-conquer algorithm for constructing Delaunay triangulation of planar points[J]. Computer Engineering and Design, 2012, 33(7): 2652-2658
Authors:XIE Zeng-guang
Affiliation:XIE Zeng-guang(North China Institute of Computing Technology,Beijing 100083,China)
Abstract:To develop graphic mesh generation technology,algorithms of triangulation in 2d is studied.According the common problems encountered in the practical application by using classical algorithm,3 auxiliary sub-algorithms are refined.In order to represent topology information of surface region efficiently,a data structure named doubly-connected edge list(DCEL) is introduced.On this basis,a Delaunay triangulation algorithm based on strategy of divide-and-conquer is illustrated in detail.Special degenerate cases are also taken into consideration,and the conclusion that the algorithm will take O(N*logN) time in total is proved.The experimental results verify the correctness and robustness of the algorithm.
Keywords:Delaunay triangulation of planar points  DCEL  divide-and-conquer  computational geometry
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号