WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Опукла оболонка - Реферат

Опукла оболонка - Реферат

яких належить 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 крок
Припустимо, що границя многокутника проглянута від вершини 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 є крайньою, але її включення не викликає видалення інших точок;
в) точка pi є внутрішньою і тому вона видаляється.
Теорема. Довільний відкритий алгоритм побудови опуклої оболонки в найгіршому випадку повинен витрачувати на обробку між надходженням послідовних елементів даних час O(log N).
Ефективність відкритого алгоритму полягає у можливості швидко будувати дві опорні прямі до опуклого многокутника, що проходять через задану точку. Позначимо через Ci-1 опуклу оболонку множини {p1, p2, ..., pi-1}. Необхідно побудувати з точки pi опорні прямі до Ci-1, якщо вони існують (коли pi є зовнішньою для Ci-1). Будемо називати опорну пряму лівою чи правою в залежності від того, по яку сторону вона знаходиться якщо дивитися з точки pi на Ci-1.
Означення. Вершина v називається вогнутою, якщо відрізок pv перетинає внутрішню частину многокутника. Якщо дві суміжні з v вершини лежать по одну сторону від прямої, що проходить через p та v, то вершина називається опорною. Інакше вершина називається опуклою.
Якщо v - опорна вершина, то розв'язок задачі завершується. Інакше будуємо опорні прямі. Для знаходження, наприклад, лівої опорної прямої, необхідно рухатися по вершинам многокутника проти чи за годинниковою стрілкою (в залежності від опуклості чи вогнутості вершини v). Таким чином визначаються дві опорні точки.
Теорема. Опукла оболонка множини з N точок на площині може бути побудована за допомогою відкритого алгоритму за час O(N * log N) з часом корекції O(log N).
Loading...

 
 

Цікаве