Как преобразовать бинарное дерево в полигональную триангуляцию и наоборот

Согласно википедии, существует биекция (соответствие 1:1) между двоичным деревом n - 2 узла и простая полигональная триангуляция n-vertex. Мне интересно, как преобразовать между собой*?
Другими словами, как преобразовать множество треугольников в двоичное дерево и как преобразовать двоичное дерево в множество треугольников? Треугольник представляет собой тройку вершин по часовой стрелке (v0, v1, v2) и соединяет соседние треугольники (n0, n1, n2).
* с точки зрения программиста, алгоритм, пример кода и т. д.


algorithm polygon binary-tree triangulation
person wondra    schedule 29.11.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вот рекурсивная биекция.

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

Индуктивно дерево имеет хотя бы один внутренний узел. Предположим, что вершины многоугольника имеют ранее существовавшие метки от 1 до n в порядке по часовой стрелке. Исследуйте уникальный треугольник T, содержащий ребро 12.

   1-----2
  /|    /|\
 / | T / | \
6  |  /  |  3
 \ | /   | /
  \|/    |/
   5-----4

Если мы удалим T, мы получим два треугольных многоугольника. В этом случае мы получаем 2345 и 156. Рекурсивно биецируем многоугольник, включающий 1, чтобы получить левое поддерево корня. Рекурсивно биецируйте многоугольник, включая 2, чтобы получить правильное поддерево корня.

Особенно изящный способ увидеть эту биекцию состоит в том, что мы получаем дерево, беря планарный двойственный граф триангуляции, удаляя ребра, инцидентные бесконечной грани, и обозначая грань, смежную с 12, как корень.

person David Eisenstat    schedule 30.11.2014
comment
Благодаря вашему посту я только что понял - набор треугольников уже является бинарным деревом. Если мы продвигаем n0 в левую дочернюю ссылку, n1 в родительскую ссылку и n2 в правую дочернюю ссылку, всегда есть способ сдвинуть вершины дочернего треугольника (и соседние ссылки), чтобы они удовлетворяли условию выше. Приняв соглашение, что n0 противоположно v0. - person wondra; 30.11.2014