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

Delaunay Triangulation Cutting Algorithm for A Set of Irregularly Located Spatial Points

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

Maximum empty circle convex polygon and maximum empty sphere convex polyhedron are introduced to compute triangulation on a set of irregularly located spatial points. The domain bounded by the convex hull of a set of spatial points is divided to maximum empty sphere convex polyhedrons firstly,then the triangulation is followed inside these polyhedrons. This method successfully solves the degeneracy problem of more than three points on a plane sharing a common circle or more than four spatial points sharing a common sphere. A possible error occurring in a class of triangulation algorithms is presented in this paper.