如何模拟一个矩形联合，从一个矩形交集开始

Question

给定相交的矩形A和矩形B，其中并集被定义为包含两个矩形的矩形，我想确定所需的（不重叠的）矩形的坐标以添加到矩形A中，以创建矩形A和矩形B的并集：

注意：这只是解决方案集合的一个配置。上面的白色矩形可以以不同的方式配置，只要它们不重叠。

是否有一个简单的算法适用于每种矩形相交情况？我已经进行了第一次尝试，但我错过了一些角落。显然这不是我的强项。

为什么？在UI中平移时，我只想（i）更新画布的新部分（ii）跟踪已绘制的矩形（矩形A和矩形B的并集）。

- jedierikb

---

是的，始终只有两个原始矩形：A和B。这两个矩形可以完全不同大小。 - jedierikb

我觉得这不太清楚——在最后一张图片中，哪些规则决定了结果矩形的位置？对于你的第三张图片，如果将两个白色矩形交换位置，是否也是有效的呢？或者说“不重叠”是唯一的限制条件吗？ - InsertNickHere

它们会一直相交吗？有可能一个矩形位于另一个矩形内部吗？B的x范围完全包含在A的x范围内（即B位于A“下方”，但宽度较小）是否可能发生？同样地，B是否可以位于A的右侧（相交，但不向上或向下延伸），但高度较小？ - ShreevatsaR

@InsertNickHere：好观点。只要矩形不重叠，解决方案可以采用任何配置。我会在原始帖子中进行澄清。 - jedierikb

您是否需要一个呈现最少矩形数量的解决方案？如果不需要，总是返回8个（可能为零面积）矩形的解决方案就很简单。 - VeeArr

Answer 1

如果您不关心最小化返回的矩形数量，您可以简化思考过程，始终返回不超过8个矩形：

U
+----------+----+-------+
|          |    |       |
|     1    | 2  |  3    |
+----------+----+-------+
|          |    |       |
|     4    | A  |  5    |
|          |    |       |
+----------+----+-------+
|     6    | 7  |  8    |
+----------+----+-------+

U.x1 = min(A.x1,B.x1)
U.x2 = max(A.x2,B.x2)
U.y1 = min(A.y1,B.y1)
U.y2 = max(A.y2,B.y2)
R1.x1 = R4.x1 = R6.x1 = U.x1
R2.x1 = R7.x1 = R1.x2 = R4.x2 = R6.x2 = A.x1
R2.x2 = R7.x2 = R3.x1 = R5.x1 = R8.x1 = A.x2
R3.x2 = R5.x2 = R8.x2 = U.x2
R1.y1 = R2.y1 = R3.y1 = U.y1
R1.y2 = R2.y2 = R3.y2 = R4.y1 = R5.y1 = A.y1
R4.y2 = R5.y2 = R6.y1 = R7.y1 = R8.y1 = A.y2
R6.y2 = R7.y2 = R8.y2 = U.y2

如果你愿意，你可以快速检查每个矩形是否满足r.x1 == r.x2 || r.y1 == r.y2（即它的面积为零），如果是，则将其排除。在大多数情况下，这种方式可以排除超过一半的矩形。

例如，在您的三个示例中，此解决方案将返回3、1和5个矩形，并且在最佳情况下（B包含在A中）返回0，在最坏情况下（A包含在B中）返回8个矩形。

- VeeArr

---

没错！关于A和B如何相交的讨论似乎不相关。您始终可以将1、2、3合并成一个，将6、7、8合并成另一个，从而获得不超过4个矩形（如果A完全在外部矩形内，则会给出最优解）。如果A接触其中一条边，它也会给出2或3的最优解。 - Aryabhatta

+1 这种技术相对容易实现，而且可以处理矩形 A 与 B 之间的任何位置关系。由于并集的工作方式，你应该总是有 3-5 个这些矩形可以忽略（它们的面积为零）。在剩下的矩形中，将相邻的矩形组合起来并减少你需要处理的多边形数量应该相对简单。 - bta

Answer 2

假设我们用一对x，y坐标对来表示矩形：左上角为x1，y1，右下角为x2，y2。同时，我们假设y坐标向下增加，x坐标从左到右增加。

现在，假设根据您对联合的定义，由A和B组成的矩形是矩形U。

因此，

U.x1=min(A.x1,B.x1), U.y1=min(A.y1,B.y2) --- top-left corner, take the lowest values
U.x2=max(A.x2,B.x2), U.y2=max(A.y2,B.y2) --- bottom-right corner, take the highest values

现在我们有了更大的矩形U，我们可以使用它来计算必须添加到A（左/上矩形）的较小的右侧和底部矩形，以使其成为U。让我们称它们为Rt和Bot。

（这次我假设A是左上角的矩形，如果不是，请交换A和B。还假设布局类似于您的图片。如果不是这种情况，您可以轻松地进行调整）。

Rt.x1=A.x2, Rt.y1=A.y1
Rt.x2=A.x2, Rt.y2=B.y2

Bot.x1=A.x1, Bot.y1=A.y2
Bot.x2=A.x2, Bot.y2=B.y2

- MAK

---

我相信这只能解决给定问题（在图像中），但有许多情况需要添加超过2个或仅1个矩形。问题仍然是如何在所有情况下找到矩形，硬编码肯定不是一个好的方法。 - InsertNickHere

@InsertNickHere：正如我在答案中所写的那样，我假设布局是最后一半中所显示的图表。如果B比A大并且实际上覆盖了A并延伸到所有侧面，则需要超过2个。在这种情况下，U=B，只需从中推导出额外的矩形。如果只需要不到2个额外的矩形，我的方法将返回面积为0的矩形。只需检查即可。 - MAK

Answer 3

很抱歉我不能提供一个可行的解决方案，但是...

首先，我会尝试为你能想象到的每种不同情况绘制漂亮的图像。有很多情况，你需要超过2个矩形或只需要一个，对吧？

我认为获取包含其他矩形的矩形是微不足道的，但此时我无法想出如何继续。 :)

编辑：此时我正在考虑使用泛洪算法，只需填充您更大的矩形即可。但是我可以想象到两个问题：如何使用泛洪输出从中生成矩形？这是否是正确的方法，还是有线性代数解决方案或其他方法？

- InsertNickHere