Bounding rectangle collision test?

Question

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

Answer 1

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.

Answer 2

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:

http://stackoverflow.com/questions/3453460/polygon-in-rectangle-algorithm/3453731#3453731

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.

Answer 3

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.

Answer 4

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.