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



A

Ae

E

I

O

O

e

e

i

"дмножини, кожна з яких буде містити одну з двох ламаних, об’єднання яких дає многокутник опуклої оболонки. Початкове розбиття множини точок визначається прямою, що проходить через дві точки 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 з найменшою абсцисою;

r0 \xF0AC\xF020(x0, y0 - e);

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

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

end.