1.3. Теоретические оценки сложности

Наименьший угол может быть найден с использованием лишь арифметических операций и сравнений, не прибегая к явному вычислению значений полярных углов.

Так как все N точек множества могут лежать на его выпуклой оболочке (быть ее вершинами), а алгоритм Джарвиса затрачивает на нахождение каждой точки оболочки линейное время, то время выполнения алгоритма в худшем случае равно О (N²), что хуже, чем у алгоритма Грэхема. Если в действительности число вершин выпуклой оболочки равно h, то время выполнения алгоритма Джарвиса будет 0(hN), и он очень эффективен, когда заранее известно, что значение h мало. Например, если оболочка заданного множества является многоугольником с произвольным постоянным числом сторон, то ее можно найти за линейное относительно числа точек время. Этот факт чрезвычайно важен в свете анализа сложности алгоритмов построения выпуклой оболочки в среднем.

2. Примеры работы алгоритма и иллюстрации (с помощью демонстрационной программы)

Равномерное распределение точек по окну.

1. Сначала проводится сортировка точек по ординате и выделяются точки с максимальной и минимальной координатами.

2. Далее осуществляется построение первой половины выпуклой оболочки:

• точка с минимальным значением координат по оси у принимается за текущую точку в выпуклой оболочке;

• проводятся вектора из текущей точки (1) ко всем остальным;

• для определения следующей точки, принадлежащей выпуклой оболочке, выбирается вектор с минимальным положительным углом (M);

M

i (1, i, M) i

1

• для каждой i-ой точки проверяем знак векторного произведения

, если <0 , то (1, i,M) ориентирован против часовой стрелки и следовательноимеет меньший угол чем(i-ая точка становится точкой М).

• определив следующую точку выпуклой оболочки, рисуем ребро между текущей точкой и следующей:

• делаем текущей точкой следующую повторяем последние четыре пункта до тех пор, пока не достигнем точки с максимальной координатой по оси у;

3. Проход от максимума к минимуму:

достигнув максимума, продолжаем поиск крайних точек (только теперь выбирается векторс минимальным положительным угломотносительно отрицательного направления оси х.)до тех пор, пока не достигнем минимума, на этом процедура построения выпуклой оболочки заканчивается.

В программе реализована генерация трех видов распределений: нормальное, равномерное в прямоугольнике и круге. Это позволяет оценить количество точек выпуклой оболочки. Алгоритм Джарвиса эффективен для распределений с небольшим количеством точек выпуклой оболочки, так как скорость выполнения алгоритма О(hN) гдеh– количество точек в выпуклой оболочке.

3. Описание программы

3.1. Функции

CChildView::CChildView()

Конструктор класса. Вызывается при создании окна приложения.

CChildView::~CChildView()

Деструктор класса. Вызывается при закрытии окна приложения.

void CChildView::Animate()

Вызывается при нажатии пользователем кнопки F5. Показывает пошаговую

анимацию построения выпуклой оболочки.

void CChildView::Create_Convex_hull()

Строит выпуклую оболочку, если количество точек больше 2.

double CChildView::drand()

Генерирует равномерно распределённое случайное число в диапазоне [0,1].

double CChildView::drand0()

Генерирует равномерно распределённое случайное число в диапазоне [-1,1].

void CChildView::drawLineEx(CDC &dc, CPoint p1, CPoint p2)

Чертит линию из точки p1 в точкуp2 с заходом за точкуp2 в указанном контексте устройства.

CPoint CChildView::Even(int Mx,int My, double sigmaX,double sigmaY)

Генерирует равномерно распределённую точку. Границы распределения – первоначальный размер клиентской области окна.

double CChildView::gaussian(double sigma, double mu)

Генерирует нормально распределённое случайное число с заданными параметрами распределения.

void CChildView::Generate()

Генерирует точки. Параметры генерации задаются пользователем в диалоговом окне.

CPoint CChildView::Norm(int Mx, int My, double sigmaX,double sigmaY)

Генерирует равномерно распределённую точку. Границы распределения – первоначальный размер клиентской области окна.

void CChildView::OnEditClearAll()

Удаляются все точки введённые или сгенерированные пользователем.

void CChildView::OnFileOpen()

Открывает текстовый файл с исходными данными (массивом точек).

void CChildView::OnFileSave()

Сохраняет исходные данные (массив точек) в текстовый файл.

void CChildView::OnFileSaveAs()

Сохраняет исходные данные (массив точек) в заданный пользователем текстовый файл.

void CChildView::OnFileSaveCopyAs()

Сохраняет рабочую область окна как картинку (WindowsBitMap)

void CChildView::OnLButtonDown(UINT nFlags, CPoint point)

Добавляет в массив точек точку в которой пользователь нажал левую кнопку «мыши»

void CChildView::OnPaint()

Производит отображение клиентской области окна. Существует три режима отображения:

• Точечный – отображение массива точек

• Выпуклая оболочка – отображение выпуклой оболочки

• Построение – отображение построения выпуклой оболочки по шагам

При пошаговом построении программа ожидает нажатия клавиши F5 и затем отображает следующий шаг. Из пошагового построения можно перейти к немедленному построению выпуклой оболочки.

void CChildView::OnRButtonDown(UINT nFlags, CPoint point)

Вызывает построение выпуклой оболочки.

void CChildView::OnSize( UINT nType, int cx, int cy )

Отслеживает изменения размеров клиентской области окна.

void CChildView::OnUpdateAnimate(CCmdUI* pCmdUI)

Разрешает или запрещает команды меню и горячие клавиши. Когда нет точек – запрещёны все команды, кроме генерации, открытия файла с исходными данными.

void CChildView::OnViewSize()

Отображает текущий размер клиентской области окна.

BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs)

Вызывается перед отображением окна. Используется для задания размеров клиентской области окна.

CPoint CChildView::Rounded(double rho)

Генерирует точку, равномерно распределённую в круге, радиусом rho.

void CChildView::Serialize(CArchive& ar)

Сохраняет или читает данные из текстового файла. Режим работы определяется из свойств входного параметра ar.

3.2. Интерфейс

1. Исходное множество точек можно сформировать тремя способами : при помощи чтения их из уже сформированного файла, для чего необходимо выбрать кнопку или нажатьCtrl+Oи выбрать нужный файл из списка имеющихся файлов, содержащих координаты точек, при помощи левой кнопки мыши расположить точки в произвольном порядке в предназначенной для этого области или сгенерировать точки автоматически, используя для этого кнопкуилиCtrl+Gи выбрав одно из предложенных распределений (равномерное в прямоугольнике и круге, нормальное).

2. Имеется возможность записать сформированное множество точек в файл, для чего необходимо нажать на кнопку или нажатьCtrl+S.

3. После того как множество точек сформировано для инициализации работы алгоритма необходимо нажать кнопку или нажатьCtrl+F5.

4. Для более наглядной демонстрации работы алгоритма имеется возможность прогона процедуры по шагам, для этого необходимо нажать на кнопку или нажатьF5.

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

6. Для подготовки программы к заданию нового множества точек нужно нажать на кнопку или нажатьDel.

7. После завершения работы алгоритма на экране отображается построенная выпуклая оболочка заданного множества точек.