Geometrické modelování a výpočetní geometrie
Obsah
- 1 Rozsah látky
- 2 Projektivní rozšíření afinního prostoru, homogenní souřadnice, afinní a projektivní transformace v rovině a v prostoru
- 3 afinní a projektivní transformace v rovině a v prostoru
- 4 projektivní zobrazení =
- 5 Kvaterniony v reprezentaci 3D orientace
- 6 Diferenciální geometrie křivek a ploch
- 7 Základní spline funkce
- 8 Kubické spliny C2 a jejich vlastnosti, interpolace kubickými spliny
- 9 Bézierovy křivky
- 10 Catmull-Rom spliny
- 11 B-spline
- 12 De Casteljaův a de Boorův algoritmus
- 13 Aproximační plochy
- 14 plochy zadané okrajem
- 15 Bezierovy plochy
- 16 plátování
- 17 B-spline plochy
- 18 NURBS plochy
- 19 Základní věty o konvexitě, kombinatorická složitost konvexních mnohostěnů
- 20 Návrh geometrických algoritmů a jejich složitost
- 21 Voroného diagram a Delaunayova triangulace
- 22 Konvexní obal, lokalizace, datové struktury a algoritmy pro efektivní prostorové vyhledávání
- 23 Materiály
Rozsah látky
Seznam oficiálních státnicových otázek:
- Projektivní rozšíření afinního prostoru, homogenní souřadnice, afinní a projektivní transformace v rovině a v prostoru, kvaterniony v reprezentaci 3D orientace, diferenciální geometrie křivek a ploch, základní spline funkce, kubické spliny C2 a jejich vlastnosti, interpolace kubickými spliny, Bézierovy křivky, Catmull-Rom spliny, B-spline, de Casteljaův a de Boorův algoritmus, aproximační plochy, plochy zadané okrajem, Bezierovy plochy, plátování, B-spline plochy, NURBS plochy, základní věty o konvexitě, kombinatorická složitost konvexních mnohostěnů, návrh geometrických algoritmů a jejich složitost, Voroného diagram a Delaunayova triangulace, konvexní obal, lokalizace, datové struktury a algoritmy pro efektivní prostorové vyhledávání.
Projektivní rozšíření afinního prostoru, homogenní souřadnice, afinní a projektivní transformace v rovině a v prostoru
Projektivne rozsireny euklidovsky_prostor.pdf
Afinní prostor:
- $ A_n $ neprázdná množina bodů
- $ W_n $ - vektorový prostor (zaměření)
- $ f:A_n \times A_n \to W_n $
- $ f(A, B) + f(B,C) = f(A,C) $
- $ \forall P \in A_n, \forall X \in A_n : f_P(x) = f(P,X) $ je bijektivní
Běžně $ A_n = R^n, W_n = R^n, f(A,B) = B - A $.
Ekv. definice: Buď $ A $ neprázdná mnžožina nazývaná body, buď $ W $ vektorový prostor nad tělesem reálných čísel a dále mějme zobrazení $ f:A \times A \to W $ spl%nující
- pro každý bod $ a \in A $ a libovolný vektor $ u \in W $ existuje právě jedno $ b \in A $, pro které platí $ f(a,b) = u $
- pro každé tři body $ a, b, c $ platí, že $ f(a,b) + f(b,c) = f(a,c) $
Potom se $ (A, V, f) $ nazývá affiní prostor.
Soustava souřadnic
Repér: pevný bod $ O $ + báze zaměření
Transformace souřadnic
Lineárně nezávislé body
$ B_0,B_1, \ldots, B_n $ jsou LN $ \Leftrightarrow $ $ (B_1-B_0), (B_2-B_0), \ldots, (B_n-B_0) $ jsou LN
Afinní prostor dimenze n je jednoznačně určen n+1 body:
- $ X = B_0 + \sum \beta_i (B_i-B_0) = B_0+ \sum \beta_i B_i - \sum \beta_i B_0 = B_0 \underbrace{(1-\sum \beta_i)}_{\beta_0} + \sum \beta_i B_i $
Afinní kombinace bodů (barycentrické souřadnice) $ X = \beta_0 B_0 + \beta_1 B_1 + \ldots + \beta_n B_n $, $ \sum \beta_i = 1 $ Konvexní kombinace bodů - navíc požadavek $ \beta_i \geq 0, \forall i $
Homogenní souřadnice. Pelikán - Algebraická motivace - dokáží reprezentovat body v nekonečnu, průnik dvou přímek má vždy řešení.
Homogení na kartézské - unikátní, kartézské na homogení neunikátní.
Proč? Transformace lze vyjádřit pomocí jedné matice
afinní a projektivní transformace v rovině a v prostoru
Geometric transformation, Pelikán - transformace
Euklidovské transformace:
- otáčení - pozor, někde se může změnit znaménka u sinus, kvůli soustavě
- posunutí
Afinní transformace: Mohou se měnit délky a úhly (např. kružnice do elipsy).
- scale - změna měřítka
- shear - kosení ($ x' = x + a*y; y' = b*x + y $)
- obecná afinní transformace - matice s různými koeficienty, poslední řádek [0,0,0,1], obecně $ x' = a_{11}x + a_{12}y + a_{13}z + a_{14}w $ apod pro ostatní. Matice může být singulární, ale pak neexistuje inverzní transformace.
Kombinace transformací. Transformace aplikovány na jednotlivé body. Transformace nejsou komutativní.
projektivní zobrazení =
Nejobecnější, vyžaduje homogení souřadnice, transformační matice nemá v posledním řádku [0,0,0,1]. Matice musí být nesingulární (=má inverzní zobrazení). Projekce může dávat vlastní body do nevlastních (=nekonečno) když w'=0. Nejsou lineární (dělení novým w'), $ x' = (a_{11}x + a_{12}y + a_{13}z + a_{14}w) / (a_{41}x + a_{42}y + a_{43}z + a_{44}w) $
Kvaterniony v reprezentaci 3D orientace
- $ Q = q_0 + q_1 i + q_2 j + q_3 k = ( q_0, (q_1, q_2, q_3) ) = (q_0, \overrightarrow{q}) $
- $ i^2 = j^2 = k^2 = -1 $
- $ i j = k, j i = -k, \ldots $
Operace s kvaterniony
- $ Q \cdot P = (q_0, \overrightarrow{q}) (p_0, \overrightarrow{p}) = (q_0 p_0 - \overline{q} \overline{p}; q_0 \overline{p} + p_0 \overline{q} +(\overline{q} \times \overline{p}) $ - komutativní pokud shodné vektorové části, jinak pouze asociativní a distributivní
- $ Q^* = (q_0, - \overrightarrow{q}) $
- $ Q \cdot Q^* = (q_0^2 + \overline{q} \overline{q}; q_0 \overline{q} - q_0 \overline{q} + \overline{0}) = q_0^2 + q_1^2 + q_2^2 + q_3^2 $
- $ \| Q \| = \sqrt{Q \cdot Q^*} $
- $ Q \cdot Q^{-1} = 1 $
- $ Q^* \cdot Q \cdot Q^{-1} = 1 $
- $ Q^* \cdot Q \cdot Q^{-1} = Q^* $
- $ Q^{-1} = \frac{Q^*}{\| Q \|^2} $
- Věta: $ \| Q \cdot P \| = \| Q \| \cdot \| P \| $
- Dk: $ \| Q \cdot P \| = \sqrt{(Q \cdot P) \cdot (Q \cdot P)^*} = \sqrt{(Q \cdot P) \cdot (P^* \cdot Q^*)} = \sqrt{Q \cdot P \cdot P^* \cdot Q^*} = \sqrt{\| P \| Q \cdot Q^*} = \sqrt{\| P \|^2 \| Q \|^2} = \| Q \| \cdot \| P \| $
Jednotkové kvaterniony
- $ \| Q \| = 1 $
- tvoří multiplikativní podgrupu
- $ Q^{-1} = Q^* $
- Jednotkový kvaternion je tvaru: $ Q = ( cos( \alpha ), sin( \alpha ) \cdot \overline{a} ), \| \overline{a} \| = 1 $
Rotace
Mějme jednotkový kvaternion $ q=(\cos \alpha, \vec{n} \sin \alpha) $, $ \vec{n} $ je jednotkový vektor. Potom $ r = q r q^{*} $ je rotace $ r $ kolem osy $ n $ o úhel $ 2\alpha $ proti směru hodinových ručiček.
Pokud není kvaternion $ p $ jednotkový, lze jednoduše upravit na jednotkový. $ p r p^{-1} = p r \frac{p*}{||p||^2} = \frac{p}{|p|} r \frac{p^{*}}{|p|} = q r q^{*} $
Proč je to rotace: Rodrigezova formule dává stejný výsledek jako operace na kvaternionech
Složení dvou rotací je opět rotace: $ q_2 (q_1 r q_1^{*} ) q_2^{*} = (q_2 q_1) r (q_2 q_1)^{*} $
Interpolace rotace
- Lineární Eulerova interpolace
- Kvaterniony - LERP
- SLERP - sférická lineární interpolace
Diferenciální geometrie křivek a ploch
Šír - diferenciální geometrie křivek, Šír křivky, fjfi, Skripta
Křivky
- Parametrizovaná křivka v R^3: interval $ I=(\alpha, \beta) $ je hladké zobrazení (=na I má spojité derivace všech řádů) $ c: I \rightarrow R^3 $
- Vektor $ T = c'(t) $ se nazývá tečný vektor ke křivce c v bodě t.
- Křivka je regulární, pokud její derivace $ c'(t) \neq [0,0,0] $.
- Křivka je parametrizovaná obloukem, pokud $ |c'(t)|=1 $
- Každou regulární křivku lze parametrizovat obloukem
- Délka křivky: $ \int_{\alpha}^{\beta} |c'(t)| dt $
Příklady křivek: přímka, úsečka, kružnice, šroubovice,
Buď $ c(s) $ křivka parametrizovaná obloukem:
- pak křivost definujeme jako $ \kappa(s) = |c''(s)| = |T'(s)| $.
- bod, kde $ \kappa(s) = 0 $ nazýváme inflexní
- Mimo inflexní body definuji Frenetův repér jako tři vektory tečný ($ T(s) = c'(s) $), normálový ($ N(s) = \frac{T'(s)}{|T'(s)|} = \frac{T'(s)}{\kappa(s)} $) a binormálový vektor ($ B = T \times N $).
- Existuje jediná hladká fce $ \tau(s) $ nazývaná torze, tak, že
$ T' = \kappa N $, $ N' = -\kappa T + \tau B $, $ B' = -\tau N $
Definujeme několik rovin:
- $ c(s) + <T,N> $ oskulační rovina
- $ c(s) + <N,B> $ normálová rovina
- $ c(s) + <B,T> $ rektifikační rovina
Reparametrizace křivky: křivka $ \bar{c}(t) = c(s(t)) $ se nazývá reparametrizací parametrizované křivky $ c $.
Nejdříve vyjádříme fci $ s(t) $, která pro zadaný parametr t spočítá délku křivky až k bodu t: $ s(t) = \int_{t_a}^{t} |c'(k)| dk $. K ní uděláme inverzní fci $ t(s) $, která pro zadanou délku nám dá parametr, reparametrizovaná křivka $ c(t(s)) $ parametrizovaná obloukem.
Plochy
Šír - Diferenciální geometrie ploch
Plocha: hladké zobrazení z otevřené množiny R2 do R3.
Parametrická regulární plocha je hladké (jsou derivace všech supňů) regulární (první derivace nikde 0) zobrazení p z otevřené množiny O R2 do R3 takové, že vektory parciálních derivací jsou v každém bodě lineárně nezávislé. Množinu $ p(O) $ nazveme obrazem mapy. Pokud je p wcs:homeomorfismus, tak $ p(O) $ se nazývá mapa.
Řekneme, že vektor $ v \in R^3 $ je tečný vektor k ploše $ S $ v bodě $ s \in S $, pokud existuje křivka $ c $, $ <c> \subset S $ (c leží na S) taková, že $ c(t0) = s; c'(t0)=v $.
Je li p mapa na S, tak definuji normálový vektor jako $ N = \frac{p_u \times p_v}{|p_u \times p_v|} $ ($ p_u $, $ p_v $ jsou parciální derivace)
Základní spline funkce
wen:Spline (mathematics), wcs:Spline
Spline křivka stupně $ n $ je po částech polynomiální křivka, kde každý polynom má stupeň nejvýše $ n $. Jméno pocházi od pružného pravítka - křivítka. Požadujeme, aby polynomy sousedících částí měly stejné derivace až do $ n-1 $.
Spline je uniformní, pokud jsou všechny intervaly stejně veliké.
wen:Spline interpolation Přirozený spline je spline, který interpoluje své body, např. přirozený kubický spline je křivka, která je složená z polynomiálních oblouků stupně 3, patří do třídy C^2 (v řídících bodech ).
Máme n+1 bodů (0..n), n intervalů, použijeme přirozené kubiky spline. 4*n neznámých (kubka má 4 neznámé, n intervalů). Máme n+1 bodů x,y. Máme celkem 4n - 2 požadavků (každá kubika musí na začátku a na konci protínat bod + první a druhé derivace se musí v bodech rovnat), zbývají dva, které zvolíme jak chceme, např. druhé derivace koncových bodů = 0.
Kubické spliny C2 a jejich vlastnosti, interpolace kubickými spliny
Bézierovy křivky
wen:Bézier curve, wcs:Bézierova křivka
Křivka zadaná svým kontrolním polynomem, obvykle se používají kvadratiky (2 kontrolní body) nebo kubiky (3 kontrolní body)
$ C(t) = \sum_{i=0}^{n} B_{i,j} P_i $, kde Bernsteinovy polynomy $ B_{i,j}(t) = \binom{n}{i} t^i (1-t)^{n-i} $. T je 0..1
Široce používané, SVG, fonty.
Výpočet hodnoty buď pomocí rovnice nebo de Casteljau algoritmem.
Kreslení: obvykle adaptivní změna kroku, pokud přiliš malý/velký.
Vlastnosti:
- tečny v koncových bodech křivy jsou dané poslenímy body kontrolního polynomu
- invariantní vůči lineárním transformacím
- křivka uvnitř konvexní obálky kontrolního polynomu (součet všech Bersteinových polynomů = 1)
- prochází přesně koncovými body
- vliv bodu globální, změna neovlivňuje jenom malé okolí.
- hodograf (křivku derivace) lze spočítat jednoduše z bodů
- derivace v počátečním a koncovém bodu stejná, jako směr dvou prvních a posledních bodů
Rozdělení na 2 křivky
Subdividing a Bézier Curve. Používají se vnitřní body získané de Casteljau.
Racionální bézier: dáme každému bodu váhu, nemusíme měnit kontrolní polygon pro změnu.
$ \mathbf{B}(t) = \frac{ \sum_{i=0}^n B_{i,n}(t) \mathbf{P}_{i}w_i } { \sum_{i=0}^n B_{i,n}(t) w_i } $
V normální Bézierovce je všude váha 1 a proto je suma jmenovatele 1.
Catmull-Rom spliny
Kubické spliny zadané posloupností $ n+1 $ bodů $ P_0, P_1,...P_n $. Křivka neprochází všemi body, vynechává první ($ P_0 $) a poslední ($ P_n $). Pokud uživatel chce, aby jimi procházela, je potřeba zadat první a poslední dvojnásobně. Používají se pro interpolaci animaci mezi klíčovými snímky.
Vlasnost tečny:
- tečna v bodě $ P_i $ je rovnoběžná s přimkou $ P_{i-1} P_{i+1} $.
- nejsou v konvexním obalu kontrolních bodů.
Výpočet na každém intervalu je snadný (známe lokace počátečního a koncového bodu a víme derivace [viz podmínka]) -> lze velmi snadno spočítat Catmul-Rom pro interval [P_i, P_{i+1}] pomocí bodů [P_{i-1}, P_{i}, P_{i+1}, P_{i+2}] (dají hodnoty i derivace).
B-spline
Základní fce $ N_{i,p} $ jsou definovány podle p.
Pro $ p=0 $ platí $ N_{i,0}(u) = \left\{\begin{matrix} 1 & \mathbf{if} \ u_i < u < u_{i+1}\\ 0 & \mathbf{jinak}\end{matrix}\right. $
Pro $ p \neq 0 $ platí $ N_{i,p}(u) = \frac{u-u_i}{u_{i+p}-u_i}N_{i,p-1}(u) +\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u) $.
B spline křivka stupně p je definovaná jako $ C(u) = \sum_{i=0}^{n} N_{i,p} P_i $. Máme n+1 bodů, m+1 uzlů a stupeň základních fcí p. Musí platit m = n + p + 1
Křivky nezačínají v počátečních souřadnicích. Pokud chceme, musíme dát počátečnímu/koncovému uzlu násobnost p+1.
Lokální, bod $ N_{i,p} $ je nenulové pouze na $ u_i, u_{i+p+1} $
- Uzavřená v konvexním obalu bodů (základní fce dávají dohromady 1)
- Lokální modifikace: změna pozice bodu $ P_i $ ovlivní pouze úseky $ [u_i, u_{i+p+1}) $
- uvnitř segmentů uzlového vektoru hladká, v uzlech je $ C^{p-k} $ spojitá, kde $ k $ je násobnost uzlu
- béziér je speciálním případem B spline.
- invariantní k afinním transformacím
Výhody - narozdíl od Béziera jsme oddělili stupeň křivky od počtu kontrolních bodů. Díky tomu můžeme mít velké množství kontrolních bodů a přesto mít jednoduchý výpočet.
Modifikace uzlu - změní se mapování úseku a fce => změna tvaru. Změna není moc predikovatelná.
De Casteljaův a de Boorův algoritmus
De Casteljaův algoritmus
Algoritmus pro nalezení bodu na bézierově křivce.
Více numericky stabilní než přímé vyhodnocení Béziera. Založeno na Bernštejnově polynomu:
$ B_{i,n}(t) = (1-t) \cdot B_{i,n-1}(t) + t \cdot B_{i-1,n-1}(t) $,
Proč je alg. korektní - spočítá se, jaký je celkový příspěvek každého přes všechny cesty, je to rovné bersteionovu polynomu.
de Boorův algoritmus
Chceme, aby v uzlovém vektoru měl hledaný bod násobnost p. Pak bude jen jedna nenulová základí fce ($ N_{i,0} $) a díky pyramidálnímu výpočtu bude křivka v daném bodě rovna kontrolnímu bodu.
Podíváme se, jakou má hledan= $ t $ násobnost a podle toho musím vložit $ t $ do uzlového vektoru.
- najdi interval v uzlovém vektoru, kam $ t $ patří ($ u_i, u_{i+1} $ - $ N_{i,0} $).
- Je potřeba přidat nový bod (aby m=n+p+1 stále platilo i po přidání $ t $)
- Najdi všechny body, které ovlivňuje $ N_{i,0} $ (je vidět z pyramidy), jsou to $ P_{i-p}...P_{i} $ .
- Vytvoř nové body Q, $ Q_i = (1-a_i)P_{i-1} + a_i P_{i} $, $ a_i = \frac{t-u_i}{u_{i+p} - u_i} $
- Nahraď vnitřní body $ P_{i-p}...P_{i} $ (= ne body $ P_{i-p} $ a $ P_i $) body $ Q_i $. Přidej do uzlového vektoru $ t $
Aproximační plochy
Aproximační plochy = plochy zadané body. Plochy modelujeme pomocí zadávání sítě řídících bodů v 3D. Obvykle se paroximuje po částech.
Pozor na rozdíl:
- interpolační - plocha prochází body
- aproximační - ploha používá body k určení svého tvaru
Zajímá nás napojení, bázové funkce jsou polynomy, protože snadno diferencovatelné. Reprezetn
plochy zadané okrajem
wen:Coons surface - Bilineární a bikubická Coonsova plocha, Coons patch & Bicubic patch
Coonsova plocha
Coonsova plocha používá křivky, nikoliv body k interpolaci povrchu. Máme zadané křivky okrajů, $ P_0(v) $ (levý okraj) $ P_1(v) $ (pravý okraj), $ Q_0(u) $ (dolní okraj) a $ Q_1(u) $ (horní okraj), stýkají se v rozích a hranice od 0-1.
Horizontální lineární interpolace mezi P nekopíruje hranice Q. Obdobně vertikální lineární interpolace mezi Q nekopíruje hranice P.
Co zkusit lineálně interpolovat obě najednou: $ C(u,v) = (1-u)P_0(v) + u P_1(v) + (1-v) Q_0(u) + v Q_1(u) $? Problém - na hranicích to přirozeně nefunguje, protože v podstatě interpolujeme 2 body a pak je sečteme. Co se stane na okrajích:
- $ C(0,v) = P_0(v) + \underline{(1-v) Q_0(0) + v Q_1(0)} $, ale má být $ C(0,v) = P_0(v) $
- $ C(1,v) = P_1(v) + \underline{(1-v) Q_0(1) + v Q_1(1)} $, ale má být $ C(1,v) = P_1(v) $
- $ C(u,0) = Q_0(u) + \underline{(1-u) P_0(0) + u P_1(0)} $, ale má být $ C(u,0) = Q_0(u) $
- $ C(u,1) = Q_1(u) + \underline{(1-u) P_0(1) + u P_1(1)} $, ale má být $ C(u,1) = Q_1(u) $
Od $ C(u,v) = (1-u)P_0(v) + u P_1(v) + (1-v) Q_0(u) + v Q_1(u) $ odečteme přebytečné členy (ty podtržené). To už hranice následuje.
Výhody
- Jednoduché na implementaci
- následují okrajové křivky
Nevýhody: nemůžeme kontrolovat vnitřní tvar plochy
Bezierovy plochy
Zobecnění křivek: $ C(u,j) = \sum_{i=0}^{n} \sum_{j=0}^{m} P_{i,j} B_{i,n}(u) B_{j,m}(v) $; $ u,v \in <0,1> $
Výpočet: vnitřní suma je bézierovka-> de casteljau a pak vnější suma, znovu de Casteljau. Případně přímo.
Vlastnosti:
- Lineární transformace nezmění plát.
- Plocha zahrnuje rohové body (P_{0,0}, P_{n,0}, P_{0,m} a P_{n,m})(dosadut do rovnice)
- hranice jsou Bézierovy křivky (dosadit).
- Plocha je uvnitř konvexního obalu
Obvykle se používají bikubiky (n=m=3)
plátování
Žára, Moderní Poč. Grafika, str. 160
Převedení Bézierovy plochy (zejména bikubit) na trojúhelníkovou síť.
Algoritmus: Pokud síť dost rovná, skonči. Jinak vezmeme síť, rozdělíme všechny křivky řídících polynomů pomocí de Casteljau na 2 v t=1/2. Pak totéž ve vertikálním směru pro každou polovinu.
Adaptivní - pokud bychom automaticky dělili všechny 4 plochy, není o nic lepší, než spočítat přímo. Plochyu před rozdělením ohodnotíme, zda není dost rovná (např. kvadrát vzdálenosti od roviny 3 okrajů).
Cracking problém - 2 sousedící pláty, 1 se rozdělí, druhý ne. Hranice rozděleného již není přímka (=je to více přímek) a máme prasklinu.
B-spline plochy
Máme uzlový vektor v horizontální u, pro vertikální v. $ C(u,v) = \sum_{i=0}^{n} \sum_{j=0}^{m} P_{i,j} N_{i,p}(u) N_{j,q}(v) $.
Pozor, stále musí platit, že počet prvků v uzlovém vektoru musí být stupeň křivky v tom směru + počet bodů v tom směru + 1. Taktéž pokud se má dotýkat okrajových bodů, násobnost musí být stupeň + 1 (i.e. $ p+1 $ nebo $ q+1 $)
Vykreslení: dvojitý de Boorův algoritmus, $ C(u,v) = \sum_{i=0}^{n} \sum_{j=0}^{m} P_{i,j} N_{i,p}(u) N_{j,q}(v) = \sum_{i=0}^{n} N_{i,p}(u) (\sum_{j=0}^{m} P_{i,j} N_{j,q}(v) ) $. Není potřeba transformovat všechny body (lokálnost).
NURBS plochy
Invariantní vůči perspektivní projekci, ta je náročná na prostředky, ale u NURBS mi stačí perspektivně transformovat body a pak ji zobrazit.
Umí zobrazovat komplikované plochy, kuželosešky, válec atd. Díky tomu ve všech alg. stačí implementovat NURBS a máme všechno ostatní (např. sledování paprsku - místo X různých objektů se pracuje s jedním typem).
Vzorec $ C(u,j) = \frac{ \sum_{i=0}^{n} \sum_{j=0}^{m} w_{i,j} P_{i,j} N_{i,p}(u) N_{j,q}(v) }{\sum_{i=0}^{n} \sum_{j=0}^{m} w_{i,j} N_{i,p}(u) N_{j,q}(v)} $.
NURBS používají homogení souřadnice - vložení nového uzlu je přes vynásobení váhovou funkcí, takže máme o dimenzi víc, tam provedeme vložení a vrátíme do 3D. Dtto de Boor.
Základní věty o konvexitě, kombinatorická složitost konvexních mnohostěnů
Konvexní kombinace dvou vektorů $ \vec{x}, \vec{y} \in R^n $ rozumíme každý vektor ve tvaru $ \alpha\vec{x} + (1-\alpha)\vec{y}, \alpha\in <0,1> $
Množina $ X \subseteq R^n $ je konvexní, pokud pro každé dva prvky $ \vec{x},\vec{y} \in X $ jsou i všechny jejich konvexní kombinace prvky X.
Věta: Průnik $ X \cap Y $ je konvexní množina. Dk: Pro každé x,y z průniku platí, že všechny jejich kombinace patří do X i Y, což je definice.
Definice: Nechť $ K $ je konvexní množina. Bod $ v \in K $ je krajním bodem $ K $, pokud neexistují body $ x, y \in K \setminus v $ takové, že v by bylo konvexní kombinací $ x $ a $ y $.
Věta o oddělující nadrovině: Máme $ X \subseteq R^n $ uzavřenou konvexní množinu. Dále máme $ \vec{z} \not\in X, \vec{z} \in R^n $. Pak existuje nadrovina oddělující $ \vec{z} $ od $ X $.
Návrh geometrických algoritmů a jejich složitost
Voroného diagram a Delaunayova triangulace
Voronoi diagramy,wen:Voronoi diagram
Máme množinu bodů a VD rozděluje rovinu na oblasti, kde každý bod je součátí oblasti nejbližšího bodu. VD je hranice mezi oblastmi (=body, které jsou stejně vzdálené k více bodům).
Vlastnosti:
- konvexní
- v každé oblasti 1 bod
- některé oblasti neuzavřené
- pokud žádné 4 body neleží na kružnici, uzly mají stupeň 3
- je-li p_i nejbližší soused p_j, tak jejich oblasti sdílí hranu
Konstrukce:
- wen:Fortune's algorithm - má sweep line, která jde zleva doprava a beachline (sjednocení parabol - parabola = stejná vzdálenost od přímky a bodu). beachline mapuje VD, když SL přijde nový bod tak nová parabola v beachline, pokud se ruší křivka (pokud se tři body, které tvoří tři sousední paraboly na beachline jsou v kruhu, který se dotýká sweep line = bod má stejnou vzdálen ost ke všem třem bodům)
Delaunayova triangulace
Rovinne triangulace a jejich aplikace,wen:Delaunay triangulation
Triangulace N bodů množiny P - rozdělení ConvexHull(N) do simplexů (simplex v dimenzi k má k+1 bodů=ve 2D trojúhelník). Počet hran v E2 (euklid2D) max 3N-6, přesně 3N-3-N_convex_hull
Kritéria - lze vybrat mnoho triangulačních sítí, kterou?:
- Co nejrovnostranější trojúhelníky - úhlová kritéria: maximalizace min. úhlů, mainimalizace max. úhlů. Hranová kritéria: Co nejkratší součet délek hran.
- občas např. chceme zachovat nekonvexnost oblasti (např. písmena)
- začlenění některých povinných hran
- kružnice opsaná libovolnému trojúhelníku DT(P) v sobě neobsahuje žádné další body z P. Ze všech triangulací má trojúhelníky nejblíže k rovnostranným. Duální k voroniho diagramu
- pokud nejsou tři na čáře apod, tak je triangulace unikátní.
Flipping: pokud máme dva trojúhelníky, které sousedí hranou a které nejsou DT (=opsané kružnice obsahují další vrchol nebo úhly > 180), přehození hrany to změní. Začne se s libovolnou triangulací a poté se přehazují hrany, které nejsou DT.
Konvexní obal, lokalizace, datové struktury a algoritmy pro efektivní prostorové vyhledávání
Pozor na degenerované případy, např. více bodů na přímce
2D
- Grahamův algoritmus - najdi bod s nejmenším y (pokud víc, nejpravější), seřaď body podle úhlu s bodem p a osou x, potom v pořadí testuj, jestli je to stále konvexní, pokud se otáčí opačným směrem, odstraň předcházející body, dokud není zase konvexní. Nejde zobecnit do vyšších dimenzí. O(N log N)
- Balení dárku - vybere se nejlevější bod (zaručeně v obalu). Opakuj: najdi další bod obalu tak, že se podívá na všechny body a vybere ten s nejmenším úhelm od současného úhlu. Složitost (počet_bodu_obalu * N). Pomalý (až N^2), nepoužívá se.
- Rozděl a panuj - pokud málo bodů, zkonstruuj obal, jinak rozděl na 2 poloviny, pro každou rekurzivně vlastní obal a výsledné obaly spoj. Pokud spojení O(N), tak O(N log N)
3D
- Balení dárku - máme stěnu F a hledáme přes její hranu e polorovinu, která má největší úhel < 180. O(počet_stěn*N)
- Rozděl a panuj. Pokud spojení O(N), tak O(N log N)
Lokalizace
Lokalizace - hledání bodu. Geometricke vyhledavani
Konvexní polygon
- Ray crossing, vodorovná přímka procházející bodem, pokud lichý počet průsečíků, uvnitř, jinak venku
- Test vůči každé hraně - každá hrana definuje polorovinu, pokud ve všech, tak uvnitř
- Půlení intervalu
Nekonvexní polygon
- Ray crossing
- Ovíjení - jdu postupně po všech bodech a sčítám úhly P_i - bod - P_i+1. Pokud je uvitř, tak obejde celý polygon a vysledek je 360, pokud venku, tak se vrátí a výsledek 0.
Hledání v síti
- Planární dělení - Každý separátor dělí rovinu na 2 částí=lze použít binární vyledávání. Něco jako BSP
- Metoda pásů - vezmemem všechny body a seřadíme do pásů podle x (lze vyhledávat binárně), v každém pásu všechny přimky, seřazené posle y. Hledání O(log N)
datové struktury a algoritmy pro efektivní prostorové vyhledávání
Geometricke vyhledavani 2 Datové struktury pro prostorové vyhledávání
- octree
- k-D tree
- range tree - strom podle x a v každé node strom podle y prvků, které spadají pad danou node
- BSP tree
- R-tree - v listech obálky, vnitřní uzly obálky podstromů
Materiály
- …