How to identify the boundary points of area overlapped between 2 rectangles in 2D?

Question

I'm looking to return the coordinates of the points bounding the area of overlap between 2 arbitrary rectangles in 2D. Whats the best way to approach this that would take care of all the special cases eg:

• Rectangles intersecting only on a single vertex ? (the program would have to return the lone vertex)
• Rectangles which share whole or part of a side ? (the program would have to return the endpoints of the common line segment)

To add to the complexity, it has to order the points in either clockwise/anticlockwise order. As such, I can use a convex hull algorithm to order them before reporting, but if there's an algorithm that can figure out the bounding points in order directly, that'll be the best !!

Any ideas of what avenues I should be looking at ? I'm not looking for code projects etc, only a general idea of a generic algorithm for which I don't have to keep a lot of if "special case" then "do this" kind of code.

EDIT: The rectangles are arbitrary - i.e. they may/may not be parallel to X/Y axis...

Answer 1

Just use the general convex polygon intersection method. Look up intersect convex polygons rotating calipers.

Answer 2

Alright, we'll try this again...

Consider a union of the two, made up of areas defined by drawing a line from every vertex in ABCD (in black) to EFGH (in red):

The hard part here is coming up with all of the shapes defined by these lines (both the gray lines and the original lines coming from the ABCD and EFGH rectangles.)

Once you figure that out, create a linked list of these shapes, and assume every one of these shapes exists within the intersection.

Step 1. Translate & rotate everything so that ABCD has one vertex on 0,0 and its lines are parallel/perpendicular to the x and y axes.

Step 1A. Find the lowest y-value vertex in ABCD, and then subtract it from all other verts in the scene. Let's assume for the purposes of demonstration that that vertex is C. By subtracting C from every vertex in the scene, we will effectively move the origin (0,0) to C, making rotation around C easy.

for all shapes in linked list {
    for all vertices in shape {
        vertex -= C;
    }
}

Step 1B. Rotate everything about the origin by an angle equal to the angle between the C->B vector and the x-axis, so that B lands on the x-axis:

// see http://en.wikipedia.org/wiki/Atan2
float rotRadians = atan2(B.x, B.y);  // assuming ABCD vertices are labelled clockwise

for all shapes in linked list {
    for all vertices in shape {
        rot(thisVert, rotRadians);
    }
}


// ...

// function declaration
void rot(theVertex, theta) {
    tempX = theVertex.x;
    tempY = theVertex.y;

    theVertex.x = cos(theta) * tempX + sin(theta) * tempY;
    theVertex.y = cos(theta) * tempY - sin(theta) * tempX;

}

If ABCD vertices were labelled clockwise, the ABCD vertices should now look like this:

A = ABCDx , ABCDy
B = ABCDx ,   0
C = 0     ,   0
D = 0     , ABCDy

(If they were not labeled clockwise, then the "lies within" check in Step 2 won't work, so make sure the vert used in the atan2(...) call is the vertex counterclockwise from the lowest vertex.)

Step 2. Now we can easily analyze whether or not a shape lies within the ABCD rectangle, e.g. if (thisVert.x >= 0 && thisVert.y >= 0 && thisVert.x <= ABCDx && thisVert.y <= ABCDy). Traverse the linked list of shapes, and check to make sure each vertex of each shape lies within ABCD. If one vertex of a shape does not lie within ABCD, then that shape is not part of the ABCD/EFGH intersection. Mark it as not part of the intersection and skip to the next shape.

Step 3. Undo the rotation from Step 1B, then undo the translation from Step 1A.

Step 4. Repeat Steps 1-3 with EFGH instead of ABCD, and you will have your intersection set.

---

If the only intersection between the two sets is a line, then the above will return nothing as an intersection. If the intersection == NULL, then check for lines that intersect.

If the intersection is still NULL, then check for intersecting points.

Answer 3

This is probably really rough but:

object rectangle { 

     pos  { x, y }              // top-left position
     size { height, width }     // rectangle-size
}


collision::check (rectangle rect) {

     // collision-detection logic 

     collision->order_coords(coords);   // order-coords clockwise;
     return collision_result_object;    // return collided vertices, ordered clockwise, or 0 if rect hit nothing
}

collision::order_rects (rectangle *rect, opt angle)  {

     return clockwise_rects; // returns rectangles ordered clockwise
}

collision::order_coords (coordinate *coord, opt angle) {

     return ordered_coords; // recieves coordinates and returns ordered clockwise
}

rectangle rects; // bunch of rectangles

ordered_rects = collision->order_rects (rects); // order rects starting at 12PM

loop {    

       foreach ordered_rects as i {

           if (collision->check(i)) {

           array_of_collision_result_objects[i] = collision->check(i);      // start checking rects starting at 12PM, if collision found, return ordered vertexes
           }
       }

}

Answer 4

Find all the intersections of segments of rectangles. The result consists of some of them and some of initial vertices. To find them just check for every point it lies in both rectangles. Remove unnecessary points (if there are 3 or more on one line). The result is convex and no point you get is strictly inside it, so (if there are at least 3 of them) sort points from some inner point by angle and enjoy the result.

Answer 5

I've come up with a reasonable method that should cover all possible cases:

All we need is basically 3 steps :

Step 1:

for each side Si of R1
    for each side Sj of R2
           Check if Si and Sj intersect. If they do, push the point in results array
           (This also has to take care of the case in case Si and Sj overlap, which is 
           basically checking if they  have the same equation or not - if so, push in 
           the points of overlap. This also takes care of the case where a vertex of 
           R2 lies on Si).
    next
next

Step 2:

for each vertex Vi of R1
   Check if Vi lies inside R2, If so, push it in the results array.
next

Step 3:

for each vertex Vi of R2
   Check if Vi lies inside R1, If so, push it in the results array.
next

Now, order the results array, and return

For step 2 & 3 (how to find if a point lies inside a rectangle) - I'd use this excellent article (the last algorithm stated there).