Триангуляция. EarClip, жадная, Делоне. Код.
Продолжаем тему триангуляции.
Описываю еще 2 алгоритма и выкладываю код для всех трех.
Хотел подробно расписать код, все функции, теорию и т.д., но слишком много текста получается.
Поэтому только алгоритмы.
По коду и остальное спрашивайте в комментах.
Отмазки
Код может глючить и все такое. Я не виноват, разбирайтесь сами :)
Описание алгоритмов
Общие замечания:
— на вход подается один или несколько списков точек (контуры)
— первый контур считается внешним и всегда ориентирован по часовой стрелке
— контуры не могут пересекаться, не могут иметь общих точек
— на выходе список треугольников
Все функции — статические.
В каждом модуле 2 функции: triangulate() и test().
Режем уши
ryz.triangulation.ears.TEarClipTriangulation
Только один контур, без дырок, делает плохие треугольники. Зато быстрый и простой.
+ Пока в контуре больше 3 точек:
++ Последовательно берем 3 точки (с перехлестом через начало списка)
++ Если треугольник ориентирован по часовой стрелке:
+++ Если треугольник «пустой» (не содержит точек внутри)
++++ Сохраняем треугольник
++++ Выбрасываем среднюю точку из контура
Жадная триангуляция
ryz.triangulation.greed.TGreedTriangulation
Поддерживает дырки. Медленный.
+ Генерируем все возможные ребра
+ Сортируем по длине по возрастанию
+ Создаем список «финальных» ребер и добавляем в него контурные ребра
+ Пока список «возможных» не пуст:
++ Вытаскиваем первое ребро (самое короткое)
++ Если нет пересечения с «финальными» ребрами:
+++ Добавляем в список «финальных»
+ Сейчас надо генерировать все треугольники из ребер
+ Пока список «финальных» ребер не пуст:
++ Вытаскиваем ребро
++ Для каждого ребра в списке «финальных», которое имеет с текущим общую точку:
+++ Для каждого ребра в списке «финальных», которое соединяет два предыдущих ребра:
++++ Создаем треугольник, ориентированный по часовой стрелке
++++ Если треугольник «пустой» (не содержит точек внутри)
+++++ Сохраняем в список «промежуточных» треугольников
+ Сейчас надо выбрать только нужные треугольники (см. предыдущую статью)
Делоне
ryz.triangulation.delaunay.TDelaunayTriangulation
Поддерживает дырки. Нормальная скорость.
См. предыдущую статью.
Архив с проектом.
docs.google.com/leaf?id=0B-KnhhmWX_leMGFkYjEzOWMtZGZmZS00MzllLWE3M2QtYjY0YWMzYjJmNjQ5&sort=name&layout=list#=50
Описываю еще 2 алгоритма и выкладываю код для всех трех.
Хотел подробно расписать код, все функции, теорию и т.д., но слишком много текста получается.
Поэтому только алгоритмы.
По коду и остальное спрашивайте в комментах.
Отмазки
Код может глючить и все такое. Я не виноват, разбирайтесь сами :)
Описание алгоритмов
Общие замечания:
— на вход подается один или несколько списков точек (контуры)
— первый контур считается внешним и всегда ориентирован по часовой стрелке
— контуры не могут пересекаться, не могут иметь общих точек
— на выходе список треугольников
Все функции — статические.
В каждом модуле 2 функции: triangulate() и test().
Режем уши
ryz.triangulation.ears.TEarClipTriangulation
Только один контур, без дырок, делает плохие треугольники. Зато быстрый и простой.
+ Пока в контуре больше 3 точек:
++ Последовательно берем 3 точки (с перехлестом через начало списка)
++ Если треугольник ориентирован по часовой стрелке:
+++ Если треугольник «пустой» (не содержит точек внутри)
++++ Сохраняем треугольник
++++ Выбрасываем среднюю точку из контура
Жадная триангуляция
ryz.triangulation.greed.TGreedTriangulation
Поддерживает дырки. Медленный.
+ Генерируем все возможные ребра
+ Сортируем по длине по возрастанию
+ Создаем список «финальных» ребер и добавляем в него контурные ребра
+ Пока список «возможных» не пуст:
++ Вытаскиваем первое ребро (самое короткое)
++ Если нет пересечения с «финальными» ребрами:
+++ Добавляем в список «финальных»
+ Сейчас надо генерировать все треугольники из ребер
+ Пока список «финальных» ребер не пуст:
++ Вытаскиваем ребро
++ Для каждого ребра в списке «финальных», которое имеет с текущим общую точку:
+++ Для каждого ребра в списке «финальных», которое соединяет два предыдущих ребра:
++++ Создаем треугольник, ориентированный по часовой стрелке
++++ Если треугольник «пустой» (не содержит точек внутри)
+++++ Сохраняем в список «промежуточных» треугольников
+ Сейчас надо выбрать только нужные треугольники (см. предыдущую статью)
Делоне
ryz.triangulation.delaunay.TDelaunayTriangulation
Поддерживает дырки. Нормальная скорость.
См. предыдущую статью.
Архив с проектом.
docs.google.com/leaf?id=0B-KnhhmWX_leMGFkYjEzOWMtZGZmZS00MzllLWE3M2QtYjY0YWMzYjJmNjQ5&sort=name&layout=list#=50
- +6
- ryzed
Комментарии (9)
Не хватает информации, где вогнутость, где просто внутренняя точка.
Представь себе три точки, образующие треугольник и четвертую точку в центре. Это треугольник с точкой в центре или «коза»?
Когда сможешь ответить — тогда и сможешь триангулировать.
Вот тогда такой алгоритм можно будет использовать. А когда для использования алгоритма нужны ещё стопицот тыщь условий — это тоже круто, но область применения сильно сокращается. ):
На картинке 4 из множества возможных контуров.
Какой использовать?
Если мы же контур задан с учетом последовательности и проблема только в ориентации, тогда не вижу препятствий.
Определил ориентацию, провернул, если надо, и задача сводится к предыдущей.