Merge Overlapping Polygons

[superahoy]

I am trying to merge overlapping polygons into a single polygon to be rendered as a GL_LINE_LOOP, so really an outline of the merged polygons.
The polygons are simple, may be convex or concave, and are 2D.

I am currently using the glu tesselator to try and do this. I have set the glu properties and rules to

glu.gluTessProperty(tesselator,
glu.GLU_TESS_BOUNDARY_ONLY,
1.0);
glu.gluTessProperty(tesselator,
glu.GLU_TESS_WINDING_RULE,
glu.GLU_TESS_WINDING_NONZERO);

I start the polygon, render the first polygon as a contour, then render the second polygon as another contour, then end the polygon.

The glu tesselator gives a close answer, but some vertices will randomly go way off in either the x or y direction. If anyone has any ideas how to fix this or knows of a general polygon merging algorithm, I would greatly appreciate it.

This link shows what I am trying to do.
http://www.linkcad.com/site/tools/merge

[wizzo]

hum could you please tell why you want to merge them ?

i dont know the glu tesslator, but it looks like you cant get the new polygon's coordinate. if you want them back, then i think you can do something with a bit of collision detection :
- detect which vert are in another polygon
- find what edge are intersecting with other, and find the collision point
- delete the first ones (those who are in another poly)
- add the intersection vert

hope this helped a bit,
wizzo

[Kilam Malik]

A few things to mention:

- Did you overwrite the combine-callback? This is called whenever two lines are overlapping and it is needed to insert a new vertex. It's described in the RedBook. Winding rule NON_ZERO is ok, you could also use POSITIVE to achieve the same result.

- When you use the tesselator to draw the resulting polygon, it will run each frame. This will cause bad performance. You can install your own callbacks into the tesselator object. Then you save the new coordinates of the resulting polygon and use them to draw the polygon. I do this to get the tesselation of complete 3D objects. Of course you could also tesselate into a display list if you don't need the coordinates.

Kilam.

[superahoy]

Post #1
I want to merge the overlapping polygons to create a single bounding polygon. I am generating countours around shapes and want to merge the contours to create the bounding polygon.

Post #2
I have overloaded the combine callback, the vertex callback, the start callback, and the end callback. I intercept the vertices returned by the tesselator and store them away for rendering. And I looked at the values passed to the combine callback and the values were valid. It is in the vertex callback that some of the vertices simple "go off" out into nowhere. The bad vertices seem to show up where the 2 polygons would be intersecting, but like I said, the combine callback is getting valid points.

[Kilam Malik]

If the bad points are where you would expect the intersections to be, it's maybe a casting problem? If you would cast wrong in the combine function, the resulting points would be way off.

Just a thought...

Kilam.