8

我在 3D 空间中有一组点（其中 100 万，未来可能更多，比如 10 或 1 亿）形成一个球体（它们填充球体 - 它们不只是在表面上），我想构建连接每个球体与其第一个邻居的四面体......寻找四面体化，到目前为止，我发现的是：

  • 网格划分算法，但据我所知，它们填充空白，而我的观点是固定的。
  • 表面观察的算法，这是完全无关的
  • 用于查看 3D 图像的算法（主要是在医学领域）：这更接近但并不完全奏效。

我怎样才能做到这一点？

2014-08-09 首先感谢大家的建议！我曾经 - 现在仍然 - 在假期里，只是路过看看是否有人回答......我并不失望！！！！:-) 我想我会先尝试 CGAL，然后再看看。我对 O(n2) 中的同一组点进行了其他数据计算，我预计这些点将持续大约 1 周，所以几个小时不会那么糟糕。分分钟梦想成真！

4

2 回答 2

1

您似乎正在寻找 3 空间中的Delaunay 三角剖分算法。

我希望您不要介意等待一段时间，因为 1 亿点的 Delaunay 三角剖分需要相当长的时间。

qhull有一个你可以尝试的 n 维 Delaunay 实现。CGAL也是如此。这两个软件包都将计算O（n log（n））渐近时间中的Delaunay三角剖分，而CGAL可以以适当的几何核进行选择，以数值强大的方式进行操作。（也就是说，对于那些不精确算术产生不确定结果的计算，它可以自动切换到精确算术。）

我不建议您尝试自己实现快速的 Delaunay 三角剖分，即使是在二维中也是如此。当您需要根据算术结果评估谓词时，可能会发生可怕的事情。

于 2014-08-03T22:50:22.953 回答
0

我在我的一个项目中使用tetgen进行四面体化。它工作得很好而且足够快

于 2015-07-22T14:49:16.137 回答