CODEWITHSUNDEEP
phpjavascriptalgorithmmathintersection
xx3004
xx3004

Reputation: 788

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

I come across this math problem which is needed to complete my application, so I'm asking for help.

Given 2 (or more, but basically for 2) rectangles with 2 known points for each: Top-left(x1, y1) and Bottom-right(x2, y2) (I can find the length with these info, if it is a need to solve the problem).

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

Is there anyway to determine if they have intersection, in area, I mean, if any part of this rectangle lays on any part of another one?

I've searched and found out a little help, but it does not solve the problem:

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

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

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

  • The top edge of one rectangle is under the bottom edge of the other one, means that the first one is completely laid under the second one, no intersection.

  • The bottom edge of one rectangle is above the top edge of the other one, means that the first one is completely laid above the second one, no intersection.

So I tried to reverse the conditions, which is if 4 of the above does not occur, the rectangles may intersect. But I still can find the condition (such as the picture above) in which 2 rectangles do not fulfill any condition, and still does not intersect.

Any help is highly appreciated, please show me the way to do it or algorithm or code (JS and PHP only please).

Big thank!

[x]

Upvotes: 4

Views: 3467

Answers (2)

donutdan4114
donutdan4114

Reputation: 1272

This is my two cents on the problem. Let me know if this can be improved upon. The examples I do myself seem to hold true with this code, however if you can give me example coordinates that make this fail, 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;
}

?>

Upvotes: 0

Jiri Kriz
Jiri Kriz

Reputation: 9292

An algorithm for the intersection detection ("overlapping") of any number of rectangles could work as follows. Two data structures are used.

  • A sorted list S of the x-coordinates of the left and right edges of the rectangles.
  • An interval tree T of the intervals given by the y-coordinates (bottom/top) of the rectangles.

The algorithm sweeps over the sorted list S of the x-coordinates:

  1. If the current x-coordinate is the left edge of a rectangle R then the y-coordinates [y1, y2] of R are compared to the interval tree T. If an overlap is found, then the algorithm stops and reports OVERLAP. If there was no overlap in the tree T, then the interval [y1, y2] is inserted into the tree.

  2. If the current x-coordinate is the right edge of a rectangle R then its y-interval [y1, y2] is removed from the interval tree T.

  3. If the sorted list S is completely processed, then there was no overlap. The algorithm stops and reports NO-OVERLAP.

The time complexity for N rectangles is O(N*log(N)) because for each 2*N x-coordinates a search in the interval tree for N intervals is performed. The space complexity is O(N) for the auxiliary data structures S and T.

Upvotes: 5

Related Questions