What's the opposite of tesselation?

0
votes

From what I understand, taking a polygon and breaking it up into composite triangles is called "tesselation". What's the opposite process called and can anyone link me to an algorithm for it?

Essentially, I have a list of 2D triangles and I need an algorithm to recombine them into a polygon.

Thanks!

3
graphicsgeometrycomputational-geometry
If I remember correctly, isn't tessellation when you can fit the same shape together without any gaps? – Adam Holmes

3 Answers

4
votes

I think you need to transform your triangles as a half edge data structure, and then you should be able to easily find the half edges which have no opposite.

alt text

2
votes

It's called mesh decimation. Here is some code I wrote to do this for a class. Tibur is correct that the half edge data structure makes this much more efficient.

http://www.cs.virginia.edu/~mjh7v/advgfx/proj1/

0
votes

The thing that you are calling tessellation is actually called triangulation. The thing you are searching for is tessellation (you may have heard of it referred to as tiling).

If you are more specific about the problem you are trying to solve (e.g. do you know the shape of the final polygon?) I can try to recommend some more specific algorithms.