Union of many (more than two) polygons without holes

Question

Im creates a union of polygons without holes. Input polygons do not have holes, and there should be an output. I already have an algorithm for finding two polygons. But there are more than two problems. Since the union should not be a disjoint polygon when I try to calculate their sum one by one, I have a problem in this case:

Then polygon 1 meets polygon 2, the union does not intersect (so my algorithm does not calculate the sum). In the second cycle c, it combines with the 3rd and 4th polygons, but the output has a second polygon. Does anyone know a quick and accurate algorithm for its implementation? It would probably be a good idea to sort the polygons by intersections first, but I can't think of any quick algorithms for this, and also not really. I'm not sure how to sort them.

Answer 1

You should not look at the polygons one by one.

You can apply either of the two algorithms from this question a polygon without holes directly with n polygons.

hope this helps

Answer 2

You can do it iteratively and create a set of connected components (instead of always only one connected component):

• Put all the polygons in the "open" list. Initialize the list of components to empty.
• Until open is empty:
  • Remove the polygon p from the open and set the flag to true.
  • Repeat on change true:
    • set changed to false
    • for each polygon q in open:
      • If q crosses p, remove q from open, change to true and set p to the union of p and q.
  • add p to the components.

At the end, the components will consist of all disjoint, connected components that can be formed by a union of the input polygons. In your placed pattern, it should create one 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. If you are not dealing with hundreds of polygons, it should work just fine.

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

Answer 3

I would use a strict line algorithm to find all the edge ntersections, split the contours at the intersection points, and then start at (say) the vertex with the smallest x coordinate at the edges, always choosing the outermost one. With a bit more work, you can get rid of the state without holes (holes are just different oriented contours).