Триангуляции вентилятора простой способ триангуляции многоугольника , выбирая вершину и рисования диагоналей для всех остальных вершин многоугольника. Не каждый многоугольник можно триангулировать таким образом, поэтому этот метод обычно используется только для выпуклых многоугольников . [1]
Характеристики
Помимо свойств всех триангуляций, веерные триангуляции обладают следующими свойствами:
- Все выпуклые многоугольники, но не все многоугольники, могут быть подвергнуты веерной триангуляции.
- Многоугольники только с одной вогнутой вершиной всегда можно разбить на веерную триангуляцию, если диагонали оттянуты от вогнутой вершины.
- Чтобы определить, есть ли хотя бы одна вершина, видимая из каждой точки многоугольника, можно узнать, можно ли провести веерную триангуляцию многоугольника, решив задачу художественной галереи .
- Триангуляция многоугольника с вершины использует диагонали, и порождает треугольники. [2]
- Создание списка треугольников тривиально, если доступен упорядоченный список вершин, и его можно вычислить за линейное время. Таким образом, нет необходимости явно хранить список треугольников, и поэтому многие графические библиотеки реализуют примитивы для представления многоугольников на основе этой триангуляции. [3]
- Хотя эта триангуляция подходит для решения определенных задач, таких как растеризация или обнаружение столкновений , она может не подходить для других задач, поскольку исходная вершина накапливает большое количество соседей, а внутренние углы триангуляции распределены неравномерно.
Смотрите также
Рекомендации
- ^ Лоэра, Иисус; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции: структуры для алгоритмов и приложений . Springer Science & Business Media. С. 103 . ISBN 9783642129711.
- ^ О'Рурк, Джозеф (1998). Вычислительная геометрия на C (2-е изд.). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 9780521649766. OCLC 38542796 .
- ^ Сегал, Марк (24 октября 2016 г.). «Графическая система OpenGL: спецификация» (PDF) . Проверено 2 марта 2017 года .