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.