I've asked this question at SO, but only answer I got is a non-answer as far as I can tell, so I would like to try my luck here.
Basically, I'm looking for a better-than-naive algorithm for the constructions of polygons out of union of many polygons, each with a list of Vertex $V$. The naive algorithm to find the union polygon(s) goes like this:
First take two polygons, union them,
and take another polygon, union it
with the union of the two polygons,
and repeat this process until every
single piece is considered. Then I will run
through the union polygon list and
check whether there are still some
polygons can be combined, and I will
repeat this step until a
satisfactory result is achieved.
Is there a smarter algorithm?
For this purpose, you can imagine each polygon as a jigsaw puzzle piece, when you complete them you will get a nice picture. But the catch is that a small portion ( say <5%) of the jigsaw is missing, and you are still require to form a picture as complete as possible; that's the polygon ( or polygons)– maybe with holes– that I want to form.
Note: I'm not asking about how to union two polygons, but I am asking about–given that I know how to union two polygons–how to union $n$ number of (where $n>>2$) polygons in an efficient manner.
Also,all the polygons can share edges, and some polygon's edge can be shared by one or many other polygon's edge. Polygons can't overlapped among themselves.
Best Answer
Likely the best method is to perform a simultaneous plane sweep of all the polygons. This is discussed in The Algorithms Design Manual under "Intersection Detection." (Algorithms to find the intersection can be altered to instead find the union.) It is also discussed in my textbook Computational Geometry in C, Chapter 7, "Intersection of NonConvex Polygons." The time complexity is $O(n \log n + k)$ for $n$ total vertices and $k$ intersection points between edges of different polygons.