作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2007, Vol. 33 ›› Issue (17): 93-95. doi: 10.3969/j.issn.1000-3428.2007.17.032

• 软件技术与数据库 • 上一篇    下一篇

基于最优凸壳技术的Delaunay三角剖分算法

陈学工,黄晶晶   

  1. (中南大学信息科学与工程学院,长沙 410083)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-05 发布日期:2007-09-05

Algorithm of Delaunay Triangulation Based on Optimal Convex Hull Technology

CHEN Xue-gong , HUANG Jing-jing   

  1. (School of Information Science and Engineering, Central South University, Changsha 410083)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-09-05 Published:2007-09-05

摘要: 提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序,利用最优凸壳技术进行凸壳的生成和三角网联结,最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试,而且使得新加入点与凸壳边的平均比较次数不大于4,从而实现了高效的三角剖分。

关键词: Delaunay三角剖分, 凸壳, 三角网优化

Abstract: A Delaunay triangulation algorithm based on optimal convex hull technology is presented. The algorithm makes the discrete points sort in scan manner, and secondly it constructs convex hull and triangulates the sorted points by the optimal convex hull technology which is proved by the author, and optimizes triangles utilizing topological structures of directed edges. The algorithm avoids the test of point of intersection. Moreover, the average test times of a newly added point is under 4, so that the high efficiency of triangulation can be sure.

Key words: Delaunay triangulation, convex hull, triangles optimization

中图分类号: