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

Будуємо дві прямі: 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 сама дальня точка(S, l, r);

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

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

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

end;

begin

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

r0 (x0, y0 - e);

Швидка опукла оболонка (S, l0, r0);

видалити точку r0/* це еквівалентно тому, якщо покласти e = 0 */

end.

Алгоритм типу розділяй та пануй

Припустимо, що при розв’язку задачі побудови опуклої оболонки початкова множина точок S була розбита на дві частини S1 та S2, кожна з яких містить половину точок множини S. Якщо тепер рекурсивно знайти CH(S1) та CH(S2), то опуклу оболонку множини S можна знайти з рівності: CH(S1  S2) = CH( CH(S1)  CH(S2)). При цьому треба пам’ятати, що CH(S1) та CH(S2) – це опуклі многокутники. Алгоритм розділяй та пануй має наступний вигляд:

1. Якщо |S| k (k – невелике ціле число), то побудувати опуклу оболонку одним із прямих методів та зупинитися; інакше перейти до кроку 2.

2. Розбити множину S довільним чином на дві приблизно рівні за потужністю множини S1 та S2.