C++中多边形的梯形分解

Question

我正在处理多边形“断裂”问题，即将带（或不带）孔的多边形分解为梯形。

我在这里发现了用Python实现的类似的东西： https://deparkes.co.uk/2015/02/05/trapezoidal-decomposition-polygons-python/.

有没有办法在C++中做到这一点？

给定一个点（x，y）（std::vector）列表，然后返回一个梯形（点）列表。

Answer 1

我不知道有哪个库可以做到这一点，但这里有一个算法的粗略轮廓，它是扫描线或线扫描算法的一个实例。

这个想法是，您想象一条与切片方向平行的线扫过您的数据。当这种情况发生时，您将维护一组活动边。每次您的线到达顶点时，您都会发出适当的梯形并删除已变得不活动的边并引入任何新的活动边。

1. 将所有边转换为有向边（它们需要有方向，以便您可以正确处理孔）
2. 通过增加最小 x 坐标对边缘进行排序（您也可以通过 y 进行排序，但假设 x 在图表中从左到右增加，这对于您的情况来说是正确的选择）。对于具有相同最小 x 坐标的边，请使用 y 坐标对它们进行排序。例如，在您显示的图表中，它们看起来像是从上到下排序的。 y 是增加还是减少取决于您的坐标系。
3. 将扫描线设置为第一个顶点并引入与扫描线接触的边
4. 将扫描线推进到下一个顶点。保持前一个扫描线的值可用通常很有帮助。
5. 发出任何梯形。发射的梯形将全部位于前一扫描线和当前扫描线之间。顶点将是当前或先前扫描线相交和边缘的位置。
6. 删除扫描线左侧的所有边缘。 （例如，在图中，当扫描线位于顶点 2 时，您将删除 0-2 之间的边）
7. 合并任何新边。
8. 当还有剩余边缘时，请转到步骤 4。

我在这里掩盖了一些尴尬的细节。您可能需要根据您的应用程序对输出梯形进行“网格化”，并且您必须非常小心计算的浮点部分。

如果您能找到执行多边形光栅化的代码，通常可以对其进行修改以执行此操作。在这种情况下，您可以将计算每个 x 或 y 坐标处的边交点的代码更改为仅计算顶点处的边交点。另一个值得寻找的地方是开源 EDA 包。需要使用该算法来准备用于掩模准备的芯片设计数据，但由于您使用了术语“断裂”，也许您已经知道了这一点;-)

Answer 2

我在这里实现了一个解决方案：https://github.com/halay08/polygon-clipping