C++中多边形的梯形分解
Trapezoidal decomposition of polygon in C++
我正在处理一个多边形“断裂”问题，即将有（或没有）孔洞的多边形分解成梯形。
我在 Python 中发现了类似的实现：
https://deparkes.co.uk/2015/02/05/trapezoidal-decomposition-polygons-python/.
有没有办法用 C++ 实现？
给定点 (x, y) (std::vector) 列表，然后 return 梯形（点）列表。
我不知道执行此操作的库，但这是执行此操作的算法的粗略概述，它是扫描线或线扫描算法的一个实例。
这个想法是您想象一条平行于您的切片方向的线扫过您的数据。发生这种情况时，您会维护一组活动边。每次您的线碰到一个顶点时，您都会发出适当的梯形并移除已变为非活动状态的边并引入任何新的活动边。
- 将所有边转换为有向边（它们需要有方向，以便您可以正确处理孔洞）
- 通过增加最小 x 坐标对边进行排序（您也可以通过 y 来完成，但假设 x 在您的图表中从左到右增加，这是适合您的情况的正确选择）。对于具有相同最小 x 坐标的边，使用 y 坐标对其进行排序。例如，在您显示的图表中，它们看起来是从上到下排序的。是增加还是减少 y 取决于您的坐标系。
- 将扫描线设置为第一个顶点并引入与扫描线相接触的边
- 将扫描线前进到下一个顶点。保持上一个扫描线的值可用通常很有帮助。
- 发射任何梯形。发射的梯形将全部位于前一扫描线和当前扫描线之间。并且顶点将是当前或先前扫描线相交和边缘的位置。
- 删除现在位于扫描线左侧的任何边缘。 （例如，在图中，当扫描线位于顶点 2 时，您将删除 0-2 的边）
- 合并任何新边。
- 当还有剩余边时，转到步骤 4。
我在这里掩盖了一些尴尬的细节。您可能需要根据您的应用程序“网格化”输出梯形，并且您必须非常小心计算的浮点部分。
如果您能找到执行多边形栅格化的代码，通常可以对其进行调整以执行此操作。在这种情况下，您将用于计算每个 x 或 y 坐标处的边交点的代码更改为仅计算顶点处的边交点。另一个值得关注的地方是开源 EDA 包。需要此算法来准备用于掩模准备的芯片设计数据，但由于您使用了术语“断裂”，所以您可能已经知道了 ;-)
我正在处理一个多边形“断裂”问题，即将有（或没有）孔洞的多边形分解成梯形。
我在 Python 中发现了类似的实现： https://deparkes.co.uk/2015/02/05/trapezoidal-decomposition-polygons-python/.
有没有办法用 C++ 实现？
给定点 (x, y) (std::vector) 列表，然后 return 梯形（点）列表。
我不知道执行此操作的库，但这是执行此操作的算法的粗略概述，它是扫描线或线扫描算法的一个实例。
这个想法是您想象一条平行于您的切片方向的线扫过您的数据。发生这种情况时，您会维护一组活动边。每次您的线碰到一个顶点时，您都会发出适当的梯形并移除已变为非活动状态的边并引入任何新的活动边。
- 将所有边转换为有向边（它们需要有方向，以便您可以正确处理孔洞）
- 通过增加最小 x 坐标对边进行排序（您也可以通过 y 来完成，但假设 x 在您的图表中从左到右增加，这是适合您的情况的正确选择）。对于具有相同最小 x 坐标的边，使用 y 坐标对其进行排序。例如，在您显示的图表中，它们看起来是从上到下排序的。是增加还是减少 y 取决于您的坐标系。
- 将扫描线设置为第一个顶点并引入与扫描线相接触的边
- 将扫描线前进到下一个顶点。保持上一个扫描线的值可用通常很有帮助。
- 发射任何梯形。发射的梯形将全部位于前一扫描线和当前扫描线之间。并且顶点将是当前或先前扫描线相交和边缘的位置。
- 删除现在位于扫描线左侧的任何边缘。 （例如，在图中，当扫描线位于顶点 2 时，您将删除 0-2 的边）
- 合并任何新边。
- 当还有剩余边时，转到步骤 4。
我在这里掩盖了一些尴尬的细节。您可能需要根据您的应用程序“网格化”输出梯形，并且您必须非常小心计算的浮点部分。
如果您能找到执行多边形栅格化的代码，通常可以对其进行调整以执行此操作。在这种情况下，您将用于计算每个 x 或 y 坐标处的边交点的代码更改为仅计算顶点处的边交点。另一个值得关注的地方是开源 EDA 包。需要此算法来准备用于掩模准备的芯片设计数据，但由于您使用了术语“断裂”，所以您可能已经知道了 ;-)