CGAL로 쉽게 보로 노이 다이어그램을 구형으로 생성하는 방법은 무엇입니까?

Question

첫째, 나는 CGAL을 처음 접했지만 C++ 프로그램이 많다. 내가 볼에 보로 노이 다이어그램을 만들기 위해 CGAL을 사용하고 싶습니다. 내 연구를 위해 나 자신을 구현했지만 데이터 구조는 매우 일반적인 것이 아니며 CGAL과 같은보다 견고하고 산업적인 라이브러리를 사용하고 싶다. CGAL의 문서에서, 우리는 볼록 선체와 3D Delaunay 삼각 측량을 사용해야 할 것 같습니다. 또한, 기초로 CGAL을 사용하는 Robust and Efficient Delaunay Triangulations of Points on Or Close to a Sphere이라는 종이를 찾았지만 코드를 찾을 수 없었습니다.

누구든지 CGAL에서이를 수행하는 방법에 대한 예제를 제공 할 수 있습니까? 그리고 CGAL은 구형 델라 네이와 보로 노이를보다 효율적인 알고리즘으로 직접 지원할 계획이 있습니까?

미리 감사드립니다.

Answer 1

먼저 볼록한 선체 [1]를 계산하고 나서 패싯 법선을 계산하여 구의 보로 노이 다이어그램을 계산할 수 있습니다. 이 법선을 각각 구의 반지름으로 곱하면 보로 노이 꼭지점을가집니다 ([2]에 따라).

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

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

Answer 2

간단히 libdts2 사용할 수 (강력한 구면 들로네 삼각 분할하는 CGAL 어댑터; https://stackoverflow.com/a/45240506/4994003 참조)

은 증분에 기지 때문에 건설, 포인트 현지화가 제공됩니다. 또한 오히려 빠르며 수치 정밀도 문제로 어려움을 겪지 않습니다.