Комплексное исследование и разработка эффективных алгоритмов триангуляции простого многоугольника

• Автор: Дворцов, Владислав Игоревич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Санкт-Петербург
• Количество страниц: 140 с. : ил.

ОГЛАВЛЕНИЕ
Введение

1 Триангуляция простого многоугольника аналитический обзор

1.1 Триангуляция простого многоугольника.

1.2 Известные алгоритмы триангуляции простого многоугольника

1.2.1 Алгоритм декомпозиции на монотонные многоугольники

1.2.2 Алгоритм триангуляции простого многоугольника методом расщепления вдоль хорды

1.2.3 Алгоритм триангуляции простого многоугольника методом сканирования Грэхема.

1.2.4 Алгоритм трапецеидальной декомпозиции Тарьяна

1.2.5 Алгоритм трапецеидальной декомпозиции Киркпатрика

1.2.6 Алгоритм трапецеидальной декомпозиции Сайдсля

1.2.7 Алгоритм трапецеидальной декомпозиции Чазелли
1.2.8 Алгоритм трапецеидальной декомпозиции АГР
1.2.9 Двойственность задач триангуляции простого многоугольника и построения трапецеидальной декомпозиции
1.2. Выводы.
2 Предложенные алгоритмы триангуляции простого многоугольника
2.1 Классификация алгоритмов триангуляции простого многоугольника.
2.2 Индексирование и кэширование
2.2.1 Модификация алгоритма Грэхема с использованием индексирования.
2.2.2 Рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования
2.2.3 Последовательный рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования и динамической коррекции.
2.2.4 Алгоритм трапецеидальной декомпозиции Сайделя с
использованием кэширования.
2.2.5 Алгоритм триангуляции простого многоугольника с предобработкой.
2.2.6 Параллельный алгоритм псевдотриангуляции простого многоугольника.
2.3 Выводы.
3 Генерация простых многоугольников.
3.1 Задача построения простого многоугольника.
3.2 Алгоритмы генерации простого многоугольника
3.2.1 Алгоритм построения монотонных и немонотонных простых многоугольников методом сортировки.
3.2.2 Алгоритм построения простых многоугольников методом полярной сортировки
3.2.3 Алгоритм построения простого многоугольника методом разделения пространства
3.2.4 Алгоритм построения простого многоугольника методом последовательной вставки.
3.2.5 Алгоритм построения простого многоугольника методом триангуляции Делоне
3.3 Примеры построенных простых многоугольников
3.4.Выводы
4 Вычислительная устойчивость алгоритмов триангуляции и генерации простого многоугольника
4.1 Причины возникновения ошибок при вычислениях
4.2 Применение целочисленной арифметики
4.3 Применение адаптивных операций вычисления.
4.4 Поведение алгоритмов при применении вычислительно устойчивых схем.
4.5.Выводы.
5 Реализация и экспериментальное исследование алгоритмов
5.1 Проверка правильности построенных результатов
5.2 Основа экспериментального исследования.
6 Сравнительный анализ алгоритмов триангуляции и генерации простого многоугольника
6.1 Сравнительный анализ алгоритмов генерации простого многоугольника.
6.2 Сравнительный анализ алгоритмов триангуляции простых многоугольников
6.3 Выводы и рекомендации
7 Заключение.
Список литературы


В первой главе формулируется задача триангуляции, проводится аналитический обзор алгоритмов и методов решения задачи. Во второй главе приводится классификация алгоритмов триангуляции простого многоугольника, описываются предложенные алгоритмы для триангуляции. Вводятся предложенные автором алгоритмы триангуляции простого многоугольника с асимптотическими оценками в среднем и худшем случае, с использованием кэширования, индексирования, динамической коррекции, параллельной обработки и предобработки. В третьей главе приводится классификация и ставится задача построения простого многоугольника, описываются известные алгоритмы и вводятся предложенные автором алгоритмы для генерации простого многоугольника. Объясняется необходимость решения и сложность этой задачи. Даются примеры сгенерированных многоугольников. В четвертой главе, обсуждается задача вычислительной устойчивости алгоритмов генерации и триангуляции простого многоугольника, причины возникновения ошибок при внутренних вычислениях, а также различные методы решения проблем, такие как целочисленная арифметика и применение адаптивных алгоритмов точной арифметики. Рассматривается поведение алгоритмов до, и после использования точной арифметики. В пятой главе описываются особенности реализации и постановки экспериментального исследования. В шестой главе проводится сравнительный анализ всех реализованных алгоритмов, выявляются особенности поведения алгоритмов, предлагаются рекомендации по использованию. ТРИАНГУЛЯЦИЯ ПРОСТОГО МНОГОУГОЛЬНИКА Триангуляция многоугольника это классическая проблема вычислительной геометрии. Существует целый ряд задач в вычислительной геометрии, эффективное решение которых, требует вычисление триангуляции многоугольника как шаг предобработки. Триангуляция многоугольника необходима как базовый блок для множества графических приложений, например, таких как геометрическая декомпозиция, задача видимости. С помощью нее легко решаются такие задачи, как вычисление внутреннего расстояния между двумя точками многоугольника, определение видимости многоугольника из точки, находящейся внутри многоугольника, решение задачи о кратчайшем пути внутри многоугольника, проверка многоугольников на пересечение . Задача ТПМ формулируется следующим образом даны координаты п вершин простого многоугольника Р в порядке его обхода, необходимо найти л3 не пересекающихся диагоналей, которые делят Р на п2 треугольника. Результат триангуляции вершинного многоугольника представлен на рисунке 1. Рис 1. Триангуляция простого многоугольника Многоугольник называется простым, если набор отрезков, из которых он состоит, не имеет самопересечений. Один из первых эффективных алгоритмов, предложенный Гэри и др. СЛОЖНОСТЬ 0. Этот алгоритм вычисляет триангуляцию многоугольника напрямую, не решая двойственных задач и довольно прост в реализации, поэтому на протяжении многих лет его приводят в учебниках по вычислительной геометрии как один из основных способов решения задачи. Долгое время было не ясно является ли оценка 0п п точной нижней границей для задачи триангуляции простого многоугольника или все таки задача триангуляции простого многоугольника проще задачи триангуляции Делоне для которой эта оценка установлена как нижняя граница. В году Чазелли и Инчерпи , а также Фурнье и Монтуно показали , что для решения задачи триангуляции простого многоугольника достаточно получить трапецеидальную декомпозицию простого многоугольника, а собственно триангуляция выполняется после этого за линейное время из декомпозиции. И этот факт дал серьезный толчок для новых алгоритмов решения задачи триангуляции простого многоугольника. Тарьян и Ван Вик в предложили алгоритм построения трапецеидальной декомпозиции простого многоугольника , имеющий вычислительную сложность 0 и, и тем самым показали, что задача триангуляции простого многоугольника проще, чем задача сортировки. К сожалению их алгоритм является довольно сложным для реализации, так как использует сложные структуры данных неоднородные и однородные красночерные деревья с указателями и малодокументированные шаги Жорданова сортировка за линейное время. Сайделя.