Algorithm of merging polygons

[Kuhl]

There are several polygons in an X-Y coordinate system. Each polygon
is described by listing the coordinates of all the vertices
sequentially. It's unpredictable whether there's overlap between each
polygon. I wish to merge them, which means that if there's overlap or
abutting between two polygons, then change them into one polygon which
covers exactly same area and location as before. Is there any
algorithm to implement this operation? Thanks.

[Rasmus Debitsch]

The term for this is "polygon clipping". E.g.: GPC at
http://www.cs.man.ac.uk/~toby/alan/software// or CGAL at
http://www.cgal.org/

Rasmus

"Kuhl" <chen_...@yahoo.com> schrieb im Newsbeitrag
news:040cd176-943e-4979...@r34g2000vba.googlegroups.com...

[Kenneth Sloan]

I

a) find a vertex which is guaranteed to be on the final perimeter (the
lowest, leftmost point should do)
b) walk that polygon, looking for intersections - switch input polygons
as needed at intersections
c) if there are still (disconnected) polygons - go to a)

II
Sweep-line: sweep a line from (say) top to bottom. Maintain a data
structure noting the (partial) boundaries, and "active edges". Look
for: a) "minimal" vertices (vertices where both edges leave the vertex
going AWAY from the sweepline) and b) intersections between active edges.

II (the modern way - INVOLVES CHEATING, but avoids certain numerical
issues at the cost of providing an "approximate" answer - never mind
that in a real computer your answer will be "approximate anyway)
Render all of your polygons into a framebuffer and then find the outline
of the resulting blob(s). For algorithms to do this, see I and II.

--
Kenneth Sloan Kennet...@gmail.com
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/