Веерная триангуляция

Веерная триангуляция выпуклого многоугольника

Веерная триангуляция вогнутого многоугольника с уникальной вогнутой вершиной.

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

Характеристики

Помимо свойств всех триангуляций, веерные триангуляции обладают следующими свойствами:

• Все выпуклые многоугольники, но не все многоугольники, можно триангулировать веером.
• Многоугольники только с одной вогнутой вершиной всегда можно триангулировать веером, если диагонали проводятся из вогнутой вершины.
• Можно узнать, можно ли выполнить веерную триангуляцию многоугольника, решив задачу «Художественная галерея» , чтобы определить, есть ли хотя бы одна вершина, видимая из каждой точки многоугольника.
• Триангуляция многоугольника с $n$ использование вершин $n-3$ диагонали и порождает $n-2$ треугольники.
• Создание списка треугольников тривиально, если доступен упорядоченный список вершин, и его можно вычислить за линейное время. Таким образом, нет необходимости явно хранить список треугольников, и поэтому многие графические библиотеки реализуют примитивы для представления многоугольников на основе этой триангуляции.
• Хотя эта триангуляция подходит для решения определенных задач, таких как растеризация или обнаружение столкновений , она может быть непригодна для других задач, поскольку исходная вершина накапливает большое количество соседей, а внутренние углы триангуляции распределены неравномерно.

См. также

• Треугольный вентилятор