У меня есть набор координат 2D-точек, которые образуют замкнутый многоугольник. Мне нужно сгенерировать набор 2D-треугольников, полностью распределяющих многоугольник.
Ограничений как таковых нет, за исключением того, что треугольники должны полностью заполнять площадь полигона. Было бы еще полезнее, если бы это был стандартный алгоритм, который я мог бы реализовать.
Как было сказано выше, триангуляция Делоне — достаточно сложный алгоритм для этой задачи. Если вы принимаете время работы O (n ^ 2), вы можете попробовать алгоритм Ear Clipping, который намного проще для понимания и кодирования. Основная идея заключается в следующем. Каждый многоугольник с >= 4 вершинами и без отверстий (т. е. его граница представляет собой одну полилинию без самопересечений и самокасаний) имеет по крайней мере одно «ухо». Ухо — это три последовательные вершины такие, что построенный на них треугольник лежит внутри многоугольника и не содержит внутри других точек многоугольника. Если вы «отрежете ухо» (добавите к ответу треугольник и замените, уберете среднюю точку из этих трех точек), вы сведете задачу к многоугольнику с меньшим количеством вершин и так далее. Уши могут быть тривиально (по определению) найдены за O (n ^ 2), что приводит к алгоритму триангуляции O (n ^ 3). Существует O(n) алгоритм нахождения ушей, и он хоть и не очень сложный, но достаточно длинный, чтобы его можно было описать в паре фраз.
Кроме того, если вам нужны более быстрые алгоритмы, вы должны посмотреть что-нибудь о триангуляции монотонных полигонов и разбиении полигона на монотонные. Существует даже алгоритм триангуляции с линейным временем, но он такой же сложный, как и триангуляция Делоне.
Вы можете рассмотреть статью Википедии и увидеть там небольшой обзор существующих методов.
Лучший способ триангуляции общих многоугольников — это вычисление ограниченной триангуляции Делоне – это стандартная триангуляция Делоне. вершин многоугольника с дополнительными ограничениями, чтобы гарантировать, что края многоугольника появляются в триангуляции явно. Этот тип подхода может обрабатывать любой тип многоугольника - выпуклый, вогнутый, многоугольники с отверстиями и т. д.
Триангуляции Делоне — это те, которые максимизируют минимальный угол в сетке, а это означает, что такая триангуляция является оптимальной с точки зрения качества формы элемента.
Кодирование алгоритма триангуляции Делоне с ограничениями — сложная задача, но существует ряд хороших библиотек, в частности CGAL и Треугольник. Обе эти библиотеки реализуют (оптимально) эффективный алгоритм O(n*log(n)).
Если вам не требуется, чтобы вершины треугольников были вершинами многоугольника, попробуйте триангуляцию на основе трапецеидального разложения, как в Быстрая триангуляция полигонов на основе алгоритма Зейделя.
