利用Voronoi图改进离散数据重构曲面算法

摘要

本文利用Delaunay三角剖分和 Voronoi图的性质,实现了一种对散乱点重构闭合曲面的方法.该方法在搜索策略上进行了改进:首先对输入点进行三角剖分,产生相互独立的四面体,构建一个凸包;然后利用Delaunay三角剖分产生Voronoi图;最后根据Voronoi图的性质,选择包含在形体内部的四面体,提取出边界三角形,完成散乱点边界重构.计算复杂度和Delaunay四面体数量成正比,在自动形状重构时形状边界提取过程的计算复杂度为O(n),算法适用于各种涉及图形重构的工程应用.