How to simulate a union of rectangles starting at the intersection of a rectangle

Question

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

Note. This is just one configuration of the rectangle solution set. the white rectangles above can be configured differently if they do not overlap.

Is there a simple algorithm for each case of intersecting rectangles? I made the first pass and I missed some corners. Apparently not mine.

Why? When panning in the user interface, I only want to (i) update the new parts of the canvas (ii) keep track of what was drawn as a rectangle (combining rectangles A and rectangle_ B).

Answer 1

If you are not interested in 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 quickly check each rectangle to see if r.x1 == r.x2 || r.y1 == r.y2 r.x1 == r.x2 || r.y1 == r.y2 (i.e. if it has a zero region) and throw it away if so. In most cases, more than half of the rectangles can be discarded this way.

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

Answer 2

Say we represent rectangles as a pair of x, y coordinate pairs: x1, y1 for the upper left and x2, y2 for the lower left corner. Suppose also that the y coordinate increases down and the x coordinates increase from left to right.

Now suppose that the rectangle formed by the union of A and B (according to your definition of a union) is a rectangle 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 a large rectangle U, we can use it to calculate the smaller right and lower rectangles that should be added to (left / top rectangle) to make it U. Lets call them Rt and Bot.

(This time, I assume that A is the top left rectangle if it is not swapping A and B. We also assume that the layout will look like the layout of your image. If it is not, you can easily adapt this).

 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 

Answer 3

I'm sorry that I can’t give a working solution, but ...

At first I would try to draw such beautiful images for every other occasion that you can imagine. There will be many cases when you need more than 2 rectangles or only one, right?

I think getting a line containing others is trivial, but at this time I can’t figure out how to proceed. :)

Edit: At this time, I’m thinking about a gulf fill algorithm, just fill your big rectangle. But there are two problems with this that I can imagine: how to use the fill fill stream to generate straight lines from it? Is this correct, or is there a solution to linear algebra or something else?