What's the opposite of polygon triangulation?

问题:

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:

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----->----->----->