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
摘要: 提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序,利用最优凸壳技术进行凸壳的生成和三角网联结,最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试,而且使得新加入点与凸壳边的平均比较次数不大于4,从而实现了高效的三角剖分。
关键词:
Delaunay三角剖分,
凸壳,
三角网优化
CLC Number:
CHEN Xue-gong ; HUANG Jing-jing. Algorithm of Delaunay Triangulation Based on Optimal Convex Hull Technology[J]. Computer Engineering, 2007, 33(17): 93-95.
陈学工;黄晶晶. 基于最优凸壳技术的Delaunay三角剖分算法[J]. 计算机工程, 2007, 33(17): 93-95.