Триангуляция Делоне с ограничением

В рамках научно-образовательного проекта «Маемся дурью» мне понадобилось сделать хитрую триангуляцию набора точек.

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

Ниже я расскажу, что у меня получилось.
Дано:

• Список двухмерных точек, по которым нужно построить треугольную сетку
• Внешний контур любой сложности, в том числе вогнутый (не пересекающийся)
• Список внутренних контуров, можно вогнутых (дырки)

Контуры пересекаться не могут, уровень вложенности только один (внешний контур и дырки).

Ограничений по времени и памяти нет.
Треугольники желательно «красивые», без длинных тонких соплей, соответственно нужна триангуляция Делоне.
Чем проще алгоритм, тем лучше.

По привычке, начал поиск в залежах сети.
Сложилось такое впечатление, что триангуляция это какая-то rocket science.
Информации мало, простых туториалов еще меньше. Или какая-то высоко-ученая муть, без капли практики, или тупо исходники, без объяснений.
Причем, триангуляция с ограничениями по контурам вообще практически нигде не описывается.
Ситуация одинаковая как на русском, так и на английском языках.

Из нормального удалось найти:
window.edu.ru/window_catalog/files/r23861/09.pdf
Обзор различных алгоритмов, более-менее просто и понятно. Правда половина алгоритмов добавлена исключительно для объема. Ограничение по контуру через задницу.

algolist.manual.ru/maths/geom/deluanay.php
Кривой перевод из книжки. Мертвые и живые ребра, какие-то пузыри надувают, упоротые что ли.
Базовая Делоне триангуляция, взял этот алгоритм за основу.
По предыдущей ссылке он описан как «прямой» алгоритм построения.

code.google.com/p/poly2tri/
Вот тут быстрый и хороший алгоритм, но не на AS3. Исходники даже не смотрел, но картинка на главной красивая.

Отмазки.
«Мой» алгоритм заведомо не оптимален, как в плане структур данных, так и в плане оптимизации самого алгоритма.
Если захотите использовать (особенно в real-time), его надо полностью переписать, а еще лучше взять за основу какой-нибудь другой алгоритм.


Общее описание алгоритма (пока без обработки контуров):
1. Создаем массив точек, заносим туда все точки, которые используются в триангуляции. Сюда входят точки всех контуров и «свободные» точки, если такие существуют.
2. Создаем 2 фейковые точки (для первичного ребра). Первичное ребро должно лежать таким образом, чтобы все(!) остальные точки находились справа от него. Проще всего создать горизонтальное ребро, лежащее выше остальных точек.
3. Создаем список активных ребер и заносим туда первичное ребро.
4. Пока список активных ребер не пуст:
4.1. Вытаскиваем любое ребро (удаляем их списка).
4.2. Находим точку, лежащую справа от ребра и образующую максимальный угол между векторами от точки к обоим концам ребра.
4.3. Если нашли точку:
4.3.1. Сохраняем полученный треугольник.
4.3.2. Сохраняем 2 новых ребра, с инвертированными нормалями. Чтобы справа у этих ребер были остальные точки, а слева полученный треугольник.
Сохраняем ребра тоже хитро. Если ребро с такими точками уже есть в списке, удаляем ребро из списка, иначе добавляем. Про активные ребра см. по второй ссылке вверху, там все на картинке понятно нарисовано.



Собственно, вот и весь алгоритм. Получаем на выходе обычную триангуляцию Делоне.
Единственная возможная оптимизация — в поиске лучшей точки. Про это написано в первой ссылке сверху.

Ограничения на триангуляцию. Контуры.
Контур, в данном алгоритме, это замкнутый полигон без самопересечения. Может быть вогнутым.
Контуры не могут пересекаться, иметь общих точек или ребер.
Контур задан списком точек.
Внешний контур ориентирован по часовой стрелке, внутренние — как угодно.
В чем смысл контуров? Контуры задают ребра, которые обязательно должны присутствовать в сетке и эти ребра не могут пересекаться с другими ребрами.

Обычная триангуляция Делоне по набору точек не может узнать какое ребро должно обязательно присутствовать в сетке и создает ребра по наибольшему углу.
При этом возможны вот такие случаи (добавлено немного «мусорных» свободных точек, чтобы было понятнее):



Красным — внешний контур.
Фиолетовым — внутренние.

Решение простое.
При поиске точки, перед тем, как проверять на максимальный угол, делается дополнительная проверка на то, что новые ребра не будут пересекаться с ребрами контуров. Если пересечение будет — точка отбрасывается.
Таким образом, незначительно ухудшая триангуляцию, мы получаем выполнение одного из условий — ребра не могут пересекать контуры.



Остается последнее условие. Ограничение внешним контуром.
Это значит, что все треугольники, снаружи внешнего контура или внутри внутренних контуров необходимо убрать.

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

Мы пойдем другим путем:
1. Возьмем любое ребро внешнего контура (первое, к примеру).
2. У этого ребра есть 1 или 2 соседних треугольника. Треугольник справа от этого ребра будет лежать в контуре, поскольку внешний контур мы задавали по часовой стрелке и контуры не пересекаются.
Итак, возьмем треугольник справа от этого ребра.
3. Заносим его в список «контурных» треугольников.
4. Пока список «контурных» не пуст:
4.1. Вытаскиваем треугольник (удаляем из списка).
4.2. Сохраняем в список «финальных» треугольников.
4.3. Для каждого ребра треугольника:
4.3.1. Если ребро принадлежит любому из контуров — ничего не делаем.
4.3.2. Если ребро обычное (не контурное) — для текущего треугольника находим соседа, который разделяет текущее ребро. Ищем в списке «обычных» треугольников.
4.3.3. Если соседа нет в списке «финальных» треугольников — сохраняем в список «контурных» треугольников.

В итоге получаем красивую сетку с дырками, что и требовалось.


Зеленым — финальные треугольники.