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.

Answer 2

I don't think it is SO difficult. I have answered the similar question on the friendly site and it was checked by a smaller community: https://cs.stackexchange.com/questions/20039/detect-closed-shapes-formed-by-points/20247#20247

• Let's look for a more common question - let's take curves instead of polygons. And let's allow them to go out of the picture border, but we'll count only for simple polygons that wholly belong to the picture.
• find all intersections by checking all pairs of segments, belonging to different curves. Of course, filter them before real check for intersection.
• Number all curves 1..n. Set some order of segments in them.
• For every point create a sequence of intersections SOI, so: if it starts from the border end, SOI[1] is null. If not, SOI[1]= (number of the first curve it is intersecting with, the sign of the left movement on the intersecting curve). Go on, writing down into SOI every intersection - number of curve if there is some, or 0 if it is the intersection with the border.
• Obviously, you are looking only for simple bordered areas, that have no curves inside.
• Pieces of curves between two adjacent non-null intersection points we'll call segments.
• Having SOI for each curve:
  • for segment of the curve 1, starting from the first point of the segment, make 2 attempts to draw a polygon of segments. It is 2 because you can go to 2 sides along the first intersecting curve.
  • For the right attempt, make only left turns, for the left attempt, make only the right turns.
  • If you arrive at point with no segment in the correct direction, the attempt fails. If you return to the curve 1, it success. You have a closed area.
  • Remember all successful attempts
  • Repeat this for all segments of curve 1
  • Repeat this for all other curves, checking all found areas against the already found ones. Two same adjacent segments is enough to consider areas equal.

How to find the orientation of the intersection.

When segment p(p1,p2) crosses segment q(q1,q2), we can count the vector multiplication of vectors pXq. We are interested in only sign of its Z coordinate - that is out of our plane. If it is +, q crosses p from left to right. If it is -, the q crosses p from right to left.

The Z coordinate of the vector multiplication is counted here as a determinant of matrix:

0         0          1
p2x-p1x   p2y-p1y    0
q2x-q1x   q2y-q1y    0

(of course, it could be written more simply, but it is a good memorization trick)

Of course, if you'll change all rights for lefts, nothing really changes in the algorithm as a whole.