空间散乱点集Delaunay四面体剖分切割算法

摘要

提出最大空圆凸多边形和最大空球凸多面体的概念.在此基础上,提出一种空间散乱点集Delaunay四面体剖分算法,即对空间散乱点集首先进行最大空球凸多面体剖分,然后在多面体内部作Delaunay四面体剖分.这种方法消除了"退化"现象(平面3个以上点共圆或空间4个以上点共球面)引起的潜在错误.最后分析了一类常见的Delaunay四面体剖分算法的潜在错误.