Algorithm to merge adjacent rectangles into polygo

Question

I guess that my problem is related to "convex hull", but no the same. All shapes in the drawing are rectangles with same width and height. Many are adjacent to each other. I want to combine those adjacent rectangles into polygons. Unlike "convex hull", the resuled polygons could be "hollow" inside.

Is there any open source algorithm available?

Answer 1

I have found a much simpler way:

1. Create a black image.
2. Draw filled rectangles on the image in white color. With this all the overlapped rectangles will be connected.
3. Find the contours of the blob.

That's it!

Answer 2

I had a similar problem earlier. I dont know exactly how you points are aligned, but mine was always spaced 5 meters apart for each other.

My solution was get the point out ordered by the x coordinate.

Had two lists, one called previous and one called current.

If current was empty then add the point to current. If current is not empty then check if the point is adjacent to one of the points in current (run the list through backwards as there is a higher chance a recent point is adjacent)

If the point is not adjacent to any point in current, then check if any of the points in current is adjacent to any point in the list previous. If yes, then merge(concat) them, if not then move the points from previous to another list holding the complete polygons, then set previous = current, empty current and add the point being processed to current.

Depending on how your points are proccesed(the order), you might need to run all the final polygons through again to check if they are adjacent to any of the other polygons.

Sorry for the long wall of text, let me know if you want to code, it is in c# and not very clean.