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

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

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

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

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

3. Рекурсивно знайти опуклі оболонки CH(S1) та CH(S2).

4. Злити дві отримані оболонки, утворивши CH(S).

Задача. Опукла оболонка об’єднання опуклих многокутників. Дано два опуклих многокутника P1 та P2. Знайти опуклу оболонку їх об’єднання.

Алгоритм Шеймоса.

1. Знайти деяку внутрішню точку p многокутника P1 – наприклад, центроїд трьох довільних вершин P1. Ця точка буде внутрішньою точкою CH(P1 \xF0C8 P2).

2. Визначити, чи є p внутрішньою точкою P2. Якщо p не є внутрішньою точкою P2, то перейти до кроку 4.

3. p є внутрішньою точкою P2. Вершини P1 та P2 є впорядкованими у відповідності зі значенням полярного кута відносно точки p. За час O(N) можна злити список вершин цих многокутників, отримавши впорядкований список вершин як P1, так і P2. Перейти до кроку 5.

4. p не є внутрішньою точкою P2. Якщо дивитися з точки p, то многокутник P2 лежить у кліні з кутом розвороту меншим чи рівним \xF070. Цей клин визначається двома вершинами u та v многокутника P2, які можуть бути знайдені за лінійний час за один обхід вершин многокутника P2. Ці вершини розбивають границю P2 на два ланцюга вершин, які є монотонними відносно зміни полярного кута з початком в p. При русі по одному ланцюгу кут збільшується, при русі по другому – зменшується. Один з ланцюгів, який є опуклим по напрямку до точки p, може бути видалений, оскільки його вершини будуть внутрішніми точками CH(P1 \xF0C8 P2). Другий ланцюг P2 та границю P1 можна злити в один впорядкований список (за полярним кутом відносно точки p) за лінійний час.

5. До отриманого впорядкованого списку вершин застосувати метод обходу Грехема, який вимагає лінійний час.

Теорема. Опукла оболонка об’єднання двох опуклих многокутників може бути знайдена за час, пропорційний сумарній кількості їх вершин.

Означення. Опорною прямою до опуклого многокутника називається пряма l, яка проходить через деяку вершину многокутника P таким чином, що внутрішня частина P цілком знаходиться по одну сторону від l.

Побічним результатом описаного метода злиття є знаходження опорних прямих для двох опуклих многокутників. Два опуклих многокутника P1 та P2 з n та m вершинами відповідно, таких що один не лежить цілком всередині іншого, мають не більш ніж 2 * min(n, m) опорних прямих. Якщо вже отримано опуклу оболонку об’єднання P1 та P2, то опорні прямі обчислюються в результаті перегляду списку вершин CH(P1 \xF0C8 P2).

Теорема. Кожна пара послідовних вершин CH(P1 \xF0C8 P2), одна з яких належить P1, а друга P2, визначає опорну пряму.

Побудова опуклої оболонки простого многокутника

Алгоритм Лі. Нехай p1 – сама ліва вершина заданого простого многокутника P, а (p1, p2, ..., pN) – впорядкована циклічна послідовність його вершин (за вершиною pN йде p1). Внутрішність P залишається по праву сторону при обході його границі в указаному порядку. Нехай pM – сама права вершина. p1 та pM є граничними точками опуклої оболонки многокутника P. Вони розбивають послідовність вершин многокутника на два ланцюги: один від p1 до pM, другий – від pM до p1. Достатньо дослідити побудову опуклої оболонки для ланцюга (p1, p2, ..., pM), яку будемо називати верхньою оболонкою.

Нехай (q1, q2, ..., qR) – підпослідовність (p1, p2, ..., pM), в якій q1 = p1 та qR = pM – шукана опукла оболонка многокутника. Кожне ребро qiqi+1 є “кришкою кармана” Ki, де карман Ki – це ланцюг послідовності (p1, p2, ..., pM), першою та останньою вершинами якої є qi та qi+1 відповідно.

Алгоритм Лі проходить ланцюг та послідовно будує кришки усіх карманів. Критичною будемо називати вершину, яка з останньою знайденою вершиною типу q утворює карман. Але не кожна критична вершина належить кінцевій опуклій оболонці. Кроком просунення будемо називати перехід від однієї критичної вершини до іншої. Наприклад, на третьому кроці критичною точкою є p4. Наступною критичною точкою буде p7. При цьому критична точка p4 не належить опуклій оболонці.

1 крок 2 крок 3 крок 4 крок

M) і вершина ps = qi є критичною. Позначимо через u вершину границі Р, яка є попередньою до qi. В залежності від положення u відносно орієнтованого відрізка qMqi мають місце два випадки:

1. Вершина u знаходиться справа від qMqi або на ньому. Тоді треба дослідити три області, які визначаються: прямою, що проходить через точки qi-1 та qi; промінем, який є продовженням відрізку qiu та частиною та частиною границі многокутника P, яка відповідає карману Ki-1.

2. Вершина u знаходиться зліва від qMqi. До дослідження треба додати четверту область.

Позначимо через v вершину, яка йде за qi на границі многокутника P. Ця вершина v може знаходитися в одній із областей, які визначено вище. В областях 2 та 3 вершина v буде критичною, в інших – ні. Дослідимо випадки розташування вершини v в кожній із цих областей.

Область 1. Границя многокутника заходить до карману. Рухаємося по границі до тих пір, поки не досягнемо першого ребра границі, одна з вершин w якого знаходиться зовні кармана (тобто в області 2). Це обов’язково відбудеться, оскільки многокутник простий.

Область 2. Шукається опорна пряма з вершини v до ланцюга (q1, q2, ...,qi-1). Якщо ця пряма містить qr (r < i), то вершини (qr+1, qr+2, ...,qi) видаляються, а v береться в якості нової qr+1.

Область 3. Вершина v є критичною і береться в якості qi+1.

Область 4. Границя многокутника заходить всередину опуклої оболонки. Як і в першому випадку будемо рухатися по границі многокутника до тих пір, поки не досягнемо першого ребра, яке має наступні властивості: одна з його вершин є зовнішньою по відношенню до області 4 або співпадає з qM.