Polygon Merge Algorithm

OpenGL
1

I am interest in an algorithm which will merge 2 polygons to give the outside border of the 2 polygons.
I have tried using the gluTesselator with the GLU_TESS_BOUNDARY_ONLY function and it has come close, but it give random junk vertices in some places. If anyone knows where I can find an example algorithm or has used the gluTesselator and knows a fix for the bad vertices thing, I would greatly appreciate it.

2

Will the two polys always be convex?

3

The polygons are not guaranteed to be convex. I can guarantee that the polygon vertices will be orderd Counter-Clockwise (or clockwise if necessary), and the polygons will not overlap themselves (no figure 8s for example).

The merged polygon will not be displayed as filled polygon. It will be rendered as a GL_LINE_LOOP.

4

How do you arrive at a merge orientation. Do you manually choose an edge to share? I’m trying to get a picture of your situation.

5

Here is how I setup the tesselator winding rules.
Ingore the glu. stuff, the program is in Java.
I have also tried the GLU_TESS_WINDING_POSITIVE with the same results.

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

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

I then start the polygon, begin and end contour 1 with the first polygon, begin and end contour 2 with the second polygon, then end the polygon. This doesnt require a point to share.

When I tried to do this myself, I ordered the points counter-clockwise with the furthest left point set as the first point in each polygons set of points. I then would start the merge with the polygon whose first point was leftmost to guarantee that the point was outside the other polygon ( I had checked to make sure one polygon was not enclosed by the other ).

6

I see. I was thinking adjacent polygons, not a contour as a hole.

Your setup looks okay to me. Are your polygons simple? What are these junk vertices you speak of? All the vertices in the winding are deemed necessary by the tesselator (to forma a continuous line loop, for example). It sould be possible to remove any vertices you see fit, by inspecting the contour vertex adjacency. That is, remove the “bridge” vertices between contours (if I understand your problem). A picture would help here.

 
--------------*------------- contour A
              | 
--------------*------------- contour B
              ^
    connecting vertex is junk?
7

For anyone interested, there’s a nice little tutorial on polygon tesselation using GLU here:

http://www.flipcode.com/tutorials/tut_tesselation.shtml