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

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

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

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

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

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

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

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

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