|
ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».
Кафедра информационных технологий и автоматизации проектирования
Вычислительная геометрия
Отчёт по лабораторной работе №2
Группа: М-490702
Студент: Беланов И.Н.
Преподаватель: Кац Е.И.
Екатеринбург
Постановка задачи:
На плоскости задано N точек, которые могут быть:
1). Распределены равномерно в прямоугольнике.
2). Распределены равномерно в круге.
3). Распределены нормально.
Даны 2 алгоритма, которые решают задачу нахождения выпуклой оболочки: алгоритм заворачивания подарка (алгоритм Джарвиса), оптимальный алгоритм (алгоритм Грэхема).
Реализовать эти алгоритмы и для каждого из них для каждого распределения составить график зависимости времени выполнения алгоритма от количества точек.
Результат работы:
Количество точек N | Среднее время выполнения (микросекунды) | |||||
Алгоритм заворачивания подарка (Джарвис) | Оптимальный алгоритм (Грэхем) | |||||
RECT | CIRCLE | NORMAL | RECT | CIRCLE | NORMAL | |
График зависимости времени выполнения от количества точек
при равномерном распределении в прямоугольнике:
J (Jarvis) – алгоритм заворачивания подарка; G (Graham) – оптимальный алгоритм;
График зависимости времени выполнения от количества точек
при равномерном распределении в круге:
J (Jarvis) – алгоритм заворачивания подарка; G (Graham) – оптимальный алгоритм;
График зависимости времени выполнения от количества точек
при нормальном распределении:
J (Jarvis) – алгоритм заворачивания подарка; G (Graham) – оптимальный алгоритм;
ВЫВОД:
Исходя из этих графиков, можно сделать вывод, что предпочтение тому или иному алгоритму следует делать в зависимости от поставленной задачи. В данном случае время работы алгоритма заворачивания подарка меняется в зависимости от количества точек на оболочке. А время работы оптимального алгоритма от этого фактора не зависит и, как следствие, на всех трёх графиках одинаковое.
1) При равномерном распределении в прямоугольнике алгоритмы работают почти одинаково (в моей реализации оптимальный алгоритм немного проигрывает по скорости).
2) При равномерном распределении в круге точек на оболочке больше, поэтому алгоритм заворачивания подарка здесь проигрывает.
3) При нормальном распределении точек на оболочке не много, поэтому алгоритм заворачивания подарка здесь выигрывает.
Дата добавления: 2015-08-28; просмотров: 120 | Нарушение авторских прав
<== предыдущая лекция | | | следующая лекция ==> |
Осталось две недели до окончания приема заявок на участие во Всероссийском кинофестивале «ЛАМПА» | | | В4.Решение прямоугольного треугольника(№ 27232) (№ 27233) (№ 27234) (№ 27235) (№ 27236) |