Что противоположно тесселяции?

Question

Из того, что я понимаю, взятие многоугольника и разбиение его на составные треугольники называется "тесселяцией". Как называется противоположный процесс, и может ли кто-нибудь связать меня с алгоритмом для него?

По сути, у меня есть список двумерных треугольников, и мне нужен алгоритм для их рекомбинации в многоугольник.

Спасибо!

Answer 1

Я думаю, вам нужно преобразовать свои треугольники в структуру данных с половинным ребром , и тогда вы сможете легко найти половину ребер, у которых нет противоположных.

Answer 2

Это называется децимация сетки . Вот код, который я написал, чтобы сделать это для класса. Тибур прав, что структура данных с половинным краем делает это намного более эффективным.

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

Answer 3

То, что вы называете тесселяцией, на самом деле называется триангуляцией .То, что вы ищете, это тесселяция (вы, возможно, слышали о ней как о мозаике).

Если вы более конкретно описываете проблему, которую пытаетесь решить (например,знаете форму конечного многоугольника?) Я могу попытаться порекомендовать некоторые более конкретные алгоритмы.