如何模拟以矩形交集开始的矩形联合

Question

给定rectangle_A交叉的rectangle_B,它有一个定义的联合使得它是包含两个矩形的矩形,我想确定添加到rectangle_A以创建rectangle_A和rectangle_B的并集所需的(不重叠)矩形的坐标:

注意:这只是矩形解集的一种配置.上面的白色矩形可以配置不同,只要它们不重叠即可.

每个矩形交叉的情况都有一个简单的算法吗？我做了第一次传球,我错过了一些角落.显然不是我的强项.

为什么？在UI中进行平移时,我只想(i)更新画布的新部分(ii)跟踪绘制为矩形的内容(rectangle_A和rectangle_B的并集).

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,在最坏情况下返回8(当A包含在B中时) .