c++ - 建立一组随机点的四面体-四面体化

我在3D空间中有一组点(其中有100万，将来可能会增加，例如10或1亿)，形成一个球体(它们充满了球体-它们不仅在表面上)，我想建立将每个球体连接到它的第一个邻居的四面体...到目前为止，寻找四面体化，我发现的是:

算法进行网格划分，但据我所知，它们填充了空白空间，而我的观点却是固定的。

用于表面查看的

算法，与

无关
用于3D图像查看的

算法(主要是在医学领域):距离更近，但效果并不理想。

我怎样才能做到这一点？

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

最佳答案

您似乎正在寻找3空间中的Delaunay triangulation算法。

我希望您不要介意等待一会儿，因为要对1亿点进行Delaunay三角剖分会花费相当长的时间。

qhull具有您可以尝试的n维Delaunay实现。 CGAL也是如此。两个包都将在o(n log(n))渐近时间和cgal可以使用适当的几何内核选择，以数字强大的方式进行计算。 (也就是说，对于不精确算术会产生不确定结果的那些计算，它可以自动切换到精确算术。)

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