Algorithm for the decomposition of polygons

Question

Does anyone know a relatively fast algorithm for decomposing a set of polygons into their distinct overlapping and non-overlapping regions, i.e. Given a set of n polygons, find all the distinct regions among them?

For instance, the input would be 4 polygons representing circles as shown below

and the output will be all polygons representing the distinct regions shown in the different colours.

I can write my own implementation using polygon operations but the algorithm will probably be slow and time consuming. I'm wondering if there's any optimised algorithm out there for this sort of problem.

Answer 1

Your problem in called the map overlay problem. It can be solved in O(n*log(n)+k*log(k)) time, where n is the number of segments and k is the number of segment intersections.

First you need to represent your polygons as a doubly connected edge list, different faces corresponding to the interiors of different polygons.

Then use the Bentley–Ottmann algorithm to find all segment intersections and rebuild the edge list. See: Computing the Overlay of Two Subdivisions or Subdivision representation and map overlay.

Finally, walk around each cycle in the edge list and collect faces of that cycle's half-edges. Every set of the faces will represent a distinct overlapping region.

See also: Shapefile Overlay Using a Doubly-Connected Edge List.