Construct A Polygon Out of Union of Many Polygons
- by Ngu Soon Hui
Supposed that I have many polygons, what is the best algorithm to construct a polygon--maybe with holes- out of the union of all those polygons?
For my purpose, you can imagine each piece of a polygon as a jigsaw puzzle piece, when you complete them you will get a nice picture. But the catch is that a small portion <5% of the jigsaw is missing, and you are still require to form a picture as complete as possible; that's the polygon-- maybe with holes-- that I want to form.
My naive approach is to 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 union. 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 process until a satisfactory result is achieved.
But this seems to be like an extremely naive approach. I just wonder is there any other better algorithm?