Osnove kompjuterske geometrije
| |
Smjer: |
Teorijska kompjuterska nauka |
| |
Semestar: |
VII |
| |
Tip kursa: |
Obavezni |
| |
Fond sati: |
3+2+0 |
| |
Broj
ECTS kredita: |
8 |
Nastavni program:
-
Uvod u kompjutersku geometriju: Problemi i
značaj geometrijskih algoritama; Oblasti primjene kompjuterske geometrije (kompjuterska
grafika, CAD–CAM, robotika, kompjuterska vizija, GIS itd.); Elementarni
geometrijski objekti; Tačke, linije i poligoni; Načini zapisivanja krivih
linija (eksplicitni, implicitni, parametarski);
-
Osnovni geometrijski algoritmi; Jednostavni
zatvoreni put; Konveksni omotač; Brzi algoritmi za nalaženje konveksnog
omotača (Graham scan, motanje paketa); Najbliži par tačaka; Presjeci
pravolinijskih segmenata; Jednodimenzionalna i dvodimenzionalna pretraga
opsega; Randomizacija u geometrijskim algoritmima;
-
Trijangulacija poligona: Linijski segmenti i
njihovi presjeci; Potreba za trijangulacijom; Naivni algoritmi za
trijangulaciju; Podjela poligona na monotone dijelove; Triangulacija
monotonog poligona; Problem umjetničke galerije;
-
Problemi bliskosti i Voronoi dijagrami:
Definicija Voronoi dijagrama; Osnovne karakteristike Voronoi dijagrama;
Sračunavanje Voronoi dijagrama; Fortune's algoritam;
-
Delaunay trijangulacija: Trijangulacija
planarnog skupa tačaka; Svojstva Delanuay trijangulacije; Sračunavanje
Delanuay trijangulacije; Flip-edge algoritam; Veza Delanuay trijangulacije i
Voronoi dijagrama;
-
Ostali geometrijski algoritmi i geometrijske
strukture podataka;
Literatura:
-
Mark de Berg, Marc van Kreveld, Mark
Overmars, Otfried Schwarzkopf, Computational Geometry, Algorithms
and Applications , Springer Verlag, 1997
-
Peter Shirley, Fundamentals of Computer
Graphics, A.K. Peters, 2002
-
Roger Sedgewick, Algorithms in C++,
Addisson-Wesley, 1992
-
Miodrag Živković, Algoritmi,
Matematički fakultet, Beograd, 2000