Merge (Boolean Union) rectangular regions with integer accuracy

Question

Given any number of intersection, disjoint and touching rectangles, how to find the (multiple) outline polylines? Rectangles are defined in pixel coordinates so they have integer accuracy, but they may be thousands of units large.

I really need numeric coordinates for the outlines, merging GDI regions won't do. I know I can simplify the problem by creating a GDI region and calling GetRegionScans, but it still won't solve the problem.

This is part of real-time UI, so the algorithm needs to be reasonably fast (I'm guessing never more than a dozen or so boxes, maybe a hundred).

I'm doing this in C#, but since this is an algorithmic question I don't really care about language. Any ideas most welcome.

Answer 1

I have no idea if this satisfies your performance requirements, but it should work:

1. Start with an empty set of rectangles.
2. Add each rectangle to the set. If a rectangle overlaps an existing rectangle, split the rectangles into as many rectangles as needed, such that no rectangle overlaps another.
3. Add the four sides of each non-overlapping rectangle to a set of lines.
4. Remove all lines that are not unique.

The resulting set contains all the lines that make up the outline.

---