c++ - CGAL 一般多边形 : rigid motions and area

Question

调查 this question ，我将不得不处理其边界由线段和圆弧组成的形状。看来 CGAL 应该可以在这里帮助我:根据 this section of the User's Manual , 一个 General_polygon_set_2 与 Gps_segment_traits_2 因为它的特征类应该能够表达我需要的大部分操作，特别是交集和差异。

到目前为止，我还没有在文档中找到对这些形状应用刚性运动的方法，以及计算所得形状面积的方法。

我想我可以解决这两个问题。对于刚性运动，我可以在转换原始定义对象后重新创建形状。为了计算面积，我可以使用鞋带方法的一种变体，并进行调整以应对圆弧。手册中的示例打印了有关支持圈的详细信息，并深入挖掘了标题，我发现每个 curve因为我的多边形确实有一个 supporting_circle() 方法，所以我想它实际上是一个 Arr_circle_segment_traits_2<K>::X_monotone_curve_2 .所以我应该能够获得足够的圆信息来计算面积。在使用故意的编译器错误消息来了解手册简单描述为 unspecified_type 的某些对象的类型之后，我才在标题中发现了这一点。 .

不过，这两个操作都需要相当多的工作，令我惊讶的是似乎没有内置的方法来完成这些操作。另一方面，CGAL 通过模板参数进行自定义的方式，我可能只是缺少一种方法来执行这些适用于圆形线段的操作，尽管它可能不适用于其他一般多边形。您知道我可以使用的任何快捷方式吗？

Answer 1

恐怕您不会喜欢我的回答。

我是一名 CGAL 开发人员，实际上是 Reg 的开发人员之一。 bool 运算和排列包。

首先，不支持您要求的操作。

关于面积计算，你的方法似乎是可行的。然而，在概念中要求这样的操作对我们来说将是一项巨大的努力，因为那样我们就需要为我们支持的所有特征类实现该操作。我想，总是可以从一个开始，然后一个一个地添加它们。我会将其放入我们的待办事项列表中，但我不会押注快速交付...

关于转型，答案比较复杂。正如您已经注意到的那样，对(精确的)几何形状(例如排列、一般多边形集，甚至是一个小的线性简单凸多边形)应用非精确变换可能是有害的。您必须想出一个精确变换，例如，一个包含精确类型数字的变换矩阵——用于表示几何元素(精确)坐标的相同(或至少可以相互转换)类型。问题自然是旋转，因为您通常从角度开始并使用三角函数(例如 sin() 和 cos())来计算旋转矩阵。假设您想旋转给定角度，比如 alpha。您需要计算 alpha 的近似值，使得 sin(alpha) 和 cos(alpha) 是有理数，因此可以用上述精确类型的数字表示。免费函数 CGAL::rational_rotation_approximation() 可以提供帮助。如该函数的手动输入中所述，该近似值基于 Farey 序列，如 Canny 和 Ressler 在 1992 年第 8 届 SoCG 上提出的有理旋转法中所述。

祝你好运!