Počítačová geometrie. + algoritmy DG

Počítačová geometrie 

Pojem výpočetní geometrie (počítačové)   



analýza a návrh efektivních algoritmů pro určování vlastností a vztahů geometrických objektů řešení geometrických problémů navrženými geometrickými algoritmy hlavním podnětem vzniku VG jako samostatné disciplíny – rozvoj počítačové grafiky, CAD/CAM systémů (počítačem podporovaná výroba a projektování) řeší se        

transformace roviny a prostoru problémy geometrického vyhledávání, problém polohy bodu hledání konvexní obálky množiny bodů v d-rozměrném prostoru problém hledání blízkých bodů výpočet průniků polygonálních oblastí a poloprostorů geometrie rovnoběžníků … + algoritmy DG

Počítačová geometrie

Petra Surynková


transformace roviny a prostoru y

y X [ x, y]

X [ x, y ]

 S[ x S , y S ]

y

S[ x S , y S ]

y

X [ x, y]

x

X [ x, y] X [ x, y]

X [ x, y ]

x

X [ x, y]

x Počítačová geometrie

X [ x, y]

x Petra Surynková


problémy geometrického vyhledávání, problém polohy bodu

M2 M1


M3

Petra Surynková


hledání konvexní obálky množiny bodů v d-rozměrném prostoru


Petra Surynková


výpočet průniků polygonálních oblastí a poloprostorů

y


Petra Surynková


triangulace


Petra Surynková


co je potřeba   



porozumění geometrickým vlastnostem problémů používat vhodnou aplikaci algoritmů a datových struktur zvládat techniky tvorby efektivních algoritmů

doporučení  



singulární případy – zprvu ignorovat, zahrnout až dodatečně (v praxi jde o běžnou metodu), důležité experimentování důležitá numerická stabilita – algoritmus může být správný a přesto nerobustní (bod napravo nalevo od přímky, průnik přímky a roviny, …) – těžké ošetřit hodnocení a porovnávání algoritmů nezávislé na typu počítače a na jazyku


Petra Surynková


Oblasti aplikací 

počítačová grafika – lokalizace myši, řešení viditelnosti, průniky geometrických objektů, stíny, …

http://cs.wikipedia.org Počítačová geometrie

Petra Surynková



geografické informační systémy (GIS) – digitální modely terénu, kartografie


http://www.sciencegl.com/gis_ dem/index.html Petra Surynková



CAD/CAM systémy (computer aided design and manufacturing) – návrh a výroba podporovaná počítačem


http://www07.ibm.com/lenovoi nfo/thinkstation/bd/A pplications.html Petra Surynková


Oblasti aplikací         

2D, 3D konstrukce obrazová analýza počítačové modelování vizualizace, hry, simulátory virtuální realita editory dopravních sítí rozpoznávání textu GIF, Flash animace …


Petra Surynková

Analytické vyjádření zobrazovacích metod 

Promítání (projekce)  

zobrazování prostorových objektů do roviny (průmětny) určeno středem (směrem) a průmětnou

3D   2D

 Počítačová geometrie

 Petra Surynková


promítací paprsek – přímka vedená promítaným bodem, jejíž směr závisí na zvolené promítací metodě



průmětna – rovina (i obecná plocha), do které promítáme



průmět bodu – průsečík promítacího paprsku a průmětny



při zobrazování prostorových objektů následuje po promítání další zpracování dat 

př. nalezení viditelných a zakrytých částí objektů


Petra Surynková


 



s

Rovnoběžné promítání střed promítání - nevlastní promítací přímky jsou určeny směrem promítání – všechny promítací paprsky mají stejný směr

A



A

B S

Středové promítání  

střed promítání – vlastní promítací přímky procházejí středem promítání – všechny promítací paprsky vycházejí z jednoho bodu


B



A

B

A

B

Petra Surynková

Rovnoběžné promítaní 





v prostoru zvolme kartézskou soustavu souřadnic    S  {O; e1 , e2 , e3}, v níž je analyticky popsán objekt, který zobrazujeme v průmětně zvolme kartézskou soustavu souřadnic

  S   {O; e1, e2 }

promítání do jiné průmětny můžeme vždy převést pomocí transformace (nejčastěji otočení nebo posunutí)


Petra Surynková


Kótované promítání A A  A [  x ,  y ] A[ x A , y A , z A ]  

z

y

A

xA

O

y A


x

O

A

 yA

x, y- souřadnice ve 2D Petra Surynková


Mongeovo promítání A[ x A , y A , z A ]   A1[  x A ,  y A ] A2 [  x A , z A ]

z

A3[ y A , z A ] y

A3

A2

zA

xA

O

A

A2

O

y A1


( y ) x, y- souřadnice ve 2D

A1

x

yA Petra Surynková


Kosoúhlá axonometrie z  y



dáno: 

průměty os s jednotkami

jx , j y , jz

jz x, y- souřadnice ve 2D

O



jx x Počítačová geometrie



x

jy y Petra Surynková



  ei - průměty ei  e1  (  jx cos  ,  jx sin  )  e2  ( j y cos  ,  j y sin  )  e3  (0, jz )



jz O






x

jy

j y cos 

 y

jy Petra Surynková



A[ x A , y A , z A ]   A[  x A  jx  cos   y A  j y  cos   0,

A

 x A  jx  sin   y A  j y  sin   z A  jz ]

jz

z A  jz

O




y  jy A



x

jy x  jx A



bod A vyjadřujeme v soustavě S 

y Petra Surynková


Nejčastěji se používají následující typy axonometrií 

Izometrie 

jx : j y : jz  1:1:1



    30



pro

jx  1, dostaneme dosazením do vzorců

 3  1 A A A A A  A    x  y  ,   x  y   z  A[ x , y , z ]  2  2  A

A


A

Petra Surynková



Dimetrie 

jx : j y : jz  k : k :1



nebo můžeme provést cyklickou záměnu



úhly  ,  volíme tak, že axonometrické osy se stejnými jednotkami jsou symetrické vzhledem ke zbývající ose



pro jx : j y : jz  1: 2 : 2 a technickou dimetrii


    30 dostaneme

Petra Surynková



Dimetrie 

technická dimetrie – po dosazení

 3  1 A A A A A  A    x  2 y  ,   x  2 y   2 z  A[ x , y , z ]  2  2  A

A


A

Petra Surynková



Kosoúhlé promítání 

jx : j y : jz  1: q :1





  (0,2 ),  k , k  1,2,3



  0



2

pro


q  1,  45 dostáváme kavalírní perspektivu

Petra Surynková



Kosoúhlé promítání 

kavalírní perspektiva – po dosazení

 2 A  2 A A A A   A[ x , y , z ]  x  y , x z  2  2  A


A

A

Petra Surynková



Pravoúhlá axonometrie 

volíme úhly  ,  , vše ostatní odvodíme z vlastností pravoúhlé axonometrie


Petra Surynková



Pravoúhlá axonometrie

z

Z

OZ jz  (O) Z

2

O

X x

2

(O) P  OP 2



(O)

3 1

P


O(O)   (O) P

1  2  3 

 1

Y

 2

y

(O) P OP

2



2

(O) P

2



Petra Surynková



Pravoúhlá axonometrie

 1

PY tg 1 PX tg 2 (O ) P

2



 1  tg 1 tg 2

jz  1  tg 1 tg 2 

ostatní jednotky stejně

jx  1  tg 2 tg 3 j y  1  tg 1 tg 3 Počítačová geometrie

Petra Surynková

Počítačová geometrie. + algoritmy DG

Recommend Documents