Как легко построить диаграмму Вороного на сфере с помощью CGAL?
Во-первых, я новичок в CGAL, но программ на C ++ много. Я хотел бы использовать CGAL для построения диаграммы точек Вороного на сфере. Я реализовал один для одного из своих исследований, но структура данных не очень общая, и я хочу использовать более надежную, промышленную библиотеку, такую как CGAL. Из документа CGAL кажется, что нам нужно использовать трехмерную триангуляцию Делоне в сочетании с выпуклой оболочкой. Кроме того, я нахожу бумагу Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere, который использовал CGAL в качестве базы, но я не смог найти его код.
Кто-нибудь может привести пример, как это сделать в CGAL? И есть ли у CGAL какой-либо план поддержки сферических Делоне и Вороного напрямую с помощью более эффективного алгоритма?
Заранее спасибо!
Решение
Вы можете вычислить диаграмму точек Вороного на сфере, сначала вычислив выпуклую оболочку [1], а затем вычисляя грани нормали. Умножьте каждую из этих нормалей на радиус вашей сферы, и вы получите вершины Вороного (согласно [2]).
[1] http://doc.cgal.org/latest/Convex_hull_3/index.html [2] http://www.qhull.org/html/qdelaun.htmДругие решения
Вы можете просто использовать libdts2 (адаптер CGAL для надежной сферической триангуляции Делоне; описано в https://stackoverflow.com/a/45240506/4994003 )
Поскольку он основан на инкрементной конструкции, предлагается локализация точек.
Кроме того, это довольно быстро и не страдает от проблем числовой точности.