how to simulate a rectangle union starting with a rectangle intersection

6
votes

Given rectangle_A intersecting rectangle_B, which has a union defined such that it is the rectangle containing both rectangles, I want to determine the coordinates of the (not overlapping) rectangles required to add to rectangle_A to create the union of rectangle_A and rectangle_B:

Note: this is just one configuration of the solution set of rectangles. the white rectangles above could be configured differently, as long as they don't overlap.

Is there a simple algorithm for every case of rectangle intersection? I've done a first pass and I miss some corners. Evidently not my forté.

Why? When panning in a UI, I only want to (i) update the new parts of the canvas (ii) keep track of what has been painted as a rectangle (the union of rectangle_A and rectangle_B).

3
algorithmgraphicsgeometry
Do you always have exactly two rectangles at a time? - ShreevatsaR
Yes, always just two original rectangles: A and B. These two rectangles can be completely different sizes. - jedierikb
I find this not clear-in the last image, which rules determine how the resulting rects must be? Your 3. image, would it be also valid to swich the to white rects? Or is "not overlapping" the only restriction? - InsertNickHere
And will they always intersect? Can it happen that one lies within the other? Can it happen that the x-range of rectangle B is entirely contained with the x-range of A (i.e. B lies "below" A, but with smaller width)? Similarly, can B lie to the right of A (intersecting, but not extending above or below) but with smaller height? - ShreevatsaR
Do you require a solution that presents the fewest possible number of rectangles? If not, a solution that always returns 8 (possibly zero-area) rectangles is trivial. - VeeArr

3 Answers

5
votes

If you are not concerned with minimizing the number of rectangles returned, you can simplify the thought process to one that always returns no more than 8 rectangles:

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

If you wanted, you could then quickly check each rectangle to see if r.x1 == r.x2 || r.y1 == r.y2 (i.e. if it has zero area), and throw it out if so. In most cases, over half of the rectangles can be thrown out this way.

For example, in your three examples, this solution would return 3, 1, and 5 rectangles, and would return 0 in the best case (when B is contained in A) and 8 in the worst case (when A is contained in B).

0
votes

Say we represent rectangles by a pair of x,y coordinate pairs: x1,y1 for the top-left and x2,y2 for the bottom left corner. Let's also assume y coordinate increase downwards and x coordinates increase left to right.

Now, suppose the rectangle formed by the union of A and B (according to your definition of union) is the rectangle is U.

So, 

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

Now that we have the larger rectangle U, we can use that to compute the smaller right and bottom rectangles that have to be added to A (the left/top rectangle) to make it U. Lets call them Rt and Bot.

(This time I'm assuming A is the top-left rectangle, if it isn't swap A and B. Also assuming the layout to be similar to that of your picture. If that isn't the case you can adapt this easily).

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
0
votes

I'm sorry i cant give a working solution, but...

At first I would try to draw such nice images for every different case that you can imagine. There will be a lot cases, where you need more than 2 rectangles, or just one, right?

I think getting the rect containing the others is trivial-but at this time I can't think of how to proceed. :)

Edit: At this time i'm thinking of a flood fill algorith, just fill up your larger rect. But there are 2 problems with this I can imagine: How to use the flood fill output to generate rects from it? Will it be the right way, or is there a linear algebra solution or something?