Joining polygons

[A. M. Santos R.]

Hello, I need an algorithm that receives polygons and outputs a single polygon that covers all.

Thanks in advance.

[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.

[A. M. Santos R.]

OK, I need the minimal polygon that covers a set of intersecting polygons. (Not necesarily the convex hull)

[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.

[A. M. Santos R.]

Thanks a lot.

[sohel]

Why do you have a poll for this thread?

[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.

[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)