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,\dots ,B_n$ jsou LN $\iff$ $(B_1-B_0),(B_2-B_0),\dots ,(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\underset{{\beta }_0}{(1-\sum {\beta }_i)}+\sum {\beta }_i{B}_i$

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

$X={\beta }_0{B}_0+{\beta }_1{B}_1+\dots +{\beta }_n{B}_n$, $\sum {\beta }_i=1$ Konvexní kombinace bodů - navíc požadavek ${\beta }_i\ge 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^{\prime }=x+a\ast y;y^{\prime }=b\ast x+y$)

• obecná afinní transformace - matice s různými koeficienty, poslední řádek [0,0,0,1], obecně $x^{\prime }=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^{\prime }=(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,q)$

• $i^2=j^2=k^2=-1$

• $ij=k,ji=-k,\dots$

Operace s kvaterniony

• $Q\cdot P=(q_0,q)(p_0,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^{\ast }=(q_0,-q)$

• $Q\cdot Q^{\ast }=(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$

• $\Vert Q\Vert =\sqrt{Q\cdot Q^{\ast }}$

• $Q\cdot Q^{-1}=1$

:: $Q^{\ast }\cdot Q\cdot Q^{-1}=1$ :: $Q^{\ast }\cdot Q\cdot Q^{-1}=Q^{\ast }$ :: $Q^{-1}=\frac{Q^{\ast }}{\Vert Q{\Vert }^2}$

• Věta: $\Vert Q\cdot P\Vert =\Vert Q\Vert \cdot \Vert P\Vert$ :: Dk: $\Vert Q\cdot P\Vert =\sqrt{(Q\cdot P)\cdot (Q\cdot P{)}^{\ast }}=\sqrt{(Q\cdot P)\cdot (P^{\ast }\cdot Q^{\ast })}=\sqrt{Q\cdot P\cdot P^{\ast }\cdot Q^{\ast }}=\sqrt{\Vert P\Vert Q\cdot Q^{\ast }}=\sqrt{\Vert P{\Vert }^2\Vert Q{\Vert }^2}=\Vert Q\Vert \cdot \Vert P\Vert$

Jednotkové kvaterniony

• $\Vert Q\Vert =1$

• tvoří multiplikativní podgrupu

• $Q^{-1}=Q^{\ast }$

• Jednotkový kvaternion je tvaru: $Q=(cos(\alpha ),sin(\alpha )\cdot \overline{a}),\Vert \overline{a}\Vert =1$

Rotace

Šír prezentace

Mějme jednotkový kvaternion $q=(\cos \alpha ,n\sin \alpha )$, $n$ je jednotkový vektor. Potom $r=qr{q}^{\ast }$ 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ý. $pr{p}^{-1}=pr\frac{p\ast }{||p|{|}^2}=\frac{p}{|p|}r\frac{p^{\ast }}{|p|}=qr{q}^{\ast }$

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^{\ast })q_2^{\ast }=(q_2{q}_1)r(q_2{q}_1{)}^{\ast }$

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

• Vektor $T=c^{\prime }(t)$ se nazývá tečný vektor ke křivce c v bodě t.

• Křivka je regulární, pokud její derivace

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 12: c'(t) \neq \̲[̲0,0,0]

  .

• Křivka je parametrizovaná obloukem, pokud $|c^{\prime }(t)|=1$

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

• Délka křivky: ${\int }_{\alpha }^{\beta }|c^{\prime }(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\ast (s)|=|T^{\prime }(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^{\prime }(s)$), normálový ($N(s)=\frac{T^{\prime }(s)}{|T^{\prime }(s)|}=\frac{T^{\prime }(s)}{\kappa (s)}$) a binormálový vektor ($B=T\times N$).

• Existuje jediná hladká fce $\tau (s)$ nazývaná torze, tak, že

$T^{\prime }=\kappa N$, $N^{\prime }=-\kappa T+\tau B$, $B^{\prime }=-\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^{\prime }(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^{\prime }(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%20%28mathematics%29, 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%20interpolation

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%20curve, wcs:Bézierova%20kř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)=\left(\genfrac{}{}{0ex}{}{n}{i}\right)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)=\{\begin{array}{cc}1& \mathbf{if}{u}_i<u<u_{i+1}\\ 0& \mathbf{jinak}\end{array}$

Pro $p\ne 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

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲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

wen:De%20Casteljau's%20algorithm

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

wen:De%20Boor's%20algorithm

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.

Jak vložit uzel?

• 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%20surface - 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

Konstrukce

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ů

http://www.fi.muni.cz/%7Ehlineny/Teaching/OU/OU-text07.pdf

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

Množina $X\subseteq R^n$ je konvexní, pokud pro každé dva prvky $x,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 $z\notin X,z\in R^n$. Pak existuje nadrovina oddělující $z$ od $X$.

Návrh geometrických algoritmů a jejich složitost

Voroného diagram a Delaunayova triangulace

Voronoi diagramy,wen:Voronoi%20diagram

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%20algorithm - 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%20triangulation

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:%20Státnice%20Informatika%20Mgr.