Počítačová geometrie I

0 Počítačová geometrie I RNDr. Petra Surynková, Ph.D. Katedra didaktiky matematiky

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

[email protected] http://surynkova.info

Osnova předmětu  

Pojem výpočetní geometrie, oblasti aplikací Analytické vyjádření zobrazovacích metod 



Transformace roviny a prostoru 



zobrazování těles, určování viditelnosti

Algoritmy počítačové geometrie      



analytické vyjádření

Prostorové modelování 



kótované promítání, Mongeovo promítaní, kosoúhlé promítání, axonometrie, středové promítání, cylindrická a sférická perspektiva

lokalizace bodu mnoţinové operace hledání konvexního obalu Voronoi diagram Delaunay triangulace průsečíky a průniky základních geometrických útvarů

Rovinné grafy

Počítačová geometrie

Petra Surynková

Literatura k přednášce 

Ţára J., Beneš B., Sochor J., Felkel P. (2005): Moderní počítačová grafika. Computer Press, Praha.



Preparata F. P., Shamos M. I. (1985): Computational geometry. SpringerVerlag, New York, USA.



Pelikán J. (1992): PC - Prostorové modelování. Grada, Praha.



Farin G. , Hoschek J., Kim M. (2002): Handbook of Computer Aided Geometric Design. Elsevier.



Pottmann H, Asperl A., Hofer M., Kilian A. (2007). Architectural Geometry. Bentley Instute Press, USA.



Foley J. D., van Dam A., Feiner S. K., Hughes J. F. (1995). Computer Graphics: principles and practice. Addison-Wesley Publishing Company, USA.



Jeţek F. (2006). Geometrické a počítačové modelování. Západočeská univerzita v Plzni, Fakulta aplikovaných věd, (online).


Petra Surynková

Literatura ke cvičení 

Heringová B. , Hora P. : Matlab I. díl – práce s programem (online).



Heringová B. , Hora P. : Matlab II. díl – popis funkcí (online).



Daniš S. (2009): Základy programování v prostředí Octave a Matlab, Matfyzpress.



Zaplatílek K., Doňar B. (2003): Matlab pro začátečníky, Nakladatelství BEN – technická literatura.



Kupka L. (2007): Matlab a Simulink: úvod do použití, SOŠ a SOU Lanškroun.



Novák J., Pultarová I., Novák P. (2005): Základy informatiky – Počítačové modelování v Matlabu, Česká technika – nakladatelství ČVUT.


Petra Surynková

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 (v polygonu, mnohostěnu)  dělení roviny či prostoru na oblasti, určení bodů v oblasti  hledání nejmenší 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ů  triangulace, tetrahedronizace, Voronoiovy diagramy  plánování pohybu, nalezení cesty v prostředí (s překáţkami)  + algoritmizace úloh DG


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

x Počítačová geometrie

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á



3D skenování, 3D tisk, rekonstrukce ploch, reverzní inţenýrství, online marketing


Petra Surynková



3D skenování, 3D tisk, rekonstrukce ploch, reverzní inţenýrství, online marketing


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á

Počítačová geometrie I

Recommend Documents