Триангуляция многоугольника

Question

Я пытаюсь триангулировать многоугольник для использования в 3d-модели. Когда я пытаюсь использовать метод уха на многоугольнике с точками, как показано ниже, я получаю треугольники, где красные линии. Поскольку внутри этих треугольников нет других точек, это, вероятно, правильно. Но я хочу, чтобы он триангулировал область только внутри черных линий. Кто-нибудь знает какие-либо алгоритмы, которые будут делать это?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

Вам нужно использовать алгоритм EarClipping, а не Делоне.См. Следующий технический документ: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf