构建一组随机点的四面体 - 四面体化

Question

我在3D空间中有一组点(其中100万,可能更多,如10或1亿)形成一个球体(它们填充球体 - 它们不仅仅在表面上)我希望建立将每个球体连接到其第一个邻居的四面体...寻找四面体化,到目前为止,我发现的只有:

• 用于网格化的算法,但据我所知,它们填充空白空间,而我的点是固定的.
• 用于表面观察的算法,这是非常无关紧要的
• 用于3D图像观察的算法(在医学领域,大多数情况下):更接近但不完全诀窍.

我怎样才能做到这一点？

2014-08-09首先,感谢大家的建议!我是 - 现在仍然是 - 在假期,只是路过来检查是否有人回答......我并没有失望!!!! :-)我想我会首先尝试CGAL,并会从那里看到.我在O(n2)的同一组点上进行了其他数据计算,我预计它将持续大约1周,所以几个小时就不会那么糟糕.分钟将是梦想成真!

Answer 1

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

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

qhull有一个 n 维 Delaunay 实现，您可以尝试一下。CGAL也是如此。这两个包都会在 O(n log(n)) 渐近时间内计算 Delaunay 三角剖分，并且 CGAL 可以通过适当选择几何内核，以数值稳健的方式执行此操作。（也就是说，对于那些不精确算术产生不确定结果的计算，它可以自动切换到精确算术。）

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