直线多边形相交

Question

我正在寻找/尝试开发一种最佳算法，用于矩形与直角多边形的相交。 我测试的多边形没有孔。

像这里和这里提供的答案是针对非常普通的多边形，因此解决方案理所当然地相当复杂。

希望S.O.社区能够帮助我记录仅包含直角多边形特殊情况的算法。

我正在寻找下图中绿色填充的多边形：

- jedierikb

---

这个矩形多边形的边缘和矩形是否平行于坐标轴？ - Andre Holzner

@Andre -- 是的 -- 所有线都是平行的。 - jedierikb

作为第一个想法，我会考虑将直角多边形存储在线段树中（用于二维）。假设直角多边形不变，而矩形会变化。 - Andre Holzner

是的，你对哪些是可变的和哪些是不可变的有正确的假设。感谢建议。 - jedierikb

Answer 1

Preparata 和 Shamos 著作的 Computational Geometry: an Introduction 这本书中有一章关于直角多边形的内容。

- lhf

---

谢谢。我会看第2章和第8章。我发现我想要的术语是等面多边形。 - jedierikb

Answer 2

使用扫描线算法，利用直角多边形由其顶点定义的事实。将顶点与所属矩形一起表示，即类似于(x, y, #rect)。对于所有边缘交叉点，添加这些点。这些新点的形式为(x, y, final)，因为我们已经知道它们属于结果点集。

现在：

- 按x值对所有点进行排序 - 使用扫描线，从第一个x坐标开始；对于每个新点： - 如果是“起始点”，则将其添加到临时集合T中。如果它是来自矩形A并处于来自T中矩形B的y坐标之间（反之亦然），则标记为“final”。 - 如果是“结束点”，则从T中删除它及其相应的起始点。

之后，所有标记为“final”的点都表示结果多边形的顶点。

设N为总点数。进一步假设测试是否应将点标记为“final”需要通过查找T花费O(log(n))时间，则整个算法为O(N*log(N))。

请注意，找到所有交点的任务可以并入上述算法中，因为高效地找到所有交点本身通常是扫描线算法。还要注意，结果点集可能包含不止一个多边形，这使得从“final”顶点重构解决方案多边形稍微困难。

- Philip