Я пытаюсь триангулировать многоугольник для использования в 3D-модели. Когда я пытаюсь использовать метод уха на многоугольнике с точками, пунктирными ниже, я получаю треугольники на месте красных линий. Поскольку внутри этих треугольников нет других точек, это, вероятно, правильно. Но я хочу, чтобы он триангулировал область только внутри черных линий. Кто-нибудь знает какие-либо алгоритмы, которые это сделают?
Существует множество алгоритмов триангуляции многоугольника, которые не требуют предварительного разбиения на монотонные многоугольники. Один из них описан в моем учебнике Computational Geometry in C, в котором есть код связанный с ним, который можно бесплатно загрузить по этой ссылке (на C или на Java). Сначала вы должны расположить точки в порядке, соответствующем обходу границы. Мой код предполагает движение против часовой стрелки, но, конечно, это легко изменить. См. Также статью в Википедии. Возможно, в этом ваша проблема, что у вас нет упорядоченной организации пограничных точек?
Обычный подход состоит в том, чтобы разделить ваш простой многоугольник на монотонный многоугольник с использованием трапециевидной декомпозиции, а затем триангулировать монотонные многоугольники. Первая часть может быть достигнута с помощью алгоритма развертки линии. И ускорение возможно с помощью правильной структуры данных (например, двусвязного списка ребер). Лучшее описание этого, насколько мне известно, можно найти в Вычислительная геометрия. Это и это тоже кажется полезным.
Википедия предлагает разбить многоугольник на монотонные многоугольники. Вы проверяете, не является ли многоугольник вогнутым, просто проверяя, что все углы меньше 180 градусов - любые углы, которые имеют угол более 180, являются вогнутыми, и вам нужно сломать его в этом углу.
Вам нужно использовать алгоритм EarClipping, а не алгоритм Делоне. См. Следующий технический документ: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
