Get contour of set of rectangles

Question

Hi,

I am looking for an algorithm to get contour of a figure created by a set of non-overlapping rectangles. The figure can be of any shape but it is simply-connected, i.e. contains no holes.

I need an idea on how to write a function like that:

IEnumerable<Point> GetContour( IEnumerable<Rect> rects )

Time complexity of the algorithm is not important, it just has to perform in reasonable time.

Answer 1

I would probably do this in two passes. The first would convert the rectangles into a collection of points (in winding order), including the points where the corner of another rectangle is a point along an edge. That way you'll end up with a graph of points where you can easily detect which points are shared between which rectangles.

With that, just search your graph for the first point with no shared rects and start walking routes along points that have up to no shared rects, or two shared rects where the previous point has no shared rects, until you get back to the starting point.

You'll need to maintain a stack for your route, as well as a map of previously explored points.

I did exactly this just recently (although it wasn't limited to rects and I already had the first pass done) and it worked quite nicely. I was seeing it able to calculate a route in a graph of about 30 points more times in a second than I could count in an int, so performance seemed pretty good, although that was in C++.

Answer 2

This seems a specific case of the concave hull problem.. many algorithms do exist to solve the opposite convex hull problems:

• Jarvis March (wikipedia) O(n^2)
• Graham Scan (wikipedia) O(nlogn)

These are simplest ones, there are at least 3 more but they just optimize performance, that is not one of your primary goals.

I think that Jarvis March can be easily adapted to your case, in which you just have rectangles. Think about the fact that on every passage this algorithm usually takes the first point on the right of the line that crosses last 2 points of the hull you are calculating, so with a better choose rule you can adapt it to be concave in the specific case of rectangles.

In any case there is also a specific concave hull algorithm described here: link, you can also download their API here (this should be the paper that describes the algorithm: link)