Триангуляция вееров - Fan triangulation

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

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

А веерная триангуляция это простой способ триангулировать многоугольник выбрав вершину и проведя диагонали ко всем остальным вершинам многоугольника. Не каждый многоугольник можно триангулировать таким образом, поэтому этот метод обычно используется только для выпуклые многоугольники.^[1]

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

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

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

Смотрите также

• Веер треугольник

Рекомендации