如何使用CGAL轻松构建球面上的Voronoi图？

Question

首先，我是CGAL的新手，但经常用C++编程。我想使用CGAL构建球面上点的Voronoi图。我已经为我的研究之一自己实现了一个，但数据结构不太通用，我想使用更强大、工业化的库，比如CGAL。从CGAL的文档中可以看出，我们需要使用3D Delaunay三角剖分和凸包。此外，我发现了一篇论文Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere，它以CGAL为基础，但我找不到它的代码。

所以，有人可以提供一个在CGAL中如何实现这个的例子吗？CGAL是否有计划直接支持球形Delaunay和Voronoi，并使用更有效的算法？

提前感谢！

- Li Dong

---

你好，你是否成功使用CGAL库在球面上构建了Voronoi图？ - Alessandro Jacopson

Answer 1

您可以通过先计算凸包[1]，然后计算面法线来计算球面上点的Voronoi图。将每个法线乘以您的球体半径，即可得到Voronoi顶点（参见[2]）。

[1]http://doc.cgal.org/latest/Convex_hull_3/index.html [2]http://www.qhull.org/html/qdelaun.htm

- Ross Hemsley

Answer 2

您可以简单地使用libdts2（一个用于稳健球形Delaunay三角剖分的CGAL适配器；在https://stackoverflow.com/a/45240506/4994003中有描述）

由于它基于增量构造，因此提供了点定位。此外，它非常快速且不会受到数值精度问题的影响。

- ree2k