ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».

ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».

Кафедра информационных технологий и автоматизации проектирования

Вычислительная геометрия

Отчёт по лабораторной работе №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