== Rozsah látky ==
Seznam [http://www.mff.cuni.cz/studium/bcmgr/ok/i3b52.htm 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 ==
[http://skola.brundik.net/szz-ma/materialy/geometrie/Geo-10_-_Projektivne_rozsireny_euklidovsky_prostor.pdf 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>.
'''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>
== 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 ===
[http://www.karlin.mff.cuni.cz/~sir/soubory/Kvaterniony.pdf Ší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>\frac{\alpha}{2}</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} = q r </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 ===
# Lineární Eulerova interpolace
# Kvaterniony - LERP
# SLERP - sférická lineární interpolace
== Diferenciální geometrie křivek a ploch==
[http://www.karlin.mff.cuni.cz/~sir/modelovani/DGkrivek.pdf Šír - diferenciální geometrie křivek], [http://www.karlin.mff.cuni.cz/~sir/soubory/seznam.pdf Šír křivky], [http://www.fd.cvut.cz/department/k611/PEDAGOG/files/webskriptum/DG_krivky/ fjfi], [http://www.karlin.mff.cuni.cz/~soucek/kpl_11_2012.pdf 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>.
=== Plochy ===
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.
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> (p_u, p_v 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. Důvodem pro polynomy je, aby ve vnitřních bodech křivky byly spojité derivace stupně až 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ř. derivace vna začátku a na konci.
== 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)
<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í.
Ractioná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 0.
== Catmull-Rom spliny==
== B-spline==
== 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>,
[[http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau-correct.html 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]]
== 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 ==
[http://iason.zcu.cz/~kolinger/AVG/AVG5.zip 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 = bod má stejnou vzdálen ost ke všem třem bodům)
=== Delaunayova triangulace ===
[http://iason.zcu.cz/~kolinger/AVG/AVG7.zip 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 2N-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í ==
[http://iason.zcu.cz/~kolinger/AVG/AVG4.zip Konvexní obal]
Pozor na degenerované případy, např. více bodů na přímce
=== 2D ===
* [https://en.wikipedia.org/wiki/Graham_scan 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)
* [https://en.wikipedia.org/wiki/Gift_wrapping_algorithm 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. [http://iason.zcu.cz/~kolinger/AVG/AVG2.zip 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í ===
[http://iason.zcu.cz/~kolinger/AVG/AVG3.zip Geometricke vyhledavani 2]
[http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-06-datasurvey.pdf 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.]]
