Programování grafických aplikací (BI-PGA), Přednáška č. 10
3D grafika - Blender: Datové struktury pro 3D
grafiku
Jiří Chludil
Fakulta informačních technologií
České vysoké učení technické v Praze
https://courses.fit.cvut.cz/BI-PGA/
ZS 2024/2025
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 1 / 155Motivace
V různých přednáškách se často zminňují následující pojmy
konvexní obálka
K-D Stromy
zametací hyperrovina
oktalový strom
atd ...
Většina těchto algoritmů souvisí s efektivními algortimy viz. BI-AG1
dříve BI-EFA.
.
Tato přednáška vychází z podkladových materiálů, které vynikly pro
BI-EFA (prof. Ing. Pavel Tvrdík, CSc., Ing. Jiří Chludil a Ing. Petr
Matyáš).
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 2 / 155Výpočetní geometrie
Definice
Cílem výpočetní geometrie je analýza a návrh efektivních algoritmů
pro určování vlastností a vztahů geometrických objektů.
(bezrozměrných geometrických bodů, základních grafických primitiv,
obecně jakýchkoli množin bodů ohraničených pomocí čar nebo ploch).
Řešené problémy:
geometrické vyhledávání,
reprezentace scény
detekce kolize objektů
konstrukce konvexní obálky,
určení polohy objektů,
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 3 / 155 Výpočetní geometrie
Výpočetní geometrie
Definice
Cílem výpočetní geometrie je analýza a návrh efektivních algoritmů
pro určování vlastností a vztahů geometrických objektů.
(bezrozměrných geometrických bodů, základních grafických primitiv,
obecně jakýchkoli množin bodů ohraničených pomocí čar nebo ploch).
Řešené problémy:
geometrické vyhledávání,
reprezentace scény
detekce kolize objektů
konstrukce konvexní obálky,
určení polohy objektů,
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 4 / 155 Kvadrantové stromy
Kvadrantový strom definice
Autory Kvadrantových stromů (Quadtree) jsou Raphael Finkel a
J.L. Bentley,
Definice (Kvadrantový strom)
Kvadrantový strom je 4-ární strom, který splňuje navíc následující
podmínky:
1 každý vnitřní uzel reprezentuje jednu dekompozici 2D prostoru
na čtyři navzájem disjunktní kvadranty resp. oblasti,
2 každý jeho vnitřní uzel má právě 4 potomky s identifikací SV,
SZ, JV, JZ,
3 každý uzel obsahuje prostorová data definující dekompozici (liší
se dle použití),
4 každý list má definovanou maximální kapacitu obsažených
objektů, pokud je překročena, je list dekomponován.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 5 / 155 Kvadrantové stromy
Použití kvadrantového stromu
tento strom je vhodný pro efektivní reprezentaci elementů (dané
souřadnicemi x a y) v 2D prostoru např hmotné body objektů,
což umožňuje:
▶snížení paměťových nároků při zobrazování 2D scény
▶urychlení 3D grafických algoritmů (sledování paprsku),
▶zpracování a analýzu obrazu,
▶efektivní uložení dat pro GIS (Geografické Informační Systémy),
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 6 / 155 Kvadrantové stromy PR Kvadrantový strom
PR kvadrantový strom (Region Point quadtree)
Definice (PR kvadrantový strom)
Je kvadrantový strom s těmito vlastnosti:
1 všechny dekomponované oblasti jsou stejně velké,
2 maximální kapacita pro obsažené elementy je 1,
3 uživatelská data jsou elementy a jsou uloženy jen v listech,
4 pro urychlení výpočtu obsahuje každý uzel souřadnice oblasti,
kterou uzel reprezentuje.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 7 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 8 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
A
A
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 9 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
A
A
B B
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 10 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
A
B A B
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 11 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
A
B A B C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 12 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
A
D
B A B C
D
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 13 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
A
D
B B C
D A
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 14 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
A
D
B B C
E
D A E
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 15 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B C
E
D A E
F
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 16 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B C
E
A E
F D
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 17 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B C
E G A E
F D
C
G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 18 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B
E
A E C
G
F D
C
G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 19 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B
E
A E
F D C
G
C
G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 20 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B
E
A E
F D
CG
C
G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 21 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 22 / 155 Kvadrantové stromy PR Kvadrantový strom
Příklad PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 23 / 155 Kvadrantové stromy PR Kvadrantový strom
Vložení elementu do PR kvadrantového stromu
Postup pro vložení prvku,řekněme (coord, elem), je velmi podobné
pro vložení do BVS jen ve dvou rozměrech.
1 Nejprve se podle souřadnice nalezne list, do kterého nově
vkládáný element patří
▶Klíči jsou zadané souřadnice (dvě pro 2D prostor), které
porovnáváme se středem oblasti, kterou reprezentuje
prohledávaný uzel a vybíráme příslušný kvadrant, do kterého
souřadnice patří.
2 Pokud je list prázdný (neobsahuje žádný element), pak je
element elem vložen do listu.
3 Pokud je list plný, provede se dekompozice uzlu
▶Vytvoří se čtyři potomci dekomponovaného uzlu.
▶Element původně uložený v dekomponovaném uzlu se přesune
do odpovídajícího syna (dle souřadnice uloženého elementu).
▶Rekursivně se provede operaci vkládání pro dekomponovaný
uzel.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 24 / 155 Kvadrantové stromy PR Kvadrantový strom
Hledání elementu v PR kvadrantovém stromu
Algoritmus vyhledání oblasti obsahující hledaný element s 2D
souřadnicí coord v kvadrantovém stromu s kořenem r:
Otestuje se, zda je kořen r listem:
▶Pokud ano, otestuje se, zda je kořen plný (obsahuje odkaz na
uložený element):
⋆Pokud ano, provede se operace nad hledaným elementem a
zadanou souřadnicí coord (např. detekce kolize souřadnice s
uloženým elementem).
⋆Pokud ne, je hledání ukončeno jako neúspěšné.
▶Pokud ne, provede se rekursivně totéž pro odpovídající podstrom
(dle hledané souřadnice coord) reprezentující jeden z kvadrantů.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 25 / 155 Kvadrantové stromy PR Kvadrantový strom
Hledání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 26 / 155 Kvadrantové stromy PR Kvadrantový strom
Hledání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 27 / 155 Kvadrantové stromy PR Kvadrantový strom
Hledání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 28 / 155 Kvadrantové stromy PR Kvadrantový strom
Hledání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 29 / 155 Kvadrantové stromy PR Kvadrantový strom
Hledání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 30 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání elementu z PR kvadrantového stromu
1 Nalezne se list, který obsahuje hledaný element.
2 Provede se výmaz daného elementu.
3 Otestují se sourozence listu, zda jsou listy a jsou prázdné:
▶Pokud ano, stane se jejich otec listem. A vracím se na bod 3.
▶Pokud ne, konec mazání.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 31 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
CG
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 32 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
C
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 33 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
C
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 34 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 35 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 36 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 37 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 38 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 39 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 40 / 155 Kvadrantové stromy PR Kvadrantový strom
Mazání v PR kvadrantového stromu
F
A
D
B B
E
A E
F D H
C G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 41 / 155 Kvadrantové stromy PR Kvadrantový strom
Hodnocení PR kvadrantového stromu
1 Struktura PR kvadrantového stromu je nezávislá na pořadí
vkládaných elementů.
2 V případě větších shluků elementu podstatně roste hloubka
strom.
3 V případě nerovnoměrného rozložení elementů v prostoru je
strom nevyvážený.
4 Operace mazání je velmi jednoduchá.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 42 / 155 Kvadrantové stromy PR Kvadrantový strom
R Kvadrantový strom (Region quadtree)
R Kvadrantový strom (Region quadtree)
Strom reprezentuje černobílý bitmapový obrázek o velikosti
2n × 2n pixelů.
V listech stromu se uchovává hodnota B nebo W.
Použití:
▶bezeztrátová komprese,
▶hledání fraktálních artefaktů.
8 x 8
1 2 3 4 4 x 4
2 x 2
1 2 1 pixel
4 3
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 43 / 155 Kvadrantové stromy P Kvadrantový strom
P kvadrantový strom (Point quadtree)
Definice (P kvadrantový strom)
Je kvadrantový strom s těmito vlastnosti:
1 dekomponované oblasti mohou mít různou velikost, ale plně
pokrývají oblast,
2 maximální kapacita pro obsažené elementy je obvykle 1,
3 uživatelská data jsou elementy a jsou uloženy ve všech uzlech,
4 souřadnice elementu ve vnitřním uzlu určuje bod rozdělení na
čtyři oblasti
Použití:
Obdobné jako u PR kvadrantových stromů.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 44 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 45 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A
A
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 46 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A
A
B B
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 47 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A A
B B
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 48 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A A
B B
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 49 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A A
B B
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 50 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A A
D
B D B
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 51 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A A
D
B D B
E E
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 52 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
A A
D B
B D
E
E C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 53 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
F
A A
D B
B F D
E
E C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 54 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
F
A A
D B
B F D
E
E C
G
C
G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 55 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
F
A A
D B
B F D
E C
E
G
C
G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 56 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
F
A A
D B
B F D
E C
E H
G
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 57 / 155 Kvadrantové stromy P Kvadrantový strom
Příklad P kvadrantového stromu
F
A A
D B
B F D
E C
E H
G
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 58 / 155 Kvadrantové stromy P Kvadrantový strom
Vložení elementu do P kvadrantového stromu
Postup pro vložení prvku,řekněme (coord, elem), je velmi podobné
pro vložení do BVS jen ve dvou rozměrech.
1 Nejprve se podle souřadnice nalezne list, do kterého nově
vkládáný element patří
▶Klíči jsou zadané souřadnice (dvě pro 2D prostor), které
porovnáváme se středem oblasti, kterou reprezentuje
prohledávaný uzel a vybíráme příslušný kvadrant, do kterého
souřadnice patří.
2 Pokud je list prázdný (neobsahuje žádný element), pak je
element elem vložen do listu.
3 Pokud je list plný, provede se dekompozice uzlu dle obsaženého
uzlu
▶Vytvoří se čtyři potomci dekomponovaného uzlu (Středem
dekompozice je souřadnice elementu obsaženého v uzlu).
▶Rekursivně se provede operaci vkládání pro dekomponovaný
uzel.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 59 / 155 Kvadrantové stromy P Kvadrantový strom
Vložení elementu do P kvadrantového stromu
Optimalizované vkládání
1 Souřadnice vkládaných elementů jsou seřazeny podle souřadnice
x.
2 Je vybrán element, jehož x-ová souřadnice je mediánem a
element je vložen do kořene.
3 Dle vybrané souřadnice jsou elementy rozděleny do čtyř skupin.
4 Pro každou skupinu se rekursivně opakuje tato operace.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 60 / 155 Kvadrantové stromy P Kvadrantový strom
Hledání elementu v P kvadrantovém stromu
Algoritmus vyhledání oblasti obsahující hledaný element s 2D
souřadnicí coord v kvadrantovém stromu s kořenem r:
Otestuje se, zda je kořen r listem:
▶Pokud ano, otestuje se, zda je kořen plný (obsahuje odkaz na
uložený element):
⋆Pokud ano, provede se operace nad hledaným elementem a
zadanou souřadnicí coord (např. detekce kolize souřadnice s
uloženým elementem).
⋆Pokud ne, je hledání ukončeno jako neúspěšné.
▶Pokud ne, provede se operace porovnání zadané souřadnice se
souřadnicí obsaženého elementu.
⋆Pokud je shoda souřadnic, element je nalezen.
⋆Pokud ne, provede se rekursivně totéž pro odpovídající podstrom
(dle hledané souřadnice coord) reprezentující jeden z kvadrantů.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 61 / 155 Kvadrantové stromy P Kvadrantový strom
Mazání elementu z P kvadrantového stromu
1 Nalezne se uzel, který obsahuje hledaný element.
2 Otestuje se, zda je uzel listem:
▶Pokud ano, odstraní se element a pokud jsou sourozence listy a
jsou prázdné, provede se sloučení uzlu (jako u PR).
▶Pokud ne, je element nahrazen elementem ze syna, jehož
podstrom má nejmenší hloubku. A rekursivně se provede mazání
elementu v synovi, jehož element byl použit pro náhradu.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 62 / 155 Kvadrantové stromy P Kvadrantový strom
Mazání v P kvadrantového stromu
F
A A
D B
B F D
E C
E H
G
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 63 / 155 Kvadrantové stromy P Kvadrantový strom
Mazání v P kvadrantového stromu
F
A A
D H D F
E C
E
znovu vložit G
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 64 / 155 Kvadrantové stromy P Kvadrantový strom
Mazání v P kvadrantového stromu
F
F
D H
D
E C
E
G
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 65 / 155 Kvadrantové stromy P Kvadrantový strom
Mazání v P kvadrantového stromu
F
F
D H
D
E C
E
G
C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 66 / 155 Kvadrantové stromy P Kvadrantový strom
Hodnocení P kvadrantového stromu
1 Struktura PR kvadrantového stromu je závislá na pořadí
vkládaných elementů.
2 Strom lze konstruovat vyvážený (operace mají log4N složitost).
3 Počet uzlů stromu je blízký počtu vložených elementů
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 67 / 155 Oktalový strom
Oktalový strom
Obdoba kvadrantového stromu v třírozměrném prostoru.
Počet potomků vnitřního uzlu je právě 8.
Používá se pro hierarchickou reprezentaci 3D scén.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 68 / 155 K-D strom
K-D strom
Autor J.L. Bentley,
Definice (K-D strom)
K-D strom je BVS provádějící dělení střídavě podle x-ové a y-ové
souřadnice
1 každý vnitřní uzel reprezentuje jednu dekompozici 2D prostoru
na dvě navzájem disjunktní oblasti,
2 existuje několik variant K-D Stromu:
▶dekomponované oblasti jsou vždy stejně veliké (PR K-D strom),
▶listy jsou vždy prázdné,
▶dekompozice je prováděna dle jedné souřadnice vloženého
elementu (tuto variantu budeme prezentovat)
3 každý jeho vnitřní uzel má právě 2 potomky,
4 každý uzel obsahuje navíc d-rozměrný klíč, podle kterého je
prováděna dekompozice,
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 69 / 155
5 dekompozice je cyklicky prováděna pro jednotlivé složky klíče K-D strom
Příklad 2D K-D stromu
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 70 / 155 K-D strom
Příklad 2D K-D stromu
A
A
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 71 / 155 K-D strom
Příklad 2D K-D stromu
A
A
B B
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 72 / 155 K-D strom
Příklad 2D K-D stromu
A
A
B
B
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 73 / 155 K-D strom
Příklad 2D K-D stromu
A
A
B
B
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 74 / 155 K-D strom
Příklad 2D K-D stromu
A
A
B
B
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 75 / 155 K-D strom
Příklad 2D K-D stromu
A
D A
B
D
B
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 76 / 155 K-D strom
Příklad 2D K-D stromu
A
D A
B
E
D
B E
C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 77 / 155 K-D strom
Příklad 2D K-D stromu
A
D A
B
E
D B
E C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 78 / 155 K-D strom
Příklad 2D K-D stromu
F
A
D A
B
E
D B
F E C
C
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 79 / 155 K-D strom
Příklad 2D K-D stromu
F
A
D A
B
E
D B
F E C
G
C
G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 80 / 155 K-D strom
Příklad 2D K-D stromu
F
A
D A
B
E
D B
F E
C
C G G
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 81 / 155 K-D strom
Příklad 2D K-D stromu
F
A
D A
B
E
D B
F E
C
C G G
H
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 82 / 155 K-D strom
Příklad 2D K-D stromu
F
A
D A
B
E
D B
F E
C
G C
G
H H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 83 / 155 K-D strom
Příklad 2D K-D stromu
F
A
D A
B
E
D B
F E
C
G C
G
H H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 84 / 155 K-D strom
Vložení elementů do K-D stromu
Postup pro vložení elementu, je podobné jako vložení do BVS.
Rozdílem je, že pro porovnávání cyklicky používáme jednotlivé
dimense prvků.
Takový postup může způsobit, že K-D strom bude nevyvážený.
Pro vyvažování nelze použít rotace, protože strom je uspořádán
podle více dimensí.
Vyvažovaní je poměrně obtížná záležitost, kterou řeší K-D-B
stromy, hB stromy a Bkd stromy.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 85 / 155 K-D strom
Vložení elementu do K-D stromu
Postup pro vložení prvku,řekněme (coord, elem), je velmi podobné
pro vložení do BVS.
1 Nejprve se podle souřadnice nalezne list, do kterého nově
vkládaný element patří
▶Klíčem je k-tá souřadnice (k = hloubka mod dimense), která
reprezentuje rozdělení oblasti podle k-té dimense na dvě
disjunktní podoblasti.
2 Provede se dekompozice uzlu:
▶Vytvoří se dva potomci dekomponovaného uzlu a nastaví se
jeho klíč tak, aby původní a vkládaný element byly v různých
oblastech.
▶Element původně uložený v dekomponovaném uzlu se přesune
do odpovídajícího syna (dle souřadnice uloženého elementu) a
nově vkládaný do druhého.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 86 / 155 K-D strom
Mazání bodu z K-D stromu
1 Nalezne se uzel, který obsahuje hledaný bod.
2 Pokud existuje:
1 Vymaže se.
2 Pokud je uzel listem a jeho sourozenec neobsahuje bod, stane se
jeho otec listem.
3 Pokud není uzel listem, musí být vymazaný bod nahrazen jiným.
1 Pokud uzel dělil scénu podle x-ové souřadnice, najdeme uzel R
obsahující bod s maximální x-ovou souøadnicí v levém
podstromu nebo s minimální x-ovou souřadnicí v pravém
podstromu, nalezený bod použijeme jako náhradu a stejný
postup uplatníme na uzel R.
2 Pokud uzel dělil scénu podle y-ové souřadnice, najdeme uzel R
obsahující bod s maximální y-ovou souøadnicí v levém
podstromu nebo s minimální y-ovou souřadnicí v pravém
podstromu, nalezený bod použijeme jako náhradu a stejný
postup uplatníme na uzel R.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 87 / 155 K-D strom
Příklad mazaní z 2D K-D stromu
F
A
D A
B
E
D B
F E
C
G C
G
H H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 88 / 155 K-D strom
Příklad mazaní z 2D K-D stromu
F
A
D A
B
E
D B
F E
C
G C
G
H H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 89 / 155 K-D strom
Příklad mazaní z 2D K-D stromu
F
D H
B
E
D B
F E
C
G C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 90 / 155 K-D strom
Příklad mazaní z 2D K-D stromu
F
D H
B
E
D B
F E
C
G C
G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 91 / 155 K-D strom
Příklad mazaní z 2D K-D stromu
F
D H
B
E
D B
F E
C
G C G
H
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 92 / 155 Hledání konvexní obálky
Hledání konvexní obálky
Definice
Nechť V je množina bodů nebo jiných objektů v rovině. Konvexní
obal (convex hull) je nejmenší konvexní objekt, který obsahuje
všechny body nebo objekty V.
Vstupem je množina bodů.
Výstupem je uspořádaný seznam (ve směru hodinových ručiček)
bodů,reprezentující konvexní obálku.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 93 / 155 Hledání konvexní obálky Grahamův algoritmus
Inkrementální Grahamův algoritmus hledání
konvexní obálky
1 Seřadíme množinu bodů dle x-ové souřadnice.
2 Nejprve nalezneme horní část konvexní obálky a to tak, že
postupně vkládáme do výstupního pole body ze vstupní množiny.
3 Testujeme, zda poslední tři body tvoří konvexní úhel. Pokud
poslední tři body netvoří konvexní úhel, je z výstupní množiny
odstraněn předposlední bod a test opakujeme
4 Obdobným způsobem nalezneme dolní část konvexní obálky.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 94 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 95 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 96 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 97 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 98 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 99 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 100 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 101 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 102 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 103 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 104 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 105 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 106 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 107 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 108 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 109 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 110 / 155 Hledání konvexní obálky Grahamův algoritmus
Grahamův algoritmus konstrukce konvexní obálky
pl
pr
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 111 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky algorimem Rozděl a Panuj
I
1 Body množiny se rozdělí na dvě stejně velké podmnožiny A a B
tak, že všechny body množiny B mají větší x-ovou
souřadnici,než bod z největší x-ovou souřadnicí z množiny A.
2 Rekurzivně je nalezena konvexní obálka obou množin A a B.
3 Konvexní obálky obálku nad oběma množinami A a B spojíme
nalezením horní a dolní tečny a odstraněním všech uzlů, které
jsou mezi těmito tečnami.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 112 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky algorimem Rozděl a Panuj
II
Nalezení horní tečny mezi konvexními obálkami:
1 Bod a je bod s největší x-ovou souřadnicí z konvexní obálky nad
množinou A.
2 Bod b je bod s nejmenší x-ovou souřadnicí z konvexní obálky
nad množinou B..
3 Dokud není ab horní tečnou prováděj
▶procházej seznam bodů reprezentující konvexní obálku z bodu a
proti směru hodinových ručiček, dokud není ab horní tečnou
konvexní obálky množiny A.
▶procházej seznam bodů reprezentující konvexní obálku z bodu b
po směru hodinových ručiček, dokud není ab horní tečnou
konvexní obálky množiny B.
Nalezení dolní tečny je obdobné.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 113 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 114 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 115 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 116 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 117 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 118 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 119 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 120 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 121 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 122 / 155 Hledání konvexní obálky Rozděl a panuj
Hledání konvexní obálky Rozdel a Panuj priklad
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 123 / 155 Zametací hyperrovina
Zametací hyperrovina
1 Vytvoření X-struktury - počáteční a koncové body úseček
seřazené podle x.
2 Vytvoření Y -struktury - seznam úseček v řezu zametací roviny
seřazené podle y (na začítku je prázdná)
3 Dokud není x-struktura prázdná prováděj:
▶Jdi na první bod x-struktury, pokud je počáteční, přidej přímku
do Y-struktury, pokud koncový odeber ji. Pokud průsečík přímky
prohoď.
▶Prozkoumej nově vzniklé sousedy v y-struktuře a urči
potenciální průsečíky na pravo od zametací přímky
▶odeber zpracovaný bod z x-struktury
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 124 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
9
G 13
10
1 A
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 125 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
9
G 13
10
1 A
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 126 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
9
G 13
10
1 A
P1
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 127 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
9
G 13
10
1 A
P1
P2
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 128 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
9
G 13
10
1 A
P1
P2
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 129 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
9
G 13
P3
10
1 A
P1
P2
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 130 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
P4 9
G 13
P3
10
1 A
P1
P2
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 131 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
P4 9
G 13
P3
10
1 A
P1
P2
3 C
E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 132 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
P4 9
G 13
P3
10
1 A
P1
P2
3 C
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 133 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
P4
9
G 13
P3
10
1 A
P1
P2
3 C
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 134 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
P4
9
G 13
P3
10
1 A
P1
P2
P6
3 C
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 135 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3
10
1 A
P1
P2
P6
3 C
E 14
P5 12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 136 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B 8
P4
P7 9
G 13
P3
10
1 A
P1
P2
P6
3 C
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 137 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P8
P3
10
1 A
P1
P2
P6
3 C
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 138 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P8
P3
10
1 A
P1
P2
P6
3 C
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 139 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P8
P3
10
1 A
P1
P2
P6
3 C P9
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 140 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P2
P6
3 C P9
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 141 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P2
P6
3 C P9
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 142 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P2
P6
3 C P9
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 143 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 144 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 145 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9 P12
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 146 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9 P12
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 147 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9 P12
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 148 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9 P12
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 149 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9 P12
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 150 / 155 Zametací hyperrovina
Zametací hyperrovina
4 D 6
F
2
B P4 P7 8
9
G 13
P3 P8
10
1 A
P1 P10 P11 P2
P6
3 C P9 P12
P5 E 14
12
7
5
11
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 151 / 155 Voroného diagram
Voroného diagram
Definice
Nechť V je množina bodů nebo jiných objektů v rovině. Voroného
buňka bodu p je množina všech bodů, které jsou k danému bodu
nejbližší. Z vodroného buněk je tvořen voroného diagram.
Vstupem je množina bodů.
Výstupem je souvislý graf dělící celý prostor na voroného buňky.
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 152 / 155 Voroného diagram
Voroného diagram
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 153 / 155 Voroného diagram
Voroného diagram
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 154 / 155 Voroného diagram
Co bychom po dnešku měli znát
Témata probraná na dnešní přednášce:
Kvadrantové stromy a jejich odvozeniny
Hledání konvexní obálky
Zametací hyperrovina
Chludil (FIT) BI-PGA, Přednáška č. 10 ZS 2024/2025 155 / 155