Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

how to simulate a rectangle union starting with a rectangle intersection

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).

like image 777
jedierikb Avatar asked Jul 14 '10 20:07

jedierikb


People also ask

How do you know if two rectangles overlap?

Two rectangles do not overlap if one of the following conditions is true. 1) One rectangle is above top edge of other rectangle. 2) One rectangle is on left side of left edge of other rectangle. We need to check above cases to find out if given rectangles overlap or not.

How do you check if two rectangles overlap with each other in python?

Practical Data Science using Python If we have two (axis-aligned) rectangles, we have to check whether they overlap or not. So, if the input is like R1 = [0,0,2,2], R2 = [1,1,3,3], then the output will be True. otherwise, return True.

How do you check if a line intersects a rectangle Python?

Get the dot product of all 4 vertices (the corners of the rectangle) with the direction vector of the line segment. If all 4 have values of the same sign, then all the vertices lie on the same side of the line (not the line segment, but the infinite line) and thus the line does not intersect the rectangle.


1 Answers

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).

like image 163
VeeArr Avatar answered Sep 21 '22 16:09

VeeArr