c++ - 带孔多边形的 CGAL 分区

Question

我正在查看手册的 Partition_2 部分和示例，以查看 CGAL 是否可以处理带孔的多边形的凸分区。所有示例似乎都使用没有任何孔的多边形。有谁知道这是否受到任何 CGAL 分区算法的支持？

https://github.com/CGAL/cgal/blob/master/Partition_2/include/CGAL/partition_2.h

https://doc.cgal.org/latest/Partition_2/index.html

谢谢，乔希。

Answer 1

从文档中：

所有的分区功能都向用户呈现相同的界面。也就是说，用户提供了一对输入迭代器，first 和before，一个输出迭代器结果，以及一个traits 类traits。假定范围 [first, beyond) 中的点定义了一个简单 多边形，其顶点按逆时针顺序排列。

简单意味着没有孔，没有自相交。

处理带有孔的多边形并不难，因为 CGAL 还提供了对多边形的布尔运算。只需创建分区并减去孔。如果您的用例对性能至关重要（直接用孔划分多边形可能更快），这可能不是一个理想的解决方案。

Answer 2

对，“2D Polygon Partitioning”包只支持没有孔的多边形（据我所知）。您始终可以使用边缘（在外部和内部 CCB 上）作为约束对带有孔的多边形进行三角剖分。另一种选择是使用垂直分解。它由“2D Minkowski Sums”包直接提供；参见Polygon_vertical_decomposition_2。它基于接受二维排列作为输入的 decompose(arr, oi) 自由函数；见CGAL::decompose()。输出是伪梯形的集合（伪梯形在退化的情况下可以是三角形），因此它比纯三角形“更好”一些并且非常有效，特别是如果您手头有底层排列。