摘要
提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序,利用最优凸壳技术进行凸壳的生成和三角网联结,最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试,而且使得新加入点与凸壳边的平均比较次数不大于4,从而实现了高效的三角剖分。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2007年第17期93-95,共3页
Computer Engineering
基金
国家"863"计划基金(2002AA135160)
