Merge mesh triangles into polygons: need help with vertex ordering

Questions & Answers
1

I’ve got an algorithm that takes triangular based meshes and creates a polygon based “mesh” from it. It seems to be working well except for one point.

When I do merge triangles or polygons(previously merged triangles) together (they must lie on the same plane and share an edge to be merged) into a poly, the points are no longer in “counterclockwise” order.

What I have been doing is, given poly1 and poly2:
Remove the shared vertices from poly2, and then append the remaining vertices to poly1.

While this does get all the points I need into the polygon, it also, sometimes, messes up the order of the points. (even for a simple cube!)

This method also does NOT get rid of all unneeded points: consider a pie-slice-like, pentagon of triangles. Once I add the last triangle of the pentagon, the center vertex should be eliminated. But I have no idea how to check for such a condition.

QUESTIONS:
How can ensure my polygons vertex order is correct (ideally WHILE merging two polys)?
How can I detect if particular vertex points need to be eliminated (like the center of the pie-slices)?

Thoughts: I was considering the following solution, but it won’t work for concave polygons, nor will it help with that center vertex removal I exampled above:
Randomly select an interior point. Compute the angle between that point and each vertex. Sort vertices based on that angle.

I’ve researched this a bit, and found some good stuff, but nothing that has really helped with this particular minutiae of the algorithm. My initial research also failed to find an open-source-library which does this algorithm already, which was surprising, until I remembered I’m totally awful at searches.

UPDATE: progress so far…
we know merging polys shared at least 2 vertices(flush)… so:

Rather than APPEND the vertices from one poly to another when merging,
we must INSERT the vertices from one poly BETWEEN the two shared vertices of the other.

Furthermore, if we are merging a triangle and a poly, if we have 3 shared vertices, we REMOVE the middle shared vertex from the poly. (to get rid of the vertex in the center of the pie)

Working better now, but sill having a few issues (though it may just be a bug in my implementation of the above).

Update2:
I managed to get an implementation going that creates an EDGE rather than a polygon, on triangles that are FLUSH , but NOT parallel (edge is created between the two shared vertices-“flush”). this seems to work for closed surface meshes only.

Update3: OK, getting REALLY close now. The ONLY issue remaining is one I though I had solved, but haven’t. When combining two polys that share THREE vertices, this means I am “CLOSING” the polygon. I will need to insert all the vertices (except those shared), from poly A, between two of the three shared vertices of poly B, and remove the last shared vertex (the interior point) from the final poly. I remain unable to figure out which two points to insert between, and which point to remove. My intuition tells me it has to do the the number of vertices listed BETWEEN the three vertices in question, but I don’t see it yet.

2

I eventually found a solution, here is the psudo-code:

Merge poly A into B

 Find first TWO or THREE shared verticies
 If we find exactly 3 shared verticies:
       -We compute the different between every shared vertex-index in B with every other shared-vertex in B
       -The differences that has a value of "2" specifies which of the two indices have the third BETWEEN them.
       -This third, between point, is the one    we will want to discard.
 Once that point is discarded we insert all the verticies from the second poly (excluding any shared    points) in exactly the same order as the original.   NOTE: This last part ASSUMES the two polygons are facing the same direction, vertex order-wise, before merging.
    -If our two points straddle the end or the vertex list, we insert at the end of the vertex list.