Алгоритм швидкої оболонки — метод обчислення опуклої оболонки скінченної множини точок на площині. Використовує підхід «розділяй та володарюй», який полягає в тому, що задача розбивається на підзадачі приблизно однакового розміру. Аналогічний метод, використовується в алгоритмі швидкого сортування, звідси така назва.
Складність алгоритму буде , якщо кількість елементів підзадач буде лінійно зменшуватись зі сталим коефіцієнтом k<1. В найгіршому випадку швидкість буде O(n2) (квадратична).
Алгоритм
Алгоритм можна розбити на наступні етапи:
- Знайти точки з мінімальною і максимальною координатою, вони зобов'язані бути частиною опуклої оболонки.
- Використовуючи лінію, утворену двома точками розділити всю множину точок на дві підмножини, які будуть оброблятися рекурсивно.
- Визначити точку, на одній стороні лінії, з максимальною відстанню від лінії. Знайдені до цього дві точки утворюють з цією точкою трикутник з найбільшою площею.
- Точки, що лежать всередині цього трикутника не може бути частиною опуклої оболонки і, отже, можуть бути проігноровані в наступних кроках.
- Повторіть попередні два кроки для двох ліній, утвореного трикутника (окрім початкової лінії).
- Продовжуйте робити так доти, поки більше точок не залишиться, у кінці рекурсії, вибрані точки, складуть опуклу оболонку.
Переваги
- Алгоритм легко розпаралелити.
- Алгоритм узагальнюється на довільну розмірність.
Недоліки
- Висока квадратична трудомісткість в найгіршому випадку.
Псевдокод
procedure otochka(tochky) begin A := крайня ліва точка B := крайня права точка s1 := множина точок з правої сторони AB s2 := множина точок з лівої сторони AB return [A] + QuickHull(A, B, s1) + [B] + QuickHull(B, A, s2); end; procedure QuickHull(A, B, tochky) begin C := найбільш віддалена точка від прямої AB s1 := множина точок, яка знаходиться на праворуч від відрізка AC s2 := множина точок, яка знаходиться на праворуч від відрізка CB return QuickHull(A, C, s1) + [C] + QuickHull(C, B, s2); end;
Див. також
Посилання
- Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 грудня 1996). (PDF). ACM Transactions on Mathematical Software. 22 (4): 469—483. doi:10.1145/235815.235821. Архів оригіналу (PDF) за 17 жовтня 2013. Процитовано 7 квітня 2014.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm shvidkoyi obolonki metod obchislennya opukloyi obolonki skinchennoyi mnozhini tochok na ploshini Vikoristovuye pidhid rozdilyaj ta volodaryuj yakij polyagaye v tomu sho zadacha rozbivayetsya na pidzadachi priblizno odnakovogo rozmiru Analogichnij metod vikoristovuyetsya v algoritmi shvidkogo sortuvannya zvidsi taka nazva Animaciya pobudovi opukloyi obolonki Skladnist algoritmu bude O n log n displaystyle O n log n yaksho kilkist elementiv pidzadach bude linijno zmenshuvatis zi stalim koeficiyentom k lt 1 V najgirshomu vipadku shvidkist bude O n2 kvadratichna AlgoritmKroki 1 2 Cherez krajni livu ta pravi tochki provodimo liniyu yaka podilit tochki na dvi mnozhini Kroki 3 5 Znahodzhennya maksimalnoyi vidstani do tochki yaka znahoditsya ne vseredini trikutnika ta ne na jogo mezhi Kroki 6 Rekursiya poki zhodnoyi tochki sho zadovolnyaye umovam ne zalishitsya Algoritm mozhna rozbiti na nastupni etapi Znajti tochki z minimalnoyu i maksimalnoyu x displaystyle x koordinatoyu voni zobov yazani buti chastinoyu opukloyi obolonki Vikoristovuyuchi liniyu utvorenu dvoma tochkami rozdiliti vsyu mnozhinu tochok na dvi pidmnozhini yaki budut obroblyatisya rekursivno Viznachiti tochku na odnij storoni liniyi z maksimalnoyu vidstannyu vid liniyi Znajdeni do cogo dvi tochki utvoryuyut z ciyeyu tochkoyu trikutnik z najbilshoyu plosheyu Tochki sho lezhat vseredini cogo trikutnika ne mozhe buti chastinoyu opukloyi obolonki i otzhe mozhut buti proignorovani v nastupnih krokah Povtorit poperedni dva kroki dlya dvoh linij utvorenogo trikutnika okrim pochatkovoyi liniyi Prodovzhujte robiti tak doti poki bilshe tochok ne zalishitsya u kinci rekursiyi vibrani tochki skladut opuklu obolonku Perevagi Algoritm legko rozparaleliti Algoritm uzagalnyuyetsya na dovilnu rozmirnist Nedoliki Visoka kvadratichna trudomistkist v najgirshomu vipadku Psevdokodprocedure otochka tochky begin A krajnya liva tochka B krajnya prava tochka s1 mnozhina tochok z pravoyi storoni AB s2 mnozhina tochok z livoyi storoni AB return A QuickHull A B s1 B QuickHull B A s2 end procedure QuickHull A B tochky begin C najbilsh viddalena tochka vid pryamoyi AB s1 mnozhina tochok yaka znahoditsya na pravoruch vid vidrizka AC s2 mnozhina tochok yaka znahoditsya na pravoruch vid vidrizka CB return QuickHull A C s1 C QuickHull C B s2 end Div takozhAlgoritmi obchislennya opukloyi obolonkiPosilannyaBarber C Bradford Dobkin David P Huhdanpaa Hannu 1 grudnya 1996 PDF ACM Transactions on Mathematical Software 22 4 469 483 doi 10 1145 235815 235821 Arhiv originalu PDF za 17 zhovtnya 2013 Procitovano 7 kvitnya 2014