What's the opposite of polygon triangulation?

2
votes

After I've done a 2D triangulation, some triangles have the same color and I want to recombine them for drawing into like-colored graphics paths. I find that if I just draw the triangles one by one, some graphic renderers shows seams between the triangles (at least if anti-aliasing and/or transparency is involved).

So how do I take a set of (non-overlapping) triangles and produce a graphics path, which may contain holes and disjoint polygons?

Blindly adding the triangles to a graphics path actually works pretty well for filling (though not for stroking, of course), but it doesn't feel right to export those extra interior points.

1
geometrycomputational-geometrytriangulationpathgeometrygraphicspath
remove all edges which occur more than once ? (where an edge is defined by the two points it connects) – Andre Holzner
Not a bad start, but there is still the issue of turning the remaining edges into a path, which is not trivial for touching polygons, and then figuring out which are holes of others. I am hoping there is a name for this kind of operation and a general algorithm that would handle partially shared edges. – xan

1 Answers

7
votes

Think of each triangle as an outline comprised of three vectors going in a counter-clockwise chain.

<--^
| /
|/ 
V

So for all the triangles in your shape, take the union of their outline vectors. If two outline vectors in the union are identical but go in opposite directions, they cancel each other out and are removed from the union.

For example, for two triangles that are side by side the union is 6 vectors

<--^^
| //|
|// |
VV-->

which reduces to 4 vectors because the two diagonal vectors in the middle cancel because they are identical but run in opposite directions:

<--^
|  |
|  |
V-->

You'll find this works for larger aggregations of triangles. Just connect the resulting vectors tail to head to get closed paths. Some of the closed paths may run clockwise, and these are holes.

<-----<-----<-----^
|                 |
|                 |
V     ^----->     ^
|     |     |     |
|     |     |     |
V     <-----V     ^
|                 |
|                 |
V----->----->----->