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

Algorithm of Delaunay Triangulation Based on Optimal Convex Hull Technology

作　　者：陈学工[1] 黄晶晶[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程》2007年第17期93-95,共3页Computer Engineering

基　　金：国家"863"计划基金(2002AA135160)

摘　　要：提出了一种基于最优凸壳技术的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.

关 键 词：DELAUNAY三角剖分 凸壳 三角网优化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]