Page 1 of 1
Joining polygons
Posted: Fri Dec 21, 2007 11:01 pm
by A. M. Santos R.
Hello, I need an algorithm that receives polygons and outputs a single polygon that covers all.
Thanks in advance.
Posted: Fri Dec 21, 2007 11:10 pm
by mf
How about a big square with vertices (a,a), (-a,a), (-a,-a), (a,-a), where a is any constant, greater than absolute value of any coordinate in the input? Or a convex hull of all input points?
Be more specific in what kind of polygon you need.
Posted: Fri Dec 21, 2007 11:15 pm
by A. M. Santos R.
OK, I need the minimal polygon that covers a set of intersecting polygons. (Not necesarily the convex hull)
Posted: Fri Dec 21, 2007 11:45 pm
by mf
One simple O(n^2) algorithm is this:
First, for each edge of every polygon, find at which points other edges intersect it, and split it into multiple edges at these points. Then choose a vertex P0, which is known to be at the border of union of polygons, for example the one with smallest x coordinate, and in case of a tie, smallest y.
Starting from P0, at each step choose an edge incident to current vertex, which makes largest right-hand turn, and follow it until you come back to P0. The polyline that this process traces is what you're looking for, I guess.
Posted: Sat Dec 22, 2007 2:52 am
by A. M. Santos R.
Thanks a lot. 
Posted: Sat Dec 22, 2007 8:01 am
by sohel
Why do you have a poll for this thread?
Posted: Sat Dec 22, 2007 5:14 pm
by A. M. Santos R.
Whether nobody post a response I would have deleted it. I think there are unnecesary threads in the entire board that should be removed to keep it simple, readable and organized.
Posted: Sun Dec 23, 2007 5:22 pm
by maxdiver
Is this problem the same problem as "external(outside) border(verge) of polygon"?
(I know English badly, so I'm not quite sure of English transcription)