Опукла оболонка, Детальна інформація

while (p[i] \xF0B9\xF020p[1]) do

begin

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

i \xF0AC\xF020i + 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* побудовано опуклу оболонку.

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

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

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

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

Будуємо дві прямі: L1 (сполучає точки l та h) та L2 (проходить через точки h та r). Для кожної точки множини S1 визначаємо її положення відносно цих прямих. Точки, які попали в трикутник lhr, можуть бути вилучені з подальшої обробки. Жодна з точок не знаходиться зліва від L1 та зліва від L2 (напрямки прямих вказано на рисунку). Точки, розташовані зліва від L1 чи на ній, утворюють множину S11. Аналогічно утворюється множина S12. Утворені множини S11 та S12 передаються далі на наступний рівень рекурсивної обробки.

Вибір початкових значень {l0, r0} точок l та r можна спростити. В якості l візьмемо точку (x0, y0), яка має найменшу абсцису, а в якості r візьмемо точку (x0, y0 - e), де e – мале додатне число. Вертикальна пряма, що проходить через l, буде першою прямою, яка розбиває множину точок S. Другою прямою буде пряма, що проходить через точки з екстремальними абсцисами.

Через * далі позначено операцію конкатенації списків.

Швидка опукла оболонка (S, l, r)

if (S = {l, r}) then return (l, r) /* опукла оболонка складається з єдиного орієнтованого ребра */

else

begin

h \xF0AC\xF020сама дальня точка(S, l, r);

S1 \xF0AC\xF020точки множини S, розташовані зліва від прямої lh чи на ній;

S2 \xF0AC\xF020точки множини S, розташовані зліва від прямої hr чи на ній;

return Швидка опукла оболонка (S1, l, r) * (Швидка опукла оболонка (S2, h, r) - h);

end;

begin

l0 \xF0AC\xF020(x0, y0) \xF0AC\xF020точка множини S з найменшою абсцисою;