Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Perhaps you should clarify the question. At one extreme you might be asking about a packing problem with irregular polygons, with a satisfactory solution obtained whenever the packing efficiency exceeds 95% by area. At the other extreme you might be asking about something very like a jigsaw puzzle in which there is a lot of additional information available to guide the solution (e.g. the missing pieces are similar to the given ones, there is a distinction between "edge" and interior pieces, the pieces fit in a globally cartesian manner, etc.). –  hardmath Dec 29 '10 at 13:34
    
@hardmath, I think you misunderstand my point; I'm actually asking about a polygon boolean operation problem, nothing to do with jigsaw puzzle! I don't know what makes you think that my problem has to do with jigsaw pieces, beyond the obvious fact that I'm just using it as an example. I could have use other objects as examples, as long as they are represented in polygonal form with a list of vertex. –  Graviton Dec 29 '10 at 13:39
    
To use the two-polygon example: do they share an edge? Do they overlap? Do the polygons have to be checked if they do intersect/overlap? –  J. M. Dec 29 '10 at 13:45
    
@J.M., they can share an edge, but they can never never overlap. And so no checking on whether they intersect is needed. Anyway does it matter? Since 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$ (where $n>>2$) polygons in an efficient manner. –  Graviton Dec 29 '10 at 13:48
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Martin Davis describes an approach on his blog which he calls "Cascading Union".

The approach is to traverse a spatial index like an R-tree, to union polygons that are likely to overlap or touch, which gets rid of a lot of internal vertices. The naive approach might not reduce the number of vertices at all between two iterations...

Martin Davis description (snippet):

This can be thought of as a post-order traversal of a tree, where the union is performed at each interior node. If the tree structure is determined by the spatial proximity of the input polygons, and there is overlap or adjacency in the input dataset, this algorithm can be quite efficient. This is because union operations higher in the tree are faster, since linework is "merged away" from the lower levels.

Cascading union

Complexity

I don't know the exact complexity of the algorithm, but could be similar to the sweep line algorithm, since the complexity of the algorithms depends on the number of vertices remaining in each step.

See also the full description of the Cascading Union algorithm on Martin Davis blog.

share|improve this answer
add comment

If the polygons either share exactly one edge or are disjoint then create a list of edges and the polygons they belong to and then remove each edge that has two polygons, joining those two polygons.

share|improve this answer
    
unfortunately the some edges of a polygon can be shared by one or many polygons. –  Graviton Dec 29 '10 at 14:03
    
How can that be if the polygons do not overlap? Can you show us a sample picture of the input polygons? –  lhf Dec 29 '10 at 14:12
    
next time when you address to me, you may want to add an alias in front of my name, i.e, @Ngu, so that I would get a notification. To answer your question, you can just imagine a jigsaw puzzles with a few missing pieces. Note that the pieces cannot overlapped at all! But one jigsaw piece can share its edge with one or many other jigsaw pieces. –  Graviton Dec 29 '10 at 14:59
1  
@Ngu, ah the polygons may share parts of edges then. In this case, first subdivide edges so that edges are shared fully, then follow my original advice. –  lhf Dec 29 '10 at 15:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.