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

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

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

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

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

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

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

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

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

Вопросы