Взвешенные скелеты для простых многоугольников Дипломная работа студента 544 группы Игнатьевского Сергея Васильевича Научный руководитель: К.В. Вяткина.

Презентация:



Advertisements
Похожие презентации
Проверка эквивалентности срединной и линейной осей многоугольника Дипломная работа студента 545 группы Подколзина Максима Валериевича Санкт-Петербургский.
Advertisements

Построение мотоциклетного графа Студент 445 группы Титов Артём Научный руководитель: Вяткина К.В.
Эффективное сопоставление полигональных объектов Дипломная работа Белоног О.С. Научный руководитель: к.ф.-м.н., доц. Вяткина К.В. Рецензент: Васильева.
Система моделирования муравьиных алгоритмов в грид: задача поиска последовательности мутаций между геномами Дырдина Анна Викторовна, 544 гр. Научный руководитель:
Сопоставление полигональных объектов на основе независимой фрагментации контуров Выполнил: Ю. М. Плотников Научный руководитель: канд. ф.-м. наук К. В.
Декомпозиция сложных дискретных систем, формализованных в виде вероятностных МП-автоматов. квалификационная работа Выполнил: Шляпенко Д.А., гр. ИУ7-83.
Выполнила : Микутина Анжелика. Многогранник. Понятие многогранник. Многогранник или полиэдр поверхность, составленная из многоугольников, которые ограничивают.
К созданию архитектуры поисковой системы в наборах документов. Горелов С.С. МГУ им. М.В. Ломоносова механико-математический факультет.
Параллельные алгоритмы для симплициального подразделения области с итерационным измельчением вблизи границы Кафедра параллельных алгоритмов Математико-Механический.
Реализация модели многочастичного газа FHP-MP на графическом ускорителе Подстригайло Алена, гр Научный руководитель: к.ф.-м.н. Калгин К.В.
Методы интерактивной визуализации динамики жидких и газообразных сред Костикова Елена Юрьевна, 521 гр. Научный руководитель: Игнатенко Алексей Викторович.
Правильная Пирамида Хоанг Хай Ли. Правильная пирамида Пирамида называется правильной, если основанием ее является правильный многоугольник, а вершина.
Сравнение и подгонка поверхностей при решении прикладных задач анализа 3d портретов человеческих лиц Дышкант Наталья Федоровна
Объём многогранника. Многогранник Многогранник – это такое тело, поверхность которого состоит из конечного числа плоских многоугольников.
Поиск путей в сложных полигонах для динамических систем реального времени. Работа Порошина И.А., 544 гр. Научный руководитель Уфнаровский В.В. Рецензент,
Мелкозернистая параллельная реализация алгоритма Монтгомери Руководитель: доктор физико- математических наук, профессор Соболевский П.И.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Методы комбинаторной оптимизации в задачах расположения сервисов в дата-центрах Дипломная работа студента 545 группы Шалупова Л.Б. Научный руководитель:
Разработка системы развертывания веб- сервисов на базе Р2Р сети Дипломная работа Скворцова Н.С. Научный руководитель: Плискин М.М. Рецензент: Глиненко.
«Знание – столь драгоценная вещь, что её не зазорно добывать из любого источника.» Фома Аквинский.
Транксрипт:

Взвешенные скелеты для простых многоугольников Дипломная работа студента 544 группы Игнатьевского Сергея Васильевича Научный руководитель: К.В. Вяткина Рецензент: Н.С. Васильева Санкт-Петербург 2008

Введение Ранние исследования: Прямолинейный скелет (straight skeleton) (Aichholzer et al., 1995). Крыша. Взвешенный скелет (weighted skeleton) (Aurenhammer, 2007). Исследовался подробно только для выпуклых многоугольников. Не было аналога крыши для многоугольника с весами

Цели Определение и исследование свойств взвешенного скелета для простых многоугольников. Введение понятия взвешенной крыши, исследование ее свойств и способов построения. Исследование возможности адаптации известных алгоритмов вычисления прямолинейного скелета для случая взвешенного скелета. Реализация одного из алгоритмов вычисления взвешенного скелета. Рассмотрение возможности применения взвешенного скелета на практике.

Взвешенный скелет и взвешенная крыша Взвешенный скелет – граф, дуги которого вычерчиваются вершинами линейного фронта в процессе его распространения, при котором ребра многоугольника движутся с разными скоростями (в зависимости от веса). Процесс распространения линейного фронта: ребра многоугольника движутся внутрь, оставаясь параллельными самим себе Скелет простого многоугольника с n вершинами – дерево, имеющее n-2 внутренних узла и 2n-3 дуги, он разбивает многоугольник на n регионов. Взвешенная крыша – результат поднятия скелета в 3D пространство, в соответствии с взвешенным расстоянием от узлов скелета до границы многоугольника Не имеет локальных минимумов (свойство waterfall); определяется однозначно.

Алгоритмы построения Адаптированный алгоритм Фелкеля и Обдржалека. Адаптация возможна, с коррекцией шагов алгоритма. Реализован на платформе.Net (С#, VS 2005). Время:, где n – число вершин многоугольника, среди которых m невыпуклых. Первый алгоритм Эппштейна и Эриксона. Адаптация возможна. Время:, - неотрицательно. Второй алгоритм Эппштейна и Эриксона. Показана невозможность адаптации. Вероятностный алгоритм Ченга и Виньерона. Показана невозможность адаптации.

Реализация модифицированного алгоритма Фелкеля и Обдржалека В рамках работы создано приложение реализующее адаптированный алгоритм Фелкеля и Обдржалека. Технологическая основа: платформа.NET 2.0, Windows Forms, библиотека Microsoft DirectX. Функциональность программы : Рисование простого многоугольника на плоскости. Назначение весов ребрам многоугольника. Загрузка и сохранение многоугольника в файл. Построение и отображение взвешенного скелета для созданного многоугольника. Построение и отображение взвешенной крыши многоугольника в трехмерном пространстве (с использованием классов из библиотек Microsoft.DirectX и Microsoft.DirectX.Direct3D).

Моделирование городов и взвешенный скелет Полуавтоматические системы моделирования городов. Моделирование городов по данным аэросъемки сводится к восстановлению зданий по их контурам. Применение взвешенных скелетов для построения крыши здания. Сравнение со старыми методами (использующими прямолинейный скелет). Применение в виртуальной архитектуре: конструирование городов в 3D играх и симуляторах.

Заключение Рассмотрены понятия, свойства и алгоритмы построения взвешенного скелета и крыши для простого многоугольника. Рассмотрена одна из возможностей применения взвешенного скелета на практике. Реализован модифицированный алгоритм Фелкеля и Обдржалека для вычисления взвешенного скелета. Дальнейшие исследования: Расширение понятия взвешенного скелета на случай многоугольников с дырками и плоских прямолинейных графов. Разработка более эффективных алгоритмов вычисления взвешенного скелета. Исследование других областей применения взвешенных скелетов и крыш, например, для построения прямолинейного скелета многогранников в трехмерном пространстве.