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

1 Проверка эквивалентности срединной и линейной осей многоугольника Дипломная работа студента 545 группы Подколзина Максима Валериевича Санкт-Петербургский Государственный университет Математико-механический факультет Кафедра системного программирования Научный руководитель: к.ф.м.н., доцент К.В. Вяткина Рецензент: д.ф.м.н., профессор О.Н. Граничин

2 Постановка задачи (1) Срединная ось (1967) преимущества: отражает свойства исходной фигуры недостаток: содержит параболические дуги

3 Постановка задачи (2) Линейная ось (2004) состоит только из прямолинейных отрезков определяется числом скрытых ребер Понятие ε-эквивалентности срединная осьлинейная ось

4 Постановка задачи (3) Цели данной работы исследование подходов для оценки сходства осей эффективный алгоритм проверки эквивалентности для данных срединной и линейной осей

5 Исследование различных типов эквивалентности понятие сильной эквивалентности справедливы уже доказанные теоремы и алгоритмы понятие геометрической эквивалентности иерархия типов эквивалентности

6 Алгоритм проверки сильной эквивалентности Идея алгоритма – обход в ширину графа срединной оси и одновременно графа линейной оси Основная трудность – обработка близких вершин без перебора Применим ко всем простым многоугольникам Работает за линейное время с использованием линейной памяти

7 Демонстрация

8

9

10

11

12

13

14 Результаты работы Иерархия типов эквивалентности Алгоритм проверки сильной эквивалентности расширение для проверки геометрической эквивалентности Реализация алгоритма и демонстрационной программы на языке Java 25 классов 2500 строк кода

15 Применение и направления для дальнейших исследований Выбор подходящего типа эквивалентности для каждой конкретной ситуации Оптимизация алгоритмов, требующих построение линейных осей для различных ε задача восстановления поверхности по набору горизонтальных срезов

16 Вопросы