Попередня Змiст Наступна

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

Шукатимемо алгоритми, оцінка яких у гіршому випадку менша О(NlogN).
Алгоритм Лі. Нехай p1 - найлівіша вершина заданого простого многокутника P, а (p1, p2, ..., pN) - впорядкована циклічна послідовність його вершин (за вершиною pN йде p1). Нехай внутрішня частина P залишається праворуч при обході його границі в указаному порядку (множина вершин многокутника орієнтована за годинниковою стрілкою). Нехай pM - найправіша вершина. p1 та pM граничні точки опуклої оболонки многокутника P. Вони розбивають послідовність вершин многокутника на два ланцюги: один від p1 до pM, другий - від pM до p1. Достатньо дослідити побудову опуклої оболонки для ланцюга (p1, p2, ..., pM), яку будемо називати верхньою оболонкою.
Мал. 4.22. Верхня опукла оболонка простого многокутника.
Нехай (q1, q2, ..., qR) - підпослідовність послідовністі (p1, p2, ..., pM), в якій q1 = p1 та qR = pM, - шукана опукла оболонка многокутника. Кожне ребро qiqi+1 є "кришкою" "кармана" Ki, де карман Ki - це підланцюг послідовності (p1, p2, ..., pM), першою та останньою вершинами якого є qi та qi+1 відповідно.
Алгоритм проходить ланцюг (p1, p2, ..., pM) та послідовно будує кришки усіх карманів. Критичною будемо називати вершину, яка з останньою знайденою вершиною типу q утворює карман. Кроком просування будемо називати перехід від однієї критичної вершини до іншої (мал.4.23). Наприклад, на третьому кроці критичною точкою є p4. Наступною критичною точкою буде p7. При цьому критична точка p4 не належить опуклій оболонці.
Мал. 4.23. Кроки просування алгоритму.
Припустимо, що границя многокутника переглядається від вершини p1 до ps (sM) і вершина ps = qi є критичною. Позначимо через u вершину границі Р, яка передує qi. Залежно від положення u відносно орієнтованого відрізка qMqi мають місце два випадки:
  1. Вершина u знаходиться праворуч qMqi або на ньому. У цьому випадку у вертикальній смузі, визначеній вершинами qM і qi, досліджуються три області (1,2,3), які визначаються: прямою, що проходить через точки qi-1 та qi, променем, який є продовженням відрізку qiu, та частиною границі многокутника P, яка відповідає карману Ki-1 (мал. 4.24 (1) ).
    2. Мал. 4.24 (1)
  2. Вершина u знаходиться ліворуч від qMqi. У цьому випадку додається до розгляду четверта область (4), мал. 4.24 (2).
    3. Мал. 4.24 (2)
Позначимо через v вершину, яка слідує за qi на границі многокутника P. Ця вершина v може бути в одній із областей. В областях 2 та 3 вершина v буде критичною, в інших - ні. Розглянемо випадки розташування вершини v в кожній із цих областей (мал. 4.25 ).
Область 1. Границя многокутника заходить у карман (Мал. 4.25 (а)). Рухаємось по границі до тих пір, поки не досягнемо першого ребра границі, одна з вершин w якого знаходиться зовні кармана (в області 2). Так як многокутник Р простий, а карман та його кришки також утворюють прості многокутники, то, згідно з теоремою про Жорданову криву, границя многокутника Р обов'язково перетинає кришку кармана. Переходимо до обробки w а, отже, до наступного випадку.
Мал. 4.25 (а)
Область 2. v в області 2 є критичною (Мал. 4.25 (б)). Шукається опорна пряма з вершини v до ланцюга (q1,q2,...,qi-1). Якщо пряма містить qr (r < i), то вершини (qr+1, qr+2, ...,qi) вилучаються, а v береться як нова qr+1. v - вершина опуклої оболонки, так як вона зовнішня відносно оболонки (q1, q2, ...,qМ).
Мал. 4.25 (б)
Область 3. Вершина v є критичною і вибирається як qi+1 (Мал. 4.25 (в)).
Мал. 4.25 (в)
Область 4. У цьому випадку границя многокутника заходить всередину опуклої оболонки. Як і в першому випадку рухаємось по границі многокутника до тих пір, доки не досягнемо першого ребра, яке має властивість: одна з його вершин є зовнішньою до області 4 або співпадає з qM. В останньому випадку процедура завершується. У першому ж випадку вершина v належить області 3 або 2 і обробляється відповідно.(Мал.4.25 (г)).
Мал. 4.25 (г)
Алгоритм
procedure ОПУКЛА_ОБОЛОНКА_ПРОСТОГО_МНОГОКУТНИКА
(p1, ..., pM)
begin P (p2, ..., pM);
Q q0 ;
Q p1 ;
while (P Ø ) do
begin v P;
if ((qi-1qiv) - правий поворот)
(* області *) then
if( (uq1v) - правий поворот) (*області *) then
if (qMqiv) - правий поворот
(* область *) then Q v
else (* область *)
while (ПЕРЕДНІЙ(Р) знаходиться
зліва від qMqi або на ньому) do
ВИШТОВХНУТИ Р
else (* область *)
while (ПЕРЕДНІЙ(Р) знаходиться ліворуч
від qiqi-1 або на ньому) do
ВИШТОВХНУТИ Р
else (* область *)
begin while ((qi-1qiv) - лівий поворот)
do ВИШТОВХНУТИ Q;
Q v
end
end
end.
Аналіз складності алгоритму. Після ініціалізації кожна вершина границі відвідується рівно один раз, перш ніж вона буде прийнята або виштовхнута. Обробка кожної вершини многокутника здійснюється за константний час. Враховуючи, що послідовністі (р1,..., рМ) і (q1, ..., qR) містять O(M) елементів, маємо теорему:
Теорема 4.12 Опукла оболонка простого многокутника з N вершинами може бути побудована за оптимальний час Q(N) при використанні пам'яті об'ємом Q(N).

Попередня Змiст Наступна