假设我有一些由面和线连接的任意点集,以便形成闭合多面体有什么算法可以把这样的网格划分成一组四面体吗?
最佳答案
您可以在R^3
中构建点的约束delaunay三角剖分(即四面体化),其中约束是边和三角形面的列表。
但是要注意--在高于2的维度中,不可能总是直接形成这样的约束三角剖分!一个很好的例子是Schonhardt Polyhedron。为了处理这种多面体,有必要通过引入额外的顶点来“分割”约束。据我所知,尽管有人提出了一系列启发式方法,但确定“最佳”方法仍然是一个开放的研究领域。
你可能对这方面的研究/软件感兴趣,特别是他的论文:
Jonathan Shewchuk's
Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery
解决高维约束三角剖分的一些问题。
另外,我假设您的问题是非平凡的——有一组定义非凸多面体的约束在凸约束的情况下,这些应该直接恢复通过计算无约束Delaunay三角剖分,保证在任何维度上都存在。