基于EMST的平面点集Delaunay三角剖分

摘要

提出一种基于欧几里德最小支撑树（EMST）的平面点集Delaunay三角剖分算法。该算法使用线性时间的随机算法求出平面点集的EMST，逐次加入一边构成三角网络，按照最小角最大化的三角化准则，通过局部变换得到平面点集的Delaunay三角剖分。采用的随机化算法有效节省了寻找EMST的计算时间，提高了整个算法的效率。