Аннотация:
В работе рассматриваются многие известные алгоритмы построения триангуляции
Делоне и предлагается их классификация. Для всех алгоритмов приводится оценка
их трудоемкости в среднем и худшем случаях. Обсуждаются особенности
реализации. Рассматриваются четыре структуры данных для представления
триангуляции. Приводятся процедуры проверки условия Делоне и описываются
процедуры слияния триангуляций.
Ключевые слова:триангуляция; вычислительная геометрия; машинная графика; построение сеток; структуры данных.
Полный текст:
PDF файл (584 kB)