Реферат
ВВЕДЕНИЕ 3
АНАЛИЗ СУЩЕСТВУЮЩИХ РЕШЕНИЙ 4
Компьютерная библиотека алгоритмов вычислительной геометрии CGAL 4
Visualization toolkit (VTK) 5
список ИСПОЛЬЗУЕМЫХ ТЕХНОЛОГИЙ 7
Выбор языка программирования 7
Выбор платформы 7
ФРЕЙМВОРК 8
Функциональные требования к фреймворку 9
Функциональные требования к библиотеке базовых классов 10
ТРИАНГУЛЯЦИЯ 12
Структуры для представления триангуляции 13
ПРОВЕРКА УСЛОВИЯ ДЕЛОНЕ 15
АЛГОРИТМЫ ПОСТРОЕНИЯ ТРИАНГУЛЯЦИИ 16
АЛГОРИТМ ПОСТРОЕНИЯ ТРИАНГУЛЯЦИИ С ДИНАМИЧЕСКИМ КЕШИРОВАНИЕМ 17
4.4.1. Модификация итеративного алгоритма с динамическим кэшированием поиска ....17
БИБЛИОТЕКА 19
5.1. Basic primitives 20
Point 21
PointSet 21
Triangle 21
Vector 22
Cache 22
PointCache 23
TrianCache 23
CMath 24
Drawer 24
Region 24
Models 25
Triangulation 25
ALGORITHMS 26
DynamicCache 26
ЗАКЛЮЧЕНИЕ 27
СПИСОК ЛИТЕРАТУРЫ 28
ПРИЛОЖЕНИЕ А 29
ПРИЛОЖЕНИЕ В 34
Задачи вычислительной геометрии на сегодняшний день решаются во многих отраслях науки и промышленности, например, в машинной графике, геоинформационных системах, при моделировании поверхностей или решении пространственных задач.
Существует множество алгоритмов для решения всевозможных задач в данной области, однако, все эти алгоритмы объединяет необходимость создания некоторой базовой структуры, необходимой для их последующей реализации.
С этой целью на базе отделения компьютерных наук института прикладной математики и компьютерных наук томского государственного университета ведется разработка фреймворка для решения задач вычислительной геометрии на базе триангуляционной модели. Данный фреймворк позволяет избавить пользователя от необходимости написания базовой структуры для реализации алгоритмов и интерактивно отобразить результаты работы алгоритма в формате отладки.
Целью данной работы является разработка библиотеки базовых классов для данного фреймворка, которая будет предоставлять пользователю и разработчику базовую структуру, необходимую для реализации алгоритмов решения задач вычислительной геометрии на основе триангуляции, а также встроенных алгоритмов построения триангуляции для наиболее быстрого и простого получения пользователем наглядных результатов.
Разработана библиотека базовых классов для фреймворка алгоритмов
вычислительной геометрии. Данная библиотека включена в фреймворк. Разработанная
библиотека может быть использована для разработки алгоритмов не только на основе
триангуляционной модели
