Algorithm for uniting a list of non-overlapping rectangles

Question

Input: An array of non-overlapping rectangles

Output: An array of points that outline all rectangles

A rectangle is represented like so: {x1, y1, x2, y2}

What I have tried

I have tried to use convex hull and concave hull algorithms.

These do not form an outline with purely horisontal and vertical lines.

(The output of these algorithms is not even proper for simplification)

Answer 1

It's difficult to define what the boundary is for arbitrary cases. However, if something you are looking for is illustrated by the posted picture, we can try to define a boundary by defining interior points.

Observing the difference between points in and out of the red boundary line in the picture, we can define an interior point as a point that has at least two distances in the following smaller than a given threshold:

• nearest distance to rectangles in +x direction
• nearest distance to rectangles in -x direction
• nearest distance to rectangles in +y direction
• nearest distance to rectangles in -y direction

I think there must be a distance threshold there, since the red line goes down and up in the first row, in which the two rectangles are far away to each other, while the red line is straight in the second row, where the two rectangles are near to each other.

If this definition is reasonable, we can use the following algorithm for your reference:

1. find minimal rectangle containing all rectangles
2. generate a m x n grid and compute the distance to the nearby rectangles in the 4 directions for each grid point.
3. classify the grid point as interior point or not by definition.
4. find a boundary point and trace.

I understand it's not a perfect solution. Here we ignore potential holes and islands for simplicity. The boundary might also not at the rectangle's edges due to grid discretization. I hope the solution can serve as a start point for the perfect one.