Модели и алгоритмы построения криволинейных скелетов пространственных форм

• Автор: Хромов, Денис Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 133 с. : ил.

Содержание
Введение
Глава 1. Трёхмерные криволинейные скелеты: постановка задачи
1.1. Трехмерные формы и связанные с ними прикладные
задачи
1.2. Серединная ось
1.3. Криволинейный скелет
1.3.1. Понятие криволинейного скелета
1.3.2. Свойства криволинейных скелетов
1.3.3. Алгоритмы построения
1.4. Основные выводы
Глава 2. Математическая модель криволинейных скелетов
2.1. Жирные кривые
2.2. Пространственные циркуляры и криволинейные скелеты
2.3. Мера близости между формой и аппроксимирующим
пространственным циркуляром
2.4. Аппроксимация плоской многоугольной фигуры
2.5. Основные выводы
Глава 3. Алгоритмы построения скелетов
3.1. Общая схема алгоритма
3.2. Построение первого приближения при помощи графов
Риба
3.2.1. Графы Риба
3.2.2. Порождающая функция
3.2.3. Вложение графа Риба
3.3. Построение первого приближения при помощи плоских проекций
3.3.1. Общая идея
3.3.2. Построение трёхмерного криволинейного скелета по плоской проекции
3.3.3. Выбор оптимальной плоской проекции
3.4. Численная оптимизация
3.4.1. Использование градиентного метода
3.4.2. Вычисление промежуточных значений
3.4.3. Корректность алгоритма
3.5. Анализ вычислительной сложности алгоритма
3.5.1. Построение первого приближения при помощи
графов Риба
3.5.2. Построение первого приближения при помощи
плоских проекций
3.5.3. Оптимизация методом градиентного спуска

3.6. Основные выводы

Глава 4. Вычислительный эксперимент
4.1. Практическая реализация
4.2. Экспериментальная проверка модели
4.3. Свойства алгоритма
4.4. Основные выводы
Заключение
Литература

Определение 10. Графом связности циркуляра с множеством вершин V называется граф, множество вершин которого совпадает с множеством V, а две вершины этого графа соединены ребром тогда и только тогда, когда пространственный циркуляр содержит в себе жирную кривую с парой концевых вершин гц,.
Для графа связности циркуляра естественным образом определяется укладка вК"в виде объединения осей жирных кривых, составляющих циркуляр. Такое вложение будем называть осями циркуляра. При этом, как и в случае с отдельной жирной кривой, оси циркуляра соответствуют интуитивному представлению о криволинейном скелете циркуляра.
Пространственный циркуляр представляет собой фигуру, составленную из набора примитивов (жирных линий). Пусть задана некоторая мера близости между фигурами в Мп (например, метрика Хау-сдорфа; подробнее вопрос о выборе меры близости будет рассмотрен ниже), тогда можно поставить задачу об аппроксимации произвольной фигуры П циркуляром с заданной погрешностью. Если для фигуры П построен аппроксимирующий её циркуляр С, то естественно определить скелет 61 как множество осей циркуляра.
Определение 11. Пусть 61 — ограниченная область в К", С — аппроксимирующий её циркуляр. Тогда оси циркуляра С называются криволинейным скелетом фигуры П.