直线多边形交集

Question

我正在寻找/尝试为rectilinear polygon交叉矩形开发最佳算法。我正在测试的多边形没有孔。

类似here和here的答案适用于非常一般的多边形，并且解决方案的理解相当复杂。

希望S.O.社区可以帮助我记录只有直线多边形的特殊情况的算法。

我找下面充满绿色的图像中的多边形：

Answer 1

书计算几何：通过Preparata的介绍和Shamos对直线多边形的一章。

Answer 2

使用扫描线算法，利用直线多边形由其顶点定义的事实。

表示顶点以及它们所属的矩形，即类似(x, y, #rect)。对于这组点，添加由所有边的交点所产生的点。这些新点的格式为(x, y, final)，因为我们已经知道它们属于所得到的一组点。

现在：

• 排序的x值
• 所有点使用扫描线，从第一个x坐标;对于每个新点：
  • 如果它是“起点”，则将其添加到临时集T。如果它是来自矩形A的点，并且来自T中的矩形B的点的y坐标（或反之亦然），则将其标记为“最终”。
  • 如果它是一个“终点”，从T.

之后删除它和它的相应的起点，被标记为“最终”的所有点表示结果多边形的顶点。

设N是点的总数。进一步假设测试我们是否应该将点标记为“最终”，通过查找T花费时间O（log（n）），整个算法在O（N * log（N））中。

请注意，查找所有交叉点的任务可以合并到上述算法中，因为通常有效地查找所有交点本身就是一个扫掠线算法。还要注意，得到的一组点可能包含多个多边形，这使得重建“最终”顶点之外的解多边形变得稍微困难​​。