Задача динамічної підтримки опуклої оболонки належить класу динамічних задач обчислювальної геометрії. Вона полягає в підтримці опуклої оболонки для набору вхідних даних що динамічно змінюються, тобто додаються, видаляються або змінюються.
Формальна постановка задачі
Задані порожня множина S і послідовність із N точок (р1, р2, ..., рN ), кожна з яких або додається до множини S, або вилучається з неї. Необхідно підтримувати опуклу оболонку множини S. Використовується той факт, що границя опуклої оболонки є об'єднанням двох (опуклих) монотонних ламаних ліній (ланцюгів), які обмежують оболонку зверху і знизу і відповідно до цього називаються В-оболонкою і Н-оболонкою множини точок. Розглянемо побудову В-оболонки.
Алгоритм
Цей розділ містить текст, що не відповідає . (червень 2014) |
Відповідна структура даних організована наступним чином. Її основою є збалансоване за висотою двійкове дерево пошуку Т, листки якого використовуються для збереження точок поточної множини. Процедура пошуку буде проводитися відповідно до значення абсциси точок, тобто проходження листків дерева зліва направо дає множину точок, впорядковану за x-координатою. Зазначимо, що послідовність точок В-оболонки (її вершин) також впорядкована за зростанням абсциси, і, тому вона є підпослідовністю глобальної послідовності точок, яка зберігається в листках дерева. Упорядковуємо S за x-координатою. Нехай v — вузол дерева Т. Позначимо через ЛСИН[v] і ПСИН[v] його лівого і правого нащадків відповідно. Побудуємо В-оболонку точок, які зберігаються в листках піддерева з коренем у вузлі v. Позначимо через U(v) В-оболонку множини точок, які зберігаються в листках піддерева з коренем v. Виходячи із принципу індукції, припустимо, що вже існують U(ЛСИН[v]) і U(ПСИН[v]). Далі (мал. 2) визначаються дві опорні точки р1 і р2 єдиного спільного опорного відрізку для двох оболонок. Тут використовується функція З'ЄДНАТИ(U1, U2), яка дозволяє знайти опорний відрізок для двох В-оболонок U1, U2. Функція З'ЄДНАТИ дозволяє ефективно розчіпляти U1 на два ланцюги, які складають впорядковану пару (U11, U12), і аналогично U2- на пару ланцюгів (U21, U22). При цьому виконується така умова: опорна точка р1 ∈ U1 входить до складу U11, а точка р2 ∈ U2 — до складу U22 (тобто в обох випадках опорна точка належить «зовнішньому» підланцюгу). На цьому етапі, зчепивши U11 і U22, одержуємо шукану В-оболонку U1 ∪ U2. Природно, щоб кожен вузол v дерева Т вказував на зчеплену чергу, яка представляє ту частину U(v), яка не належить U(БАТЬКО[v]).
Обернена операція: маючи U(v), одержати U(ЛСИН[v]) і U(ПСИН[v]).
Знаючи ребро [р1, р2], яке з'єднує опорні точки (одне ціле число J[v], яке вказує на положення точки р1 у ланцюзі вершин U(v)), можна розчепити U(v) на ланцюги U11 і U22, які в свою чергу можуть бути зчеплені з ланцюгами, що зберігаються в ЛСИН[v] і ПСИН[v] відповідно. Структура даних Т доповнюється такими атрибутами, які пов'язуються з кожним вузлом v дерева:
- Вказівником на зчеплену чергу Q[v], яка містить частину U(v), що не входить до U(БАТЬКО[v]) (якщо v є коренем, то Q[v]=U(v)).
- Цілим числом J[v], яке вказує на положення (індекс) лівої опорної точки в U(v)
Функція З'ЄДНАТИ(U1, U2):
- Знайти р1 і р2.
- Розчепити U1 на U11 та U12.
- Розчепити U2 на U21 та U22.
- Зчепити U11 з U22 ⇔ CH(S1 ∪ S2): U11*U22
Структура даних використовує пам'ять об'ємом О(N).
Враховуючи, що операції розчеплення і зчеплення зчеплених черг є стандартними, наша увага буде зосереджена на операції, що виконується функцією З'ЄДНАТИ, для якої був запропонований наступний розв'язок:
Лема 1 З'єднання двох розділених опуклих ланцюгів, які містять в сумі N точок, може бути виконане за О(logN) кроків.
Доведення. Нехай дано дві В-оболонки U1, U2 і дві вершини q1 ∈ U1, q2∈U2. Кожна із цих двох вершин може бути класифікована відносно відрізка [q1,q2] як опукла, опорна або ввігнута. Залежно від класифікації можливі 9 випадків, схематично зображених на малюнку 3(а). Усі випадки зрозумілі за винятком випадку (q1,q2) = (ввігнута, ввігнута), який детальніше представлений на малюнку 3 (б). Нехай пряма l1 проходить через q1 і її правого сусіда на U1. Аналогічно пряма l2 проходить через q2 і її лівого сусіда на U2. Позначимо через р точку перетину прямих l1 і l2. U1 і U2 розділимі вертикаллю l.
- Припустимо, що точка р знаходиться праворуч від прямої l. р1 може належати лише заштрихованій області і u(y) < v(y) ⇒ довільна вершина q" ∈ U2прав. відносно q2, є ввігнутою відносно відрізка [q',q"], де q' — довільна вершина U1 і U2прав. відносно q2 не розглядається. Що стосується ланцюга ліворуч від вершини q1, то для нього не можна це стверджувати.
- Якщо точка перетину р знаходиться ліворуч від прямої l, то ланцюг ліворуч від вершини q1 можна не розглядати.
Посилання
- - основні алгоритми обчислювальної геометрії
- Overmars, M. H.; (1981), Maintenance of configurations in the plane, , 23 (2): 166—204, doi:10.1016/0022-0000(81)90012-X.
- Jacob Rico, Dynamic Planar Convex Hull [ 4 червня 2011 у Wayback Machine.] (2002), a BRICS [ 22 квітня 2011 у Wayback Machine.] dissertation
Це незавершена стаття про програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zadacha dinamichnoyi pidtrimki opukloyi obolonki nalezhit klasu dinamichnih zadach obchislyuvalnoyi geometriyi Vona polyagaye v pidtrimci opukloyi obolonki dlya naboru vhidnih danih sho dinamichno zminyuyutsya tobto dodayutsya vidalyayutsya abo zminyuyutsya Formalna postanovka zadachiZadani porozhnya mnozhina S i poslidovnist iz N tochok r1 r2 rN kozhna z yakih abo dodayetsya do mnozhini S abo viluchayetsya z neyi Neobhidno pidtrimuvati opuklu obolonku mnozhini S Vikoristovuyetsya toj fakt sho granicya opukloyi obolonki ye ob yednannyam dvoh opuklih monotonnih lamanih linij lancyugiv yaki obmezhuyut obolonku zverhu i znizu i vidpovidno do cogo nazivayutsya V obolonkoyu i N obolonkoyu mnozhini tochok Rozglyanemo pobudovu V obolonki AlgoritmCej rozdil mistit tekst sho ne vidpovidaye enciklopedichnomu stilyu Bud laska dopomozhit udoskonaliti cej rozdil pogodivshi stil vikladu zi stilistichnimi pravilami Vikipediyi Mozhlivo storinka obgovorennya mistit zauvazhennya shodo potribnih zmin cherven 2014 Vidpovidna struktura danih organizovana nastupnim chinom Yiyi osnovoyu ye zbalansovane za visotoyu dvijkove derevo poshuku T listki yakogo vikoristovuyutsya dlya zberezhennya tochok potochnoyi mnozhini Procedura poshuku bude provoditisya vidpovidno do znachennya abscisi tochok tobto prohodzhennya listkiv dereva zliva napravo daye mnozhinu tochok vporyadkovanu za x koordinatoyu Zaznachimo sho poslidovnist tochok V obolonki yiyi vershin takozh vporyadkovana za zrostannyam abscisi i tomu vona ye pidposlidovnistyu globalnoyi poslidovnosti tochok yaka zberigayetsya v listkah dereva Uporyadkovuyemo S za x koordinatoyu Nehaj v vuzol dereva T Poznachimo cherez LSIN v i PSIN v jogo livogo i pravogo nashadkiv vidpovidno Pobuduyemo V obolonku tochok yaki zberigayutsya v listkah piddereva z korenem u vuzli v Poznachimo cherez U v V obolonku mnozhini tochok yaki zberigayutsya v listkah piddereva z korenem v Vihodyachi iz principu indukciyi pripustimo sho vzhe isnuyut U LSIN v i U PSIN v Dali mal 2 viznachayutsya dvi oporni tochki r1 i r2 yedinogo spilnogo opornogo vidrizku dlya dvoh obolonok Tut vikoristovuyetsya funkciya Z YeDNATI U1 U2 yaka dozvolyaye znajti opornij vidrizok dlya dvoh V obolonok U1 U2 Funkciya Z YeDNATI dozvolyaye efektivno rozchiplyati U1 na dva lancyugi yaki skladayut vporyadkovanu paru U11 U12 i analogichno U2 na paru lancyugiv U21 U22 Pri comu vikonuyetsya taka umova oporna tochka r1 U1 vhodit do skladu U11 a tochka r2 U2 do skladu U22 tobto v oboh vipadkah oporna tochka nalezhit zovnishnomu pidlancyugu Na comu etapi zchepivshi U11 i U22 oderzhuyemo shukanu V obolonku U1 U2 Prirodno shob kozhen vuzol v dereva T vkazuvav na zcheplenu chergu yaka predstavlyaye tu chastinu U v yaka ne nalezhit U BATKO v Obernena operaciya mayuchi U v oderzhati U LSIN v i U PSIN v Znayuchi rebro r1 r2 yake z yednuye oporni tochki odne cile chislo J v yake vkazuye na polozhennya tochki r1 u lancyuzi vershin U v mozhna rozchepiti U v na lancyugi U11 i U22 yaki v svoyu chergu mozhut buti zchepleni z lancyugami sho zberigayutsya v LSIN v i PSIN v vidpovidno Struktura danih T dopovnyuyetsya takimi atributami yaki pov yazuyutsya z kozhnim vuzlom v dereva Vkazivnikom na zcheplenu chergu Q v yaka mistit chastinu U v sho ne vhodit do U BATKO v yaksho v ye korenem to Q v U v Cilim chislom J v yake vkazuye na polozhennya indeks livoyi opornoyi tochki v U v Funkciya Z YeDNATI U1 U2 Znajti r1 i r2 Rozchepiti U1 na U11 ta U12 Rozchepiti U2 na U21 ta U22 Zchepiti U11 z U22 CH S1 S2 U11 U22 Struktura danih vikoristovuye pam yat ob yemom O N Vrahovuyuchi sho operaciyi rozcheplennya i zcheplennya zcheplenih cherg ye standartnimi nasha uvaga bude zoseredzhena na operaciyi sho vikonuyetsya funkciyeyu Z YeDNATI dlya yakoyi buv zaproponovanij nastupnij rozv yazok Lema 1 Z yednannya dvoh rozdilenih opuklih lancyugiv yaki mistyat v sumi N tochok mozhe buti vikonane za O logN krokiv Dovedennya Nehaj dano dvi V obolonki U1 U2 i dvi vershini q1 U1 q2 U2 Kozhna iz cih dvoh vershin mozhe buti klasifikovana vidnosno vidrizka q1 q2 yak opukla oporna abo vvignuta Zalezhno vid klasifikaciyi mozhlivi 9 vipadkiv shematichno zobrazhenih na malyunku 3 a Usi vipadki zrozumili za vinyatkom vipadku q1 q2 vvignuta vvignuta yakij detalnishe predstavlenij na malyunku 3 b Nehaj pryama l1 prohodit cherez q1 i yiyi pravogo susida na U1 Analogichno pryama l2 prohodit cherez q2 i yiyi livogo susida na U2 Poznachimo cherez r tochku peretinu pryamih l1 i l2 U1 i U2 rozdilimi vertikallyu l Pripustimo sho tochka r znahoditsya pravoruch vid pryamoyi l r1 mozhe nalezhati lishe zashtrihovanij oblasti i u y lt v y dovilna vershina q U2prav vidnosno q2 ye vvignutoyu vidnosno vidrizka q q de q dovilna vershina U1 i U2prav vidnosno q2 ne rozglyadayetsya Sho stosuyetsya lancyuga livoruch vid vershini q1 to dlya nogo ne mozhna ce stverdzhuvati Yaksho tochka peretinu r znahoditsya livoruch vid pryamoyi l to lancyug livoruch vid vershini q1 mozhna ne rozglyadati Posilannya osnovni algoritmi obchislyuvalnoyi geometriyi Overmars M H 1981 Maintenance of configurations in the plane 23 2 166 204 doi 10 1016 0022 0000 81 90012 X Jacob Rico Dynamic Planar Convex Hull 4 chervnya 2011 u Wayback Machine 2002 a BRICS 22 kvitnya 2011 u Wayback Machine dissertationCe nezavershena stattya pro programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi