如何用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？

在此先感謝！

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

Answer 2

您可以簡單地使用libdts2（一個CGAL適配器魯棒球形Delaunay三角;在https://stackoverflow.com/a/45240506/4994003描述）

由於立足於增量建設，點本地化提供。此外，它速度相當快，不會遇到數值精度問題。