ВВЕДЕНИЕ 3
ГЛАВА 1 ТЕОРЕТИЧЕСКОЕ ОПИСАНИЕ АЛГОРИТМОВ 5
1.1 Задача проектирования нуля Евклидова пространства на выпуклый
многогранник 5
1.2 Метод Митчелла-Демьянова-Малоземова (МДМ-метод) 6
1.2.1 МДМ-метод 6
1.2.2 МДМ-метод практическая реализация 8
1.3 Метод Гильберта (Гильберта-Джонсона-Керти, GJK алгоритм) 9
1.3.1 Алгоритм GJK - метода 9
1.3.2 Метод Гильберта практическая реализация 11
ГЛАВА 2 ПРАКТИЧЕСКАЯ ЧАСТЬ 13
2.1 Численные эксперименты 13
2.2 Тесты программы 19
2.3 Структурное описание программы 24
ЗАКЛЮЧЕНИЕ 27
СПИСОК ЛИТЕРАТУРЫ 28
ПРИЛОЖЕНИЯ
В наше время компьютер стал неотъемлемой частью нашей жизни. Возможности, предоставляемые компьютерами, с течением времени неуклонно растут. Большой популярностью среди молодежи и взрослых пользуются фильмы, особенно фантастика со спецэффектами, а среди детей - игры. Ни одна игра и ни один фильм не обходится без компьютерной графики. При этом нужно, чтобы наблюдаемые в фильмах и компьютерных играх явления были реалистичны, поэтому актуальной темой на сегодня является реалистичное физическое моделирование.
Векторное пространство представляет немалый интерес в науке и в исследованиях. Оно носит не только теоретический характер, но и имеет реальное применение в современном мире.
В связи с появлением гаджетов на операционных мобильных системах, таких как Android, IOS, BlackBerry OS, Windows Mobile, а также других операционных систем, связь с векторным пространством резко возросла. Все действия, совершаемые над мобильным устройством: нажатия на экранные кнопки, работа с камерой и её направлением, изменение скоростей объектов и т.д., основаны на свойствах векторных пространств, n-мерных векторов и действиях над ними.
Именно поэтому, данная тема дипломной работы, актуальна на сегодняшний день.
В данной дипломной работе была спроектирована численная реализация МДМ-метода и метода Гильберта, были проведены численные эксперименты, результаты которых были сравнены и проанализированы.
Проект должен быть разработан в интерактивной среде программирования Matlab R2013b. Разработанное приложение должно быть нетребовательно к ресурсам системы, просто в установке и настройке и удобно в эксплуатации.
Целью данной работы является: реализация решения задачи
проектирования нуля Евклидова пространства на выпуклый многогранник двумя методами (методом Гильберта и МДМ-методом).
Задачи в рамках выполнения работы:
• Изучить научную и учебно-методическую литературу по теме;
• Численно реализовать метод МДМ в пакете Matlab;
• Численно реализовать метод Гильберта в пакете Matlab;
• Реализовать пользовательский интерфейс для удобного использования методов;
• Провести численные эксперименты;
• Сравнить и проанализировать полученные результаты
В данной выпускной квалификационной работе была разработана численная реализация методов проектирования нуля Евклидова пространства на выпуклый многогранник следующими методами поиска ближайшей точки: МДМ-методом, методом Гильберта.
Для разработки приложения использовалась интерактивная среда программирования Matlab R2013b. Проведены тесты для случая различной размерности пространства. Был изучен предложенный, теоретический материал, что позволило качественно и быстро справиться с поставленными целями и задачами:
Изучена научная и учебно-методическая литература по теме;
• Численно реализован метод МДМ в пакете Matlab;
• Численно реализован метод Гильберта в пакете Matlab;
• Разработан удобный пользовательский интерфейс, включающий в себя все необходимые объекты;
• Проведены численные эксперименты;
• Сравнены и проанализированы полученные результаты.
На основе проделанных тестов сделан следующий вывод: в пространстве с большой размерностью эффективнее использовать метод Гильберта, т.к. время, потраченное для решения поставленной задачи в данном случае, меньше, чем в МДМ-методе, но для более точного результата эффективнее использовать МДМ-метод. В пространстве с малой размерностью, более точный результат дает метод Гильберта.
