Опукла оболонка

p[1] точка з найменшою y координатою;

p[2] точка з множини S, для якої кут між прямою p[2] - p[1] та віссю Ox найменший;

print (p[1], p[2]);

i 2;

while (p[i] p[1]) do

begin

p[i + 1] точка з множини S, для якої кут p[i - 1] p[i] p[i + 1] є найбільшим;

i i + 1;

print (p[i]);

end.

Теорема. Часова оцінка обходу Джарвіса дорівнює O(N2).

Оскільки всі N точок можуть лежати на опуклій оболонці, а алгоритм Джарвіса вимагає лінійний час для знаходження кожної наступної точки оболонки, то в найгіршому випадку часова оцінка дорівнює O(N2). Обхід Джарвіса є ефективним, якщо кількість вершин опуклої оболонки h є малою у порівнянні зі значенням N – часова оцінка у цьому випадку дорівнюватиме O(N * h).

Алгоритм апроксимації опуклої оболонки

При знаходженні наближеної опуклої оболонки ми розмінюємо точність на простоту та ефективність алгоритму.

Знайдемо мінімальне та максимальне значення х координати точок множини S та розіб’ємо вертикальну полосу між ними на k полос рівної ширини. В кожній із цих k полос шукаються дві точки, які мають мінімальну та максимальну у координату (обирається 2k точок). Обираються також точки з екстремальними значеннями х координати; якщо їх декілька, то обираються дві точки з екстремальними значеннями у координати (максимум обирається 4 точки). Обрана множина містить не більш ніж 2k + 4 точок і позначимо її через S*. Далі можна застосувати алгоритм Грехема побудови опуклої оболонки для множини точок S*.

Приклад. Множину точок S розбито на k = 4 полоси. В кожній полосі обрано дві точки. Для утвореної множини S* побудовано опуклу оболонку.

Теорема. Довільна точка p S, яка не попала всередину наближеної опуклої оболонки, знаходиться на відстані, не більшої за значення (xmax - xmin) / k.

Швидкі методи побудови опуклої оболонки

Розіб’ємо множину S з N точок на дві підмножини, кожна з яких буде містити одну з двох ламаних, об’єднання яких дає многокутник опуклої оболонки. Початкове розбиття множини точок визначається прямою, що проходить через дві точки l та r, які мають відповідно найменшу та найбільшу абсцису. Позначимо через S1 підмножину точок, яка розташована вище або на прямій, а через S2 – підмножину точок, яка розташована нижче або на прямій. Якщо бути точним, то {S1, S2} не є розбиттям множини S, оскільки {l, r} S1 S2. Далі множини S1 та S2 обробляються наступним чином (розглянемо на прикладі множини S1).

Знайдемо точку h, для якої трикутник lhr має максимальну площу серед усіх інших трикутників (якщо таких точок декілька, то обираємо ту, в якій кут hlr більший). Точка h гарантовано належить опуклій оболонці. Якщо провести через h пряму, паралельну lr, то над ній не буде жодної точки множини S. Якщо на цій прямій лежать декілька точок, то згідно з припущенням точка h буде самою лівою з них.