Math / Algorithm / JS: How to determine if 2+ rectangles intersect considering TopLeft (x0, y0) and Bottom-Right (x1, y1) of each rectangle

Question

I am facing this math problem that is needed to complete my application, so I ask for help.

For two (or more, but mostly 2) rectangles with two known points for each: Top left (x1, y1) and Bottom right (x2, y2) (I can find the length with this information if necessary to solve the problem )

TL(x1, y1) +-----------------+ | | | | TL(x3, y3) | | +---------------------------+ +-----------------+ | | BR(x2, y2) +---------------------------+ BR(x4, y4) 

In any case, to determine if they have an intersection, in a region, I mean, if any part of this rectangle lies on any part of another?

I searched and helped a little, but this does not solve the problem:

There are 4 conditions in which two rectangles will not intersect:

• The left edge of one rectangle is to the right of the right edge of the other, means that the first is completely laid on the right side of the second, without intersection.

• The right edge of one rectangle is to the left of the left edge of the other, which means that the first is completely laid on the left side of the second, without intersection.

• The upper edge of one rectangle is under the lower edge of the other, meaning that the first is completely laid out under the second, without intersection.

• The lower edge of one rectangle is above the upper edge of the other, which means that the first lies completely over the second, without intersection.

So, I tried to change the conditions, which means that 4 of the above does not happen, the rectangles can intersect. But I can still find a condition (for example, the image above) in which 2 rectangles do not fulfill any conditions and still do not intersect.

Any help is much appreciated, please show me a way to do this, either an algorithm or code (JS and PHP only).

Thank you very much!

[x]

Answer 1

The intersection detection algorithm ("overlap") of any number of rectangles can work as follows. Two data structures are used.

• Sorted list of x-coordinates of the left and right edges of the rectangles.
• Spacing tree

Answer 2

These are my two cents on the problem. Let me know if this can be improved. The examples that I myself do seem to match this code, however, if you can give me an example of the coordinates that make this unsuccessful, I would still like to work on this problem :)

  <?php //declare the points for your rectangles //'UL' means upper left points, and 'LR' means the lower right points $rectangle_array = array( $R1 = array("UL" => array("x" => 10, "y" => 20), "LR" => array("x" => 22, "y" => 5)), $R2 = array("UL" => array("x" => 32, "y" => 44), "LR" => array("x" => 65, "y" => 20)), $R3 = array("UL" => array("x" => 20, "y" => 16), "LR" => array("x" => 25, "y" => 10)) ); if (rectIntersect($rectangle_array)) { echo "THEY INTERSECT"; } else { echo "NO INTERSECTION"; } function rectIntersect($rectangles) { $num_rectangles = count($rectangles); for ($i = 0; $i < $num_rectangles; $i++) { //for each rectangle, compare points to every following rectangle $R1 = $rectangles[$i]; for ($k = $i; $k < ($num_rectangles - $i); $k++) { $R2 = $rectangles[$k + 1]; if ($R1['LR']['x'] > $R2['UL']['x'] && $R1['UL']['x'] < $R2['LR']['x']) { //rectangles cross on x-axis if (($R1['LR']['y'] < $R2['UL']['y'] && $R1['UR']['y'] < $R2['LR']['y']) || ($R1['UL']['y'] > $R2['LR']['y'] && $R1['LR']['y'] < $R2['UL']['y'])) { //rectangles intersect return true; } } } } return false; } ?>