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:

  • <math>A_n</math> neprázdná množina bodů

  • <math>W_n</math> - vektorový prostor (zaměření)

  • <math>f:A_n \times A_n \to W_n</math>

  • <math>f(A, B) + f(B,C) = f(A,C)</math>

  • <math>\forall P \in A_n, \forall X \in A_n : f_P(x) = f(P,X)</math> je bijektivní

Běžně <math>A_n = R^n, W_n = R^n, f(A,B) = B - A</math>.

Ekv. definice: Buď <math>A</math> neprázdná mnžožina nazývaná body, buď <math>W</math> vektorový prostor nad tělesem reálných čísel a dále mějme zobrazení <math>f:A \times A \to W</math> spl%nující

  • pro každý bod <math>a \in A</math> a libovolný vektor <math>u \in W</math> existuje právě jedno <math>b \in A</math>, pro které platí <math>f(a,b) = u</math>

  • pro každé tři body <math>a, b, c</math> platí, že <math>f(a,b) + f(b,c) = f(a,c)</math>

Potom se <math>(A, V, f)</math> nazývá affiní prostor.

Soustava souřadnic

Repér: pevný bod <math>O</math> + báze zaměření

Transformace souřadnic

Lineárně nezávislé body

<math>B_0,B_1, \ldots, B_n</math> jsou LN <math>\Leftrightarrow</math> <math>(B_1-B_0), (B_2-B_0), \ldots, (B_n-B_0)</math> jsou LN

Afinní prostor dimenze n je jednoznačně určen n+1 body:

<math>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</math>

Afinní kombinace bodů (barycentrické souřadnice)

<math>X = \beta_0 B_0 + \beta_1 B_1 + \ldots + \beta_n B_n</math>, <math>\sum \beta_i = 1</math> Konvexní kombinace bodů - navíc požadavek <math>\beta_i \geq 0, \forall i</math>

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í (<math>x' = x + a*y; y' = b*x + y</math>)

  • obecná afinní transformace - matice s různými koeficienty, poslední řádek [0,0,0,1], obecně <math>x' = a_{11}x + a_{12}y + a_{13}z + a_{14}w</math> 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'), <math>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)</math>

Kvaterniony v reprezentaci 3D orientace

  • <math>Q = q_0 + q_1 i + q_2 j + q_3 k = ( q_0, (q_1, q_2, q_3) ) = (q_0, \overrightarrow{q})</math>

  • <math>i^2 = j^2 = k^2 = -1</math>

  • <math>i j = k, j i = -k, \ldots</math>

Operace s kvaterniony

  • <math>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})</math> - komutativní pokud shodné vektorové části, jinak pouze asociativní a distributivní

  • <math>Q^* = (q_0, - \overrightarrow{q})</math>

  • <math>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</math>

  • <math>\| Q \| = \sqrt{Q \cdot Q^*}</math>

  • <math>Q \cdot Q^{-1} = 1 </math>

<math>Q^* \cdot Q \cdot Q^{-1} = 1 </math>

<math>Q^* \cdot Q \cdot Q^{-1} = Q^* </math>

<math>Q^{-1} = \frac{Q^*}{\| Q \|^2}</math>

  • Věta: <math>\| Q \cdot P \| = \| Q \| \cdot \| P \|</math>

    Dk: <math>\| 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 \|</math>

Jednotkové kvaterniony

  • <math>\| Q \| = 1</math>

  • tvoří multiplikativní podgrupu

  • <math>Q^{-1} = Q^*</math>

  • Jednotkový kvaternion je tvaru: <math>Q = ( cos( \alpha ), sin( \alpha ) \cdot \overline{a} ), \| \overline{a} \| = 1</math>

Rotace

Šír prezentace

Mějme jednotkový kvaternion <math>q=(\cos \alpha, \vec{n} \sin \alpha)</math>, <math>\vec{n}</math> je jednotkový vektor. Potom <math>r = q r q^{*}</math> je rotace <math>r</math> kolem osy <math>n</math> o úhel <math>2\alpha</math> proti směru hodinových ručiček.

Pokud není kvaternion <math>p</math> jednotkový, lze jednoduše upravit na jednotkový. <math>p r p^{-1} = p r \frac{p*}{||p||^2} = \frac{p}{|p|} r \frac{p^{*}}{|p|} = q r q^{*}</math>

Proč je to rotace: Rodrigezova formule dává stejný výsledek jako operace na kvaternionech

Složení dvou rotací je opět rotace: <math>q_2 (q_1 r q_1^{*} ) q_2^{*} = (q_2 q_1) r (q_2 q_1)^{*}</math>

Interpolace rotace

  1. Lineární Eulerova interpolace

  2. Kvaterniony - LERP

  3. 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 <math>I=(\alpha, \beta)</math> je hladké zobrazení (=na I má spojité derivace všech řádů) <math>c: I \rightarrow R^3</math>

  • Vektor <math>T = c'(t)</math> se nazývá tečný vektor ke křivce c v bodě t.

  • Křivka je regulární, pokud její derivace <math>c'(t) \neq [0,0,0]</math>.

  • Křivka je parametrizovaná obloukem, pokud <math>|c'(t)|=1</math>

  • Každou regulární křivku lze parametrizovat obloukem

  • Délka křivky: <math>\int_{\alpha}^{\beta} |c'(t)| dt</math>

Příklady křivek: přímka, úsečka, kružnice, šroubovice,

Buď <math>c(s)</math> křivka parametrizovaná obloukem:

  • pak křivost definujeme jako <math>\kappa(s) = |c(s)| = |T'(s)|</math>.

  • bod, kde <math>\kappa(s) = 0</math> nazýváme inflexní

  • Mimo inflexní body definuji Frenetův repér jako tři vektory tečný (<math>T(s) = c'(s)</math>), normálový (<math>N(s) = \frac{T'(s)}{|T'(s)|} = \frac{T'(s)}{\kappa(s)}</math>) a binormálový vektor (<math>B = T \times N</math>).

  • Existuje jediná hladká fce <math>\tau(s)</math> nazývaná torze, tak, že

<math>T' = \kappa N</math>, <math>N' = -\kappa T + \tau B</math>, <math>B' = -\tau N</math>

Definujeme několik rovin:

  • <math>c(s) + <T,N></math> oskulační rovina

  • <math>c(s) + <N,B></math> normálová rovina

  • <math>c(s) + <B,T></math> rektifikační rovina

Reparametrizace křivky: křivka <math>\bar{c}(t) = c(s(t))</math> se nazývá reparametrizací parametrizované křivky <math>c</math>.

Nejdříve vyjádříme fci <math>s(t)</math>, která pro zadaný parametr t spočítá délku křivky až k bodu t: <math>s(t) = \int_{t_a}^{t} |c'(k)| dk</math>. K ní uděláme inverzní fci <math>t(s)</math>, která pro zadanou délku nám dá parametr, reparametrizovaná křivka <math>c(t(s))</math> 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 <math>p(O)</math> nazveme obrazem mapy. Pokud je p wcs:homeomorfismus, tak <math>p(O)</math> se nazývá mapa.

Řekneme, že vektor <math>v \in R^3</math> je tečný vektor k ploše <math>S</math> v bodě <math>s \in S</math>, pokud existuje křivka <math>c</math>, <math><c> \subset S</math> (c leží na S) taková, že <math>c(t0) = s; c'(t0)=v</math>.

Je li p mapa na S, tak definuji normálový vektor jako <math>N = \frac{p_u \times p_v}{|p_u \times p_v|}</math> (<math>p_u</math>, <math>p_v</math> jsou parciální derivace)

Základní spline funkce

wen:Spline (mathematics), wcs:Spline

Spline křivka stupně <math>n</math> je po částech polynomiální křivka, kde každý polynom má stupeň nejvýše <math>n</math>. 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 <math>n-1</math>.

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

Interpolace kubickými splajny

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)

<math>C(t) = \sum_{i=0}^{n} B_{i,j} P_i</math>, kde Bernsteinovy polynomy <math>B_{i,j}(t) = \binom{n}{i} t^i (1-t)^{n-i}</math>. 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.

<math> \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 }

</math>

V normální Bézierovce je všude váha 1 a proto je suma jmenovatele 1.

Catmull-Rom spliny

Kubické spliny zadané posloupností <math>n+1</math> bodů <math>P_0, P_1,...P_n</math>. Křivka neprochází všemi body, vynechává první (<math>P_0</math>) a poslední (<math>P_n</math>). 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ě <math>P_i</math> je rovnoběžná s přimkou <math>P_{i-1} P_{i+1}</math>.

  • 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 <math>N_{i,p}</math> jsou definovány podle p.

Pro <math>p=0</math> platí <math>N_{i,0}(u) = \left\{\begin{matrix} 1 & \mathbf{if} \ u_i <u < u_{i+1}\\ 0 & \mathbf{jinak}\end{matrix}\right.</math>

Pro <math>p \neq 0</math> platí <math>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)</math>.

B spline křivka stupně p je definovaná jako <math>C(u) = \sum_{i=0}^{n} N_{i,p} P_i</math>. 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 <math>N_{i,p}</math> je nenulové pouze na <math>u_i, u_{i+p+1}</math>

  • Uzavřená v konvexním obalu bodů (základní fce dávají dohromady 1)

  • Lokální modifikace: změna pozice bodu <math>P_i</math> ovlivní pouze úseky <math>[u_i, u_{i+p+1})</math>

  • uvnitř segmentů uzlového vektoru hladká, v uzlech je <math>C^{p-k}</math> spojitá, kde <math>k</math> 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

wen:De Casteljau's algorithm

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:

<math>B_{i,n}(t) = (1-t) \cdot B_{i,n-1}(t) + t \cdot B_{i-1,n-1}(t)</math>,

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

wen:De Boor's algorithm

Chceme, aby v uzlovém vektoru měl hledaný bod násobnost p. Pak bude jen jedna nenulová základí fce (<math>N_{i,0}</math>) 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= <math>t</math> násobnost a podle toho musím vložit <math>t</math> do uzlového vektoru.

Jak vložit uzel?

  • najdi interval v uzlovém vektoru, kam <math>t</math> patří (<math>u_i, u_{i+1}</math> - <math>N_{i,0}</math>).

  • Je potřeba přidat nový bod (aby m=n+p+1 stále platilo i po přidání <math>t</math>)

  • Najdi všechny body, které ovlivňuje <math>N_{i,0}</math> (je vidět z pyramidy), jsou to <math>P_{i-p}...P_{i}</math> .

  • Vytvoř nové body Q, <math>Q_i = (1-a_i)P_{i-1} + a_i P_{i}</math>, <math>a_i = \frac{t-u_i}{u_{i+p} - u_i}</math>

  • Nahraď vnitřní body <math>P_{i-p}...P_{i}</math> (= ne body <math>P_{i-p}</math> a <math>P_i</math>) body <math>Q_i</math>. Přidej do uzlového vektoru <math>t</math>

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ů, <math>P_0(v)</math> (levý okraj) <math>P_1(v)</math> (pravý okraj), <math>Q_0(u)</math> (dolní okraj) a <math>Q_1(u)</math> (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: <math>C(u,v) = (1-u)P_0(v) + u P_1(v) + (1-v) Q_0(u) + v Q_1(u)</math>? 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:

  • <math>C(0,v) = P_0(v) + \underline{(1-v) Q_0(0) + v Q_1(0)}</math>, ale má být <math>C(0,v) = P_0(v)</math>

  • <math>C(1,v) = P_1(v) + \underline{(1-v) Q_0(1) + v Q_1(1)}</math>, ale má být <math>C(1,v) = P_1(v)</math>

  • <math>C(u,0) = Q_0(u) + \underline{(1-u) P_0(0) + u P_1(0)}</math>, ale má být <math>C(u,0) = Q_0(u)</math>

  • <math>C(u,1) = Q_1(u) + \underline{(1-u) P_0(1) + u P_1(1)}</math>, ale má být <math>C(u,1) = Q_1(u)</math>

Od <math>C(u,v) = (1-u)P_0(v) + u P_1(v) + (1-v) Q_0(u) + v Q_1(u)</math> 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: <math>C(u,j) = \sum_{i=0}^{n} \sum_{j=0}^{m} P_{i,j} B_{i,n}(u) B_{j,m}(v)</math>; <math>u,v \in <0,1></math>

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

Konstrukce

Máme uzlový vektor v horizontální u, pro vertikální v.

<math>C(u,v) = \sum_{i=0}^{n} \sum_{j=0}^{m} P_{i,j} N_{i,p}(u) N_{j,q}(v)</math>.

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. <math>p+1</math> nebo <math>q+1</math>)

Vykreslení: dvojitý de Boorův algoritmus, <math>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) )</math>. 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 <math>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)}</math>.

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ů

~hlineny/Teaching/OU/OU-text07.pdf

Konvexní kombinace dvou vektorů <math>\vec{x}, \vec{y} \in R^n</math> rozumíme každý vektor ve tvaru <math>\alpha\vec{x} + (1-\alpha)\vec{y}, \alpha\in <0,1></math>

Množina <math>X \subseteq R^n</math> je konvexní, pokud pro každé dva prvky <math>\vec{x},\vec{y} \in X</math> jsou i všechny jejich konvexní kombinace prvky X.

Věta: Průnik <math>X \cap Y</math> 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ť <math>K</math> je konvexní množina. Bod <math>v \in K</math> je krajním bodem <math>K</math>, pokud neexistují body <math>x, y \in K \setminus v</math> takové, že v by bylo konvexní kombinací <math>x</math> a <math>y</math>.

Věta o oddělující nadrovině: Máme <math>X \subseteq R^n</math> uzavřenou konvexní množinu. Dále máme <math>\vec{z} \not\in X, \vec{z} \in R^n</math>. Pak existuje nadrovina oddělující <math>\vec{z}</math> od <math>X</math>.

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í

Konvexní obal

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

{{Stub}} Category: Státnice Informatika Mgr.