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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема. Кожна пара послідовних вершин CH(P1  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 не належить опуклій оболонці.