math - 多个矩形的边界(凹)多边形？

Question

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

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

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

Answer 1

我不知道是否有标准的方法来做到这一点，但我想到边界多边形的顶点将是矩形的角及其边相交的点，并排除位于其中的那些点一个矩形。

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

如果一个矩形的角沿着另一个矩形的边缘，则必须小心，因为远离角的一条路径将通向矩形的内部。因此，需要选择要追踪的正确边缘。但是，如果您维护因位于内部而排除的点的列表，您就会知道前往排除点是错误的方向。

编辑让我尝试更明确地表达它。

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

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

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

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

(5) 重复此操作，直到返回开始时的端点。