任意多面体的四面体剖分算法

该文提出一种将任意多面体剖分为四面体的算法,该算法首先依据顶点凸凹性算法判定多面体顶点的凸凹性性质,再寻找符合剖分条件的凸顶点,将该凸顶点的凸空间从原多面体中剖分出去,得到一个新的多面体,剖分出来的凸空间再分为多个四面体;再重复对新的多面体进行剖分,直到剖分完毕。该算法的平均时间复杂度为O(N+M),其中N为多面体的凸顶点数目,M为多面体的凹顶点数目。

Algorithm of Dividing an Arbitrary Polyhedron to Tetrahedrons

This paper proposes an algorithm to divide an arbitrary polyhedron to tetrahedrons,which is based on our al-gorithm to decide its vertex's attribute of concave or convex,then searches the qualified convex vertex to be divided.Af-ter removing the convex vertex from the original polyhedron,we can obtain a new one.At the end we can finish all of divisions after continuing this procedure again and again.The algorithm complexity at average time is O(N+M),therein contained the number of polyhedron convex vertex N and the number of polyhedron concave vertex M.