How easy is it to build a Voronoi diagram on a sphere with CGAL?

Question

Firstly, I am new to CGAL, but there are many C ++ programs. I would like to use CGAL to build a Voronoi diagram on points on a sphere. I implemented one of them for one of my research, but the data structure is not very universal, and I want to use a more robust industrial library like CGAL. From the CGAL document, it seems that we need to use 3D Delaunay triangulation in combination with a convex hull. In addition, I find a document Robust and Efficient Delaunay Triangulations of Points on Or Close to a Spherethat used CGAL as a base, but I could not find its code.

So can anyone provide an example on how to do this in CGAL? And does CGAL have any plan to support the spherical Delaunay and Voronoi directly with a more efficient algorithm?

Thanks in advance!

Answer 1

You can calculate the Voronoi diagram by points on a sphere by first calculating the convex hull [1] and then calculating the normal of the facets. Multiply each of these normals by the radius of your sphere and you have Voronoi vertices (according to [2]).

[1] http://doc.cgal.org/latest/Convex_hull_3/index.html

[2] http://www.qhull.org/html/qdelaun.htm

Answer 2

You can simply use libdts2 (CGAL adapter for reliable Delaunay spherical triangulation described in fooobar.com/questions/1529366 / ... )

, . , .