Calculating Cornerpoints and Edges of intersecting Recangles

Question

I am looking for an algorithm to find the outer edges and the cornerpoints of multiple overlapping rectangles.

Given are a number of rectangles, which are parallel to the axes, defined by: x, y, width and height.

Wanted are the cornerpoints of the emerging shapes, defined by: x, y and 2 neighboring cornerpoints.

Wanted are also the edges, defined by: 2 cornerpoints and a direction (North, East, South, West).

If a rectangle is completly inside others it can be ignored.

The algorithm does not have to be very optimized nor is memory a problem.

Answer 1

This can be solved by using polygon clipping algorithms; for example, those suggested by Vatti or Martinez. Using this technique:

• Treat each rectangle as a polygon (a path consisting of lines that trace the edges of the rectangle). The clipping algorithm assumes that each rectangle is traced in the same direction.
• Find the union of all the polygons.
• The resulting shape will then contain only points that lie on the outer edge of the polygon (these are the corner points you're looking for).

There is one corner case, though, if the resulting shape forms a hole. This will usually be traced in the opposite direction as the rest of the shape:

I don't know whether that matters, but if it does, you need to reverse the direction of any holes and recalculate the union from the shape and its holes, until no further holes appear.

To get the edge direction, the polygon clipper implementation needs to save information on the edges (in this case, the edge direction) as it clips them.