polygon - 将凸多边形外的空间划分为水平跨越的四边形

Question

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

这是输入：

这是所需的输出：

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

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

Answer 1

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

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

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

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

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

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

对每个水平条重复上述过程即可达到预期的效果。假设一组凸的、不重叠的多边形作为输入，创建的多边形保证是三角形或四边形。如果水平条不包含边，算法将创建一个矩形。如果场景中不存在多边形，算法将创建一个覆盖整个场景的矩形。