Простая 2d полигональная триангуляция

Question

Пытаясь триангулировать набор простых 2-мерных полигонов , я придумал этот алгоритм:

• 1) Для каждой вершины многоугольника вычислить угол между двумя связанными ребрами
• 2) Сортировка вершин по уменьшению угла относительно внутренней части многоугольника
• 3) Если в наборе меньше 3 вершин, все готово
• 4) Возьмите последнюю вершину в наборе и выведите треугольник, образованный ею и двумя ее соседями
• 5) Удалить вершину из множества
• 6) Обновление угла двух соседей
• 7) Перейти к 2

Я протестировал его и обнаружил, что он работает даже на очень больших и сложных простых 2-мерных полигонах (он не работает для полигонов с дырками или самопересекающихся полигонов).

Есть ли угловые случаи, которые дадут вырожденный результат?

Является ли этот алгоритм известным?

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

Большое спасибо.

Answer 1

Вы используете вариант подхода триангуляции «обрезание ушей», см .: http://en.wikipedia.org/wiki/Polygon_triangulation

Ваш алгоритм потерпит неудачу, если другая вершина многоугольника (скажем, с другой стороны многоугольника) окажется внутри треугольника «ухо», которое вы формируете. Рассмотрим этот пример:

Ваш алгоритм сначала выберет A и создаст треугольник с двумя смежными ребрами (соединенными пунктирной линией). Но этот треугольник включает в себя другую вершину (B) и явно неверен.

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

Answer 2

Простые выпуклые полигоны: O (n)

Это когда вы хотите работать с простыми полигонами, такими как прямоугольники, пятиугольники, шестиугольники и так далее.Здесь вы просто берете отправную точку и соединяете ее со всеми остальными вершинами.Этот алгоритм тривиален, и что я действительно хотел, так это более общее решение, которое могло бы обрабатывать вогнутые и многоугольники с отверстиями.

Для того, чтобы иметь дело с более сложными полигонами, такими как предоставленный Пэйном ...

Произвольный многоугольник в треугольник в O (n log n)

Хотя существуют алгоритмы, которые работают быстрее, более быстрые алгоритмы становятся очень сложными. Киркпатрик и соавт.нашел алгоритм для запуска в O (n log log n) и Chazelle сделал это в O (n).Однако проще всего реализовать, вероятно, алгоритм Зейделя , который работает в O (n log n).

Алгоритм представляет собой трехэтапный процесс

1. Разложить многоугольник на трапеции
2. Разложить трапеции на монотонных многоугольников
3. Разложить монотонные многоугольники на треугольники

C источник

Если вас интересует источник C, его можно получить в Университете Северной Каролины в Чапел-Хилле .В целом качество кода хорошее, он обрабатывает дыры, но, вероятно, его нужно будет массировать в соответствии с вашими потребностями.

Answer 3

Если я вас правильно понимаю, вы отсекаете треугольники, начиная с наименьшего внутреннего угла.Это может потерпеть неудачу, если многоугольник не выпуклый.Рассмотрим многоугольник с вершинами (по порядку) в точке: (0,0) (10,9) (9,9) (9,10).Наименьший угол равен исходному, но вы не можете безопасно отрезать этот треугольник.

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

Answer 4

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

Алгоритм обрезания ушей из libgdx является хорошимначинать с него, поскольку он очень надежный - с использованием FIST (Быстрая промышленная триангуляция прочности полигонов) .

Я использовал это как основу для тесселяции полигонов, затем добавил пространственную оптимизацию длятесты точка-треугольник, (O(n log n) вместо O(n^2)).

См .:

• код C , тесты .
• Код ржавчины , тесты
• Оригинальный код из libgdx .

---

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

Answer 5

Раньше мне приходилось решать аналогичную проблему, и полученный код может быть полезен вам или кому-то еще, кто смотрит на это:

Демо: http://cecchi.me/portfolio/triangulation
Источник: http://cecchi.me/js/point-picking.js.src

Источник немного грязный, чтобы облегчить анимацию, но вы должны увидеть, как я решил проблему, указанную Пейном с помощью выпуклых многоугольников (соответствующий код начинается в строке 200). Обратите внимание, что мое решение по-прежнему не учитывает сложные полигоны.