Merging two overlapping rectangles into the resulting polygon

Question

I am looking for an algorithm that, given two rectangles that overlap partially or totally, finds the ordered list of vertexes that defines the polygon representing the sum of the two rectangles.

To be more specific:

I have as input two ordered list of points, representing the two rectangles
I know how to find the vertexes of the resulting polygon, which is formed by the vertexes of each rectangle which are outside the other rectangle, plus the intersection points between each edge of one rectangle with each edge of the other
I don't currently know how to order into an array the points, obtained as explained above, so that the element j and j+1 of the array represents the two vertexes of the same edge (this is what I mean by ordered list of vertexes).

Thanks in advance for any help

UPDATE : I found a way to sort vertexes to obtain a polygon, as follows:

compute the vertexes centroid ( coords average )
sort the vertexes by the angle formed between the segment from the centroid and the vertex and any reference line passing by the centroid (e.g. the X axis ).

However, although I consistently obtain a polygon enclosing the two rectangles, without holes or intersecting edges, it is not always the polygon I want ( sometimes it includes extra area not belonging to one of the input rectangles ).

So I'm going back to the solution pointed in one of the comments, which is also described here:

polygon union without holes

This is similar tohttps://stackguides.com/questions/8011267/area-of-rectangle-rectangle-intersection/8011422#8011422, and basically handled the same, just with different turning rules. — Codie CodeMonkey
Yep, i did not read that answer but I already tried something very similar to that approach, but kept stumbling in corner cases, particularly when some vertex of a rectangle lies on the edge of the other, which for how the two rectangles are constructed happen quite frequently. So I switched approach to the one outlined in the question, figuring it would have less corner cases. If that does not work, maybe I will go back to the first solution and try to work out the corner cases. — bieffe62

SGM1 SGM1 · Accepted Answer · 2014-04-04T00:19:46

Once you have the 4 vertices, you merely find the farther point using the distance formula (since it seems we can't make the assumption of a collinear or unrotated beginning rects)

So if you have points a = (xA, yA), b, c, d and you know these 4 points make a rectangle

float dist(Point a, Point b){
    float dx = a.x - b.x;
    float dy = a.y - b.y;
    return Math.sqrt(dx * dx + dy * dy);
}


//somewhere else, where u need it
//put point A into index 0
Point curFarthest = b;
float distance = dist(a, b);
if (dist(a, c) > distance){
    curFarther = c;
    distance = dist(a, c);
} else if (dist(a, d) > distance){
    curFarther = d;
    curFarthest = dist(a, d);
}

//store curFarthest into index 2
// store the rest (exculding points a and curFarthest)
// into index 1 and 3 in no particular order

Merging two overlapping rectangles into the resulting polygon

2 Answers