Union of many (more than two) polygons without holes

Question

I'm creating union of polygons without holes. Input polygons are without holes and also output one should be. I already have working algorithm for finding it for two polygons. But in case of more than two there is a problem. As a union shouldn't be disjoint polygon, when I try to compute sum of them one by one I have a problem in such case:

Then polygon 1 meets polygon 2 the union is disjoint (so my algorithm does not compute sum). In second loop of course it makes union with 3rd and 4th polygon, but output is wihout 2nd polygon. So does any one know kind of fast and accurate algorithm of doing it? Probably a good idea would be to sort polygons by intersections first, but I can't think of any fast algorithms for that and also not quite I'm not sure how they should be sorted.

Answer 1

You could do this iteratively and produce a set of connected components (instead of always just a single connected component):

1. Put all polygons in an "open" list. Initialize a components list to empty.
2. While open is not empty:
   • Remove a polygon p from open and set flag changed to true.
   • Repeat while changed is true:
     • set changed to false
     • for each polygon q in open:
       • if q intersects p, remove q from open, set changed to true, and set p to the union of p and q.
   • add p to components.

At the end, components will consist of all the non-intersecting, connected components that can be formed by union of the input polygons. In your posted sample, it should produce a single polygon.

This is not the most efficient approach (see the algorithms in the link posted by Ricky Bobby), but it has the advantage of simplicity. Provided you aren't dealing with hundreds of polygons, it should perform just fine.

P.S. As @japreiss points out, a union can have holes even if none of the input polygons has a hole, even if the inputs are all convex polygons. If the inputs can be concave, then even a union of 2 polygons can have a hole. Does your 2-polygon algorithm handle that already?

Answer 2

I would use a sweeping line algorithm to find all edge ntersections, break contours at intersection points, then starting at (say) lowest-x-coordinate vertex walk along the edges, always selecting the outermost one. With a bit more work it is possible to get rid of the no-holes condition (holes are just differently oriented contours).