如何使用CGAL将一个大圆球体切片？

Question

球体上的一堆大圆将球体切成球形多边形。我想知道每个多边形的面积。 （事实上，我只需要最小的区域，但我不希望这会改变任何东西。）

CGAL::Nef_polyhedron_S2 似乎非常适合该任务，但我有两个问题。首先，我不确定如何最好地向 CGAL 提出问题。以下是初步尝试，但我确信它不是最佳的。使用精确的内核，对于我的用例来说太慢了。这引出了第二个问题：相同的代码在不精确的内核中出现段错误。

#include <CGAL/Nef_polyhedron_S2.h>
#include <CGAL/Random.h>
#include <iostream>

#define EXACT 1

#if EXACT
// TOO SLOW
#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
typedef CGAL::Exact_integer RT;
typedef CGAL::Homogeneous<RT> Kernel;
#else
// SEGFAULTS
#include <CGAL/Cartesian.h>
typedef CGAL::Cartesian<double> Kernel;
#endif

typedef CGAL::Nef_polyhedron_S2<Kernel> Nef_polyhedron;
typedef Nef_polyhedron::Sphere_circle Sphere_circle;
typedef Kernel::Vector_3 Vector_3;
typedef Kernel::Plane_3 Plane_3;


// ChatGPT-4's Marsaglia implementation as a placeholder
Vector_3 create_random_unit_vector(CGAL::Random& rng) {
    double x1, x2, s;
    do {
        x1 = 2 * rng.get_double() - 1;
        x2 = 2 * rng.get_double() - 1;
        s = x1 * x1 + x2 * x2;
    } while (s >= 1); // Continue looping until s is less than 1.

    double z = 1 - 2 * s;
    double scale = 2 * std::sqrt(1 - z * z);
    double x = scale * x1;
    double y = scale * x2;

    const int N = 1000000;
    return Vector_3((int)(x * N), (int)(y * N), (int)(z * N));
}


int main()
{
  CGAL::Random rng(1);

  const int n = 10;

  std::cout << "starting construction" << std::endl;
  Nef_polyhedron N(Nef_polyhedron::EMPTY);
  for (int i=0; i<n; ++i) {
    Vector_3 v = create_random_unit_vector(rng);
    Plane_3 plane(CGAL::ORIGIN, v);
    Sphere_circle S(plane);
    N = N + Nef_polyhedron(S) * Nef_polyhedron(S.opposite());
  }

  std::cout << N.number_of_sfaces() << " faces" << std::endl;
  std::cout << "supposed to be " << n * n - n + 2 << std::endl;
  return 0;
}

Answer 1

自 5.4 版本起，CGAL 的 2D 排列包 (Arrangement_on_surface_2) 支持球体上测地线弧引起的 2D 排列。查找名称中含有“球形”一词的示例。阅读该软件包的用户手册，特别是第 6 章“曲面上的排列”(https://doc.cgal.org/latest/Arrangement_on_surface_2/index.html#aos_sec-curved_surfaces) 和第 7.2.4 节圆弧嵌入球体中的大圆 (https://doc.cgal.org/latest/Arrangement_on_surface_2/index.html#arr_ssectr_spherical)。

您可以构建、维护和操作此类安排。您还可以独立使用特征类模板 Arr_geodesic_arc_on_sphere_traits_2 （与包中的任何其他特征一样）。请注意，仅使用有理算术。