CODEWITHSUNDEEP
c++c
jmasterx
jmasterx

Reputation: 54173

Bounding rectangle collision test?

I have complex polygons which I know the minimum x, minimum y, maximum x and maximum y. I also have another rectangle which I know the top left and bottom right vertices. Knowing this information, how can I know if these 2 bounding boxes are colliding? Thanks

Upvotes: 2

Views: 2491

Answers (4)

bta
bta

Reputation: 45087

Try something like this:

typedef struct rect {
    int top;     // maximum y-coord
    int bottom;  // minimum y-coord
    int left;    // minimum x-coord
    int right;   // maximum x-coord
} rectangle;

// Returns 1 if the point (x, y) lies within the rectangle, 0 otherwise
int is_point_in_rectangle(rectangle r, int x, int y) {
    if ((r.left   <= x && r.right >= x) &&
        (r.bottom <= y && r.top   >= y))
        return 1;
    return 0;
}

// Returns 1 if the rectangles overlap, 0 otherwise
int do_rectangles_intersect(rectangle a, rectangle b) {
    if ( is_point_in_rectangle(a, b.left , b.top   ) ||
         is_point_in_rectangle(a, b.right, b.top   ) ||
         is_point_in_rectangle(a, b.left , b.bottom) ||
         is_point_in_rectangle(a, b.right, b.bottom))
        return 1;
    if ( is_point_in_rectangle(b, a.left , a.top   ) ||
         is_point_in_rectangle(b, a.right, a.top   ) ||
         is_point_in_rectangle(b, a.left , a.bottom) ||
         is_point_in_rectangle(b, a.right, a.bottom))
        return 1;
    return 0;
}

You can do the same for any polygon, just iterate through all of its points and call is_point_in_rectangle with them. Since you only have a bounding box for the complex polygon, there is a chance that this method gives you a false positive (that is, the rectangle is inside the complex polygon's bounding box but outside of the polygon itself). However, this restriction applies to any method where a complex shape is simplified to a bounding box.

Upvotes: 3

josh
josh

Reputation: 14443

Create a sorted array of the x coordinates of the left and right edges of the rectangles. Then, use a "scanline" to move from left to right through the rectangles. Keep a binary search tree containing the y coordinates of the top and bottom edges of the rectangles that overlap the scanline. For each element of the array, check whether it is a left or right edge. If it is a right edge, remove the corresponding top and bottom edges from the BST. If it is a left edge, search the BST for rectangles that overlap the current rectangle; if there is one, return the overlap. Then, add the y coordinates of the top and bottom edges of the rectangle to the BST. The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles and each of the 2n iterations takes O(log n) time - Copied from google search results.

Upvotes: 0

ysap
ysap

Reputation: 8115

I think the following works most of the times, but it is surely more accurate than bounding box check, although more complex. Take a look at the following question:

Polygon in rectangle algorithm?

There, you see an algorithm for finding out if a point is inside a polygon. You can apply this test to each point of the 1st poly w.r.t. the 2nd one. Then the opposite. If the test passes at least once, you have a collision.

Upvotes: 0

Gintautas Miliauskas
Gintautas Miliauskas

Reputation: 7892

Rectangles A and B are colliding if the intervals [Ax1, Ax2] and [Bx1, Bx2] are overlapping and the intervals [Ay1, Ay2] and [By1, By2] are overlapping.

Upvotes: 2

Related Questions