高阶沃罗诺伊图

Question

是否有任何用于构建高阶 voronoi 图的 C/C++ 库？AFAIK，CGAL仅支持普通的Voronoi图。

Answer 1

从Delaunay三角测量中检索Voronoi细胞应该在任何维度上工作，因此CGAL的Delaunay_d类可能是一个解决方案。但是在更高维度上，计算时间将大大增加。

Answer 2

从 CGAL 4.1 开始，仍然没有用于 k 阶 Voronoi 图的 API。 但是，CGAL Ipelets 包中有一个演示，用于计算双 k 阶 Delaunay 三角测量。 您可能会发现它作为起点很有用。

在 CGAL 发行版中，在目录 demo/CGAL_ipelets 下查找文件multi_delaunay.cpp并include/CGAL_ipelets/k_delaunay.h 。