Quickhull - Quickhull - Wikipedia

Quickhull je metoda výpočtu konvexní obal konečné sady bodů v n-rozměrný prostor. Používá a rozděl a panuj podobný přístup jako quicksort, od kterého je odvozen jeho název. Za jeho nejhorší případ se považuje složitost pro 2-dimenzionální a 3-dimenzionální prostor ${ displaystyle O (n log (r))}$, kde ${ displaystyle n}$ je počet vstupních bodů a ${ displaystyle r}$ je počet zpracovaných bodů^[1]. Na rozdíl od quicksortu však neexistuje žádný zřejmý způsob, jak převést quickhull na randomizovaný algoritmus. Přesto existují díla z Vyhlazená analýza což nám říká, že 2-dimenzionální algoritmus Quick hull očekával dobu běhu ${ displaystyle O (n log (n))}$. Vskutku, ^[2] a související práce ukazují, že počet bodů na konvexním trupu libovolné náhodně narušené množiny bodů s Gaussovým šumem je ${ displaystyle O ({ sqrt { log n}})}$ z čehož vyplývá, že rychlý trup (a mnoho dalších algoritmů) může trvat jen čas ${ displaystyle O (n { sqrt { log n}})}$ na libovolnou sadu narušených bodů.

N-rozměrný Quickhull vynalezl v roce 1996 C. Bradford Barber, David P. Dobkin a Hannu Huhdanpaa.^[1] Jednalo se o rozšíření rovinného Quickhullova algoritmu Jonathana Scotta Greenfielda z roku 1990, ačkoli autoři z roku 1996 o jeho metodách nevěděli.^[3] Místo toho to Barber et al popisuje jako deterministickou variantu Clarksonova a Shorova algoritmu z roku 1989.^[1]

Tato animace zobrazuje algoritmus quickhull.

Algoritmus

Kroky 1–2: Rozdělte body do dvou podmnožin

Za průměrných okolností algoritmus funguje docela dobře, ale zpracování se obvykle zpomalí v případech vysoké symetrie nebo bodů ležících na obvodu kruhu. Algoritmus lze rozdělit na následující kroky:^[3]

1. Najděte body s minimálními a maximálními souřadnicemi x, protože ty budou vždy součástí konvexního trupu. Pokud existuje mnoho bodů se stejným minimem / maximem x, použijte odpovídající body s minimem / maximem y.
2. Pomocí čáry tvořené dvěma body rozdělte množinu na dvě podmnožiny bodů, které budou zpracovány rekurzivně.
3. Určete bod na jedné straně přímky s maximální vzdáleností od přímky. Tento bod tvoří trojúhelník s přímkami.
4. Body ležící uvnitř tohoto trojúhelníku nemohou být součástí konvexního trupu, a proto je lze v následujících krocích ignorovat.
5. Opakujte předchozí dva kroky na dvou liniích tvořených trojúhelníkem (ne počáteční linii).
6. Pokračujte v tom, dokud nezůstanou žádné další body, rekurze skončila a vybrané body tvoří konvexní trup.

Kroky 3 - 5: Najděte bod maximální vzdálenosti, ignorujte body uvnitř trojúhelníku a opakujte to

Krok 6: Opakujte, dokud nezůstanou žádné další body

Problém je složitější v případě vyšší dimenze, protože trup je postaven z mnoha aspektů; datová struktura to musí zohlednit a zaznamenat také přímku / rovinu / nadrovinu (hřeben) sdílenou sousedními fazetami. Pro d rozměry:^[1]

1. Výběr d +1 body ze sady, které nesdílejí rovinu nebo nadrovinu. To tvoří počáteční trup s fazetami Fs [].
2. Pro každého F v Fs [], najděte všechny nepřiřazené body, které jsou „nad“, tj. směřující od středu trupu, a přidejte jej do „vnější“ sady F.O. spojený s F.
3. Pro každého F s neprázdným F.O.:
   1. Najděte bod p s maximální vzdáleností od F. Přidáme to do trupu.
   2. Vytvořte viditelnou sadu PROTI a inicializujte jej na F. Rozšířit PROTI ve všech směrech pro sousední fazety F v dokud nebudou viditelné žádné další aspekty p. F v být viditelný z p znamená, že p je výše F v
   3. Hranice PROTI pak tvoří soubor obzorových hřebenů H.
   4. Nechat Nové [] být množinou fazet vytvořených z p a všechny hřebeny dovnitř H.
   5. Pro každý nový aspekt v Nové [], proveďte krok (2) a inicializujte své vlastní vnější sady. Tentokrát se podívejte pouze z bodů, které jsou mimo fazetu PROTI pomocí jejich vnějších sad V [i] .O, protože jsme se rozšířili pouze tímto směrem.
   6. Odstraňte nyní interní fazety v PROTI z Fs []. Přidejte nové fazety Nové [] na Fs [] a pokračujte v iteraci.

Pseudokód pro 2D sadu bodů

Vstup = sada S n bodů Předpokládejme, že ve vstupní sadě S bodů jsou alespoň 2 bodyfunkce QuickHull (S) je    // Najděte konvexní trup z množiny S bodů n    Konvexní trup: = {} Najděte levý a pravý nejvíce bodů, řekněte A & B a přidejte A & B do konvexního trupu. Segment AB rozděluje zbývající (n - 2) body do 2 skupin S1 a S2         kde S1 jsou body v S které jsou na pravé straně orientované čáry od A na B,         a S2 jsou body v S které jsou na pravé straně orientované čáry od B na A     NajítHull (S1, A, B) NajítHull (S2, B, A) Výstup: = Konvexní trupkoncová funkcefunkce NajítHull (Sk, P, Q) je    // Najděte body na konvexním trupu ze sady Sk bodů     // které jsou na pravé straně orientované přímky od P do Q    -li Sk nemá smysl pak        vrátit se    Z dané množiny bodů v Sk, najděte nejvzdálenější bod, řekněme C, ze segmentu PQ     Přidat bod C na konvexní trup v místě mezi P a Q     Tři body P, Q, a C rozdělit zbývající body Sk do 3 podmnožin: S0, S1, a S2         kde S0 jsou body uvnitř trojúhelníku PCQ, S1 jsou body na pravé straně orientované čáry od P na C, a S2 jsou body na pravé straně orientované čáry od C na Q. NajítHull (S1, P, C) NajítHull (S2, C, Q) koncová funkce

Pseudokód specializovaný pro 3D případ je k dispozici od Jordan Smith. Zahrnuje podobnou strategii „maximálního bodu“ pro výběr výchozího trupu. Pokud jsou tyto maximální body zdegenerované, je také celý mrak bodů.^[4]

Viz také

• Konvexní trupové algoritmy

Reference

• Dave Mount. „Lecture 3: More Convex Hull Algorithms“.
• Pseudo kód, "http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html ".

externí odkazy

• Implementace QuickHull (GDC 2014) - Prezentace algoritmu s podrobnostmi 3D implementace.