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

Припустимо, що границя многокутника проглянута від вершини p1 до ps (s 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.

Теорема. Опукла оболонка простого многокутника з N вершинами може бути побудована за оптимальний час O(N) з використанням пам’яті об’ємом O(N).

Динамічні алгоритми побудови опуклої оболонки

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

Означення. Часовий проміжок між вводом двох послідовних елементів даних називається затримкою надходження даних.

Задача. Відкритий алгоритм для опуклої оболонки. На площині задана послідовність N точок p1, p2, ..., pN. Необхідно знайти їх опуклу оболонку таким чином, щоб після обробки точки pi була побудована CH(p1, p2, ..., pi). Алгоритм повинен підтримувати деяке представлення поточної опуклої оболонки та коректувати його по мірі надходження точок.

Якщо не брати до уваги часову оцінку, то можна запропонувати наступний алгоритм:

1. Вводити точки поки не буде знайдено три неколінеарні точки. Їх центроїд буде внутрішньою точкою кінцевої опуклої оболонки, а отже підходить в якості початку координат, відносно якого визначаються полярні кути точок при сортуванні.

2. Підтримувати зв’язаний список впорядкованих крайніх точок. При надходженні точки pi вставити її у список відповідно до її полярного кута, витративши час O(i).

3. Виконати перегляд зв’язаного списку крайніх точокметодом Грехема. Можливі три варіанти цього кроку:

а) точка pi є крайньою і її включення викликає видалення деяких інших точок;

б) точка pi є крайньою, але її включення не викликає видалення інших точок;