Введение
1 Триангуляция простого многоугольника: аналитический обзор 10
1.1 Триангуляция простого многоугольника 10
1.2 Известные алгоритмы триангуляции простого многоугольника 15
1.2.1 Алгоритм декомпозиции на монотонные многоугольники 15
1.2.2 Алгоритм триангуляции простого многоугольника методом расщепления вдоль хорды 18
1.2.3 Алгоритм триангуляции простого многоугольника методом сканирования Грэхема 21
1.2.4 Алгоритм трапецеидальной декомпозиции Тарьяна 23
1.2.5 Алгоритм трапецеидальной декомпозиции Киркпатрика 24
1.2.6 Алгоритм трапецеидальной декомпозиции Сайделя 25
1.2.7 Алгоритм трапецеидальной декомпозиции Чазелли 31
1.2.8 Алгоритм трапецеидальной декомпозиции АГР 32
1.2.9 Двойственность задач триангуляции простого многоугольника и построения трапецеидальной декомпозиции 39
1.2.10 Выводы 40
2 Предложенные алгоритмы триангуляции простого многоугольника .. 41
2Л Классификация алгоритмов триангуляции простого многоугольника 41
2.2 Индексирование и кэширование 43
2.2.1 Модификация алгоритма Грэхема с использованием индексирования 43
2.2.2 Рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования 46
2.2.3 Последовательный рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования и динамической коррекции 49
2.2.4 Алгоритм трапецеидальной декомпозиции Сайделя с
использованием кэширования 53
2.2.5 Алгоритм триангуляции простого многоугольника с предобработкой 55
2.2.6 Параллельный алгоритм псевдотриангуляции простого многоугольника 58
2.3 Выводы 61
3 Генерация простых многоугольников 63
3.1 Задача построения простого многоугольника 63
3.2 Алгоритмы генерации простого многоугольника 65
3.2.1 Алгоритм построения монотонных и немонотонных простых многоугольников методом сортировки 66
3.2.2 Алгоритм построения простых многоугольников методом полярной сортировки 69
3.2.3 Алгоритм построения простого многоугольника методом разделения пространства 70
3.2.4 Алгоритм построения простого многоугольника методом последовательной вставки 72
3.2.5 Алгоритм построения простого многоугольника методом триангуляции Делоне 74
3.3 Примеры построенных простых многоугольников 77
3.4 Выводы 82
4 Вычислительная устойчивость алгоритмов триангуляции и генерации простого многоугольника 84
4.1 Причины возникновения ошибок при вычислениях 86
4.2 Применение целочисленной арифметики 94
4.3 Применение адаптивных операций вычисления 97
4.4 Поведение алгоритмов при применении вычислительно устойчивых схем 101
4.5 Выводы 102
5 Реализация и экспериментальное исследование алгоритмов 103
5.1 Проверка правильности построенных результатов 103
5.2 Основа экспериментального исследования 106
6 Сравнительный анализ алгоритмов триангуляции и генерации простого многоугольника 110
6.1 Сравнительный анализ алгоритмов генерации простого многоугольника 111
6.2 Сравнительный анализ алгоритмов триангуляции простых многоугольников 115
6.3 Выводы и рекомендации 131
7 Заключение 132
Список литературы
