How can I find a natural border polygon of a set of arbitrarily placed non-overlapping rectangles?

Question

Given a set of arbitrarily placed, non-overlapping rectangles; how could I find a polygon that represents a natural border around the points that make up the rectangles? To illustrate:

How can I find either the green or blue line? I have tried, but not succeeded, with the following:

• Walking using pathfinding. I struggled to find a heuristic that made sense.
• Walking using distance threshold and choosing next based on angle about the vector of the previous two points (e.g. always turn right). This kinda worked but had a lot of weird edge cases that didn't.
• Procedurally building up the polygon starting with an initial diamond of the left, top, right and bottom most points. The idea was to detect if a point was inside the polgyon already, in which case ignore it, but when I needed to insert I didn't know how to determine the insert position.

I'm unsure if I'm missing something obvious or if this is actually a harder problem than I initially expected.

Answer 1

Here is a heuristic. Compute the hull H₁ of the rectangles. Now compute the hull H₂ of the rectangle corners not on H₁. So now you have two nested convex hulls. Consider moving an edge e of H₁ to a vertex v of H₂. Some such moves can be excluded because the two new edges cross a rectangle. Choose to accept the smallest altitudes of the triangle formed by e and v, as suggested in the image below.

---

   

---