如何模拟从矩形交集开始的矩形并集

如果您不关心最小化返回的矩形数,可以将思维过程简化为始终返回不超过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。

假设我们用一对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,我们可以用它来计算必须添加到(左/上矩形)中的较小的右下矩形,使其成为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

很抱歉我不能给出有效的解决方案,但是…

起初,我会为你能想象到的每一个不同的情况画出如此美妙的图像。会有很多情况,你需要两个以上的矩形,或者只有一个,对吗?

我认为让rect包含其他的是微不足道的,但此时我想不出如何继续。:)

编辑:现在我正在考虑一个洪水填充算法,只需填充你的大矩形区域。但我可以想象,这有两个问题:如何使用洪水填充输出生成rect?这是正确的方法吗,或者有线性代数的解决方案吗?