基于点集凸包的Delaunay三角剖分实时算法研究

摘要

凸包作为计算几何的一种基本的数据结构,在计算几何设计方面有着十分重要的应用.本文采用坐标及单映射的算法来构建平面散乱点集的凸包.而点集的Delaunay三角化对三维曲面重构有着十分重要的应用,由于Voronoi图和Delaunay三角化的对偶性,一般通过构建点集的Voronoi图来构建Delaunay三角网,本文直接构建Delaunay三角剖分,该算法原理简单,稳定,易实现,尤其适合数据点较少的点集.