将 space 个凸多边形之外的部分分成水平跨越的四边形

Question

我正在寻找一种算法，该算法可以将包含一组非重叠凸多边形的区域作为输入，并将多边形外部的 space 分解为一组非重叠凸四边形.四边形需要有 属性，它们（单独）使用尽可能多的水平 space。

这是输入：

这是所需的输出：

我觉得我已经看到这种算法的一些变体，用于计算非常古老的绘画程序中要被洪水填充的区域。有没有比 O(n^2) 时间更好的方法来做到这一点？

编辑：我发现输出中有一些三角形。我可能应该说四边形是所需的输出，只有在物理上不可能使用四边形时才回落到三角形。

Answer 1

我想出了一个解决办法。为了有效地解决这个问题，需要某种空间数据结构来查询哪些多边形与给定的矩形区域重叠。我用了一个Quadtree。所使用的多边形数据结构也必须能够区分 internal 和 external 边。如果一条边为两个多边形所共有，则该边是 内部。

步骤如下（假设坐标系原点在左上角）：

1. 将所有多边形插入到您正在使用的任何空间数据结构中。
2. 遍历所有多边形并构建一个包含所有 Y 值的列表 出现哪些顶点。这具有概念上划分的效果 将场景分成水平条带：

3. 从上到下迭代 Y 值对。对于每个 一对 (y0, y1) 的 Y 值，用 a 声明一个矩形区域 左上角 (0, y0) 和右下角 (width, y1)。确定一组多边形 S 通过查询空间数据结构与 a 重叠。为了 S 中的每个多边形 p，确定 p 的边集 E 与 a 重叠。为了获得最佳效果，忽略任何边缘 E 带有直接向上或向下的 normal。对于每个 E 中的边 e，则需要确定对 e 与 a 的顶部和底部边缘相交的点。 这是通过简单的 line intersection 测试实现的， 将 a 的顶部和底部边缘视为简单的水平 线段。连接交点以创建一组 新线段，以红色显示：

4. 创建垂直线段L0 = (0, y0) → (0, y1)和 L1 = (width, y0) → (width, y1)。从左到右工作， 将上一步中创建的任何线段成对收集， 忽略从内部边缘创建的任何线段。 如果没有相交的外部边缘，那么仅有的两个 边将是 L0 和 L1。在这个例子中，只有四个 边缘保持：

5. 连接剩余边对中的顶点以创建 多边形：

对每个水平条重复上述过程实现 想要的结果。假设一组凸的、不重叠的 多边形作为输入，创建的多边形保证是 无论是三角形还是四边形。如果水平条包含 没有边，算法将创建一个矩形。如果不 场景中存在多边形，算法将创建一个 覆盖整个场景的矩形。