CGAL中的有效k阶voronoi图和三维voronoi图可用于求解

Question

我在计算CGAL中的k阶Voronoi图和三维Voronoi图时遇到问题。

1. 首先，我想从给定的点集(2d/3d)计算一个k阶Voronoi图(k是最近邻居的数量)。

   • 据我所知，CGAL演示ipelet文件夹中有一个头文件"k_delaunay.h"(此处代码)。并且它可以计算一个k阶正则三角剖分。我相信我可以将常规三角测量转换为Delaunay三角测量。

   • 然而，从代码中我们可以看到复杂性非常高。我已经测试了300k个2d点，计算k阶Voronoi图的实际运行时间是不可接受的。所以我想知道在CGAL中是否有其他k阶Voronoi图的实现(我的其余代码都是用CGAL编写的，所以我真的想使用现有的数据结构)？

2. 此外，由于CGAL的voronoi图适配器仅支持2D，有没有任何有效的方法将3D delaunay三角测量转换为3D voronoi图表？

谢谢！

Answer 1

您可以使用层次簇，即树状图，而不是k阶。