Построение мотоциклетного графа Студент 445 группы Титов Артём Научный руководитель: Вяткина К.В.

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



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

Проверка эквивалентности срединной и линейной осей многоугольника Дипломная работа студента 545 группы Подколзина Максима Валериевича Санкт-Петербургский.
О применении динамически перестраиваемых диаграмм Вороного к контролю технологических правил М.В. Шеблаев, Р.В. Ерохин, А.Н. Яхонтов eASIC Corporation.
Применение методов решения задачи удовлетворения ограничениям для построения управляющих конечных автоматов по сценариям работы Владимир Ульянцев Научный.
Построение сечений многогранниковмногогранников. Практикум Геометрические понятия ПлоскостьПлоскость – грань ПрямаяПрямая – ребро ТочкаТочка – вершина.
Алгоритмы и методы поиска событий в видео потоке Вороной А.С. Научный руководитель: проф. Башков Е.А.
Распознавание двух- и трехмерных жестов ладони на основе анализа скелетного представления ее силуэта Куракин Алексей Владимирович Московский Физико-Технический.
Построение сечений параллелепипеда Автор презентации Мартусевич Т.О.
Геометрические алгоритмы синтеза элементов одежды Автор: Пантелеева С.Г. Руководитель: Карабчевский В.В. III Международная научная конференция студентов,
2 из 21 Введение в Cache-oblivious алгоритмы: –Определение Cache-oblivious алгоритмов. –Модель памяти компьютера. –Cache-oblivious модель –Примеры сache-oblivious.
СЕЧЕНИЕ Алгоритм построения. 1. Анализ геометрической формы детали.
Использование графиков функций с модулем при решении задач Исследовательская работа Автор: Никонов Николай, 11 класс Научный руководитель: Атапина Елена.
Информационно-поисковые системы. Сычев А.В. 1 Самоорганизация в сети Веб Воронежский государственный университет Факультет компьютерных наук Кафедра информационных.
Цилиндр геометрическое тело, ограниченное цилиндрической поверхностью (называемой боковой поверхностью цилиндра) и не более чем двумя поверхностями (основаниями.
Сопоставление полигональных объектов на основе независимой фрагментации контуров Выполнил: Ю. М. Плотников Научный руководитель: канд. ф.-м. наук К. В.
учебный год учебный год учебный год.
1. Это средство передачи наших представлений. 2. В ней есть объекты-числа, вектора, геометрические фигуры и их элементы. Я З Ы К.
Построение областей в R 3 для вычисления их объемов Задача 1. Построить область, ограниченную поверхностями z=0, z=y, y=x 2, y=1 а) Строим параболический.
Основы современных операционных систем Лекция 14.
Введение в эволюционную и медицинскую геномику. Часть 1: Введение в эволюционную геномику Егор Базыкин 9 октября 2007 г.
Транксрипт:

Построение мотоциклетного графа Студент 445 группы Титов Артём Научный руководитель: Вяткина К.В.

Основные понятия Мотоциклетный граф Eppstein and Erickson, 1998 Прямолинейный скелет Aichholzer et al., 1995

Цель будущая [1] Cheng and Vigneron, 2007

Цель нынешняя [2] Cheng and Vigneron, 2007

Алгоритм Разбиение и события перехода Начальные столкновения Мотоциклетный граф [2] Cheng and Vigneron, 2007

Факты Используется в наиболее эффективных методах построения прямолинейного скелета Теоритическая сложность работы алгоритма построение мотоциклетного графа O(nnlogn)

А зачем ? Для построения прямолинейного скелета !

А зачем нам прямолинейный скелет ? Построение крыши Восстановление поверхности по множеству сечений параллельными плоскостями. Оригами

Результат Программа на Java Построение мотоциклетного графа Визуализация процесса построения Набор классов для работы с геометрическими объектами

Источники 1. Wikipedia A. Aichholzer, F. Aurenhammer, D. Alberts, B. Gärthner. A novel type of skeleton for polygons. The Journal of Universal Computer Science, 1 (1995) D. Eppstein, J. Erickson. Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions. Discrete and Computational Geometry Б 22(4) (1999) S.-W. Cheng, A. Vigneron. Motorcycle Graphs and Straight Skeletons. Algorithmica, 47 (2007),