math - 多个矩形的边界（凹）多边形？

Question

给定一组相交的矩形，是否有标准算法来找到它们的边界多边形？（一个多边形与矩形的并集完全相同的区域。）可以假设矩形都以相同的方式定向，边沿两个正交轴。

在搜索中，我找到了凸边界多边形的算法，但在这里我真的更喜欢只包含矩形覆盖的区域，这很可能是凹的。

（如果矩形完全围绕一个区域，则可以将其包含在边界多边形内。）

score 2 · Accepted Answer

我不知道是否有标准的方法可以做到这一点，但在我看来，边界多边形的顶点将是矩形的角和它们的边相交的点，不包括位于矩形内的点。

要对点进行排序，请从集合中的一个点开始。它要么是两条边的交点，要么是一个角，所以无论哪种方式，它都保证至少在两条边上。只需沿着其中一个边缘移动，直到到达下一个点。因为我们已经移除了内部点，所以我们总是会在到达内部之前碰到另一个顶点。

如果一个矩形的角沿另一个矩形的边缘，则必须小心，因为离开该角的一条路径将通向矩形的内部。所以有一些选择正确的边缘来追踪的元素。但是，如果您维护因位于内部而被排除的点的列表，您就会知道前往排除点是错误的方向。

编辑让我试着更明确地说。

(1) 从每个矩形的每一边开始。计算它们相交的位置并在那里分割边缘。

(2) 现在你有了一个段列表。检查每个段的端点以查看它们是否在任何矩形内。

(3) 现在取任意一个外部端点，它是至少一个段的端点，它具有另一个外部端点。绘制从您的端点到另一个外部端点的线。

(4) 该外部端点也应该是具有另一个外部端点的不同段的端点。画一条线到那个外部端点。

(5) 重复直到你回到你开始的端点。

score 1 · Accepted Answer

如果您需要计算矩形的并集，这就是计算几何中通常所说的“合并”操作。它通常通过扫描线算法轻松实现。

扫线方法通常需要相当大的初始投资：实施扫线引擎。一旦完成，引擎可以立即用于轻松地在输入几何上实现任何面向集合的操作，如“合并”、“与”、“或”、“差异”等。

同时，为轴定向（等轴测）几何实现扫描线引擎是一项相当简单的任务。当您需要处理大量输入时，即矩形数量相对较多时，这将是最佳方法。其他答案中提到的各种基于边缘遍历的方法仅适用于相对较小的输入。

2 回答 2