Cilj i ishod predmeta
Sticanje znanja iz geometrijskih algoritama (kompjuterske geometrije).
Po završetku, student zna da koristi osnovne i složenije geometrijske strukture podataka i algoritme.
Razume i zna da rešava geometrijske probleme u vezi sa Računarskom geometrijom, računarskom grafikom,
grafičkim korisničkim interfejsom, računarskim igrama i sličnim primenama.
Teorijska nastava
Predstavljanje geometrijskih objekata. Problem određivanja preseka n duži. Problem određivanja
najbližeg para tačaka među n tačaka. Konveksni omotač u 2D (Jarvis-ov, Graham-ov, divide-and-conquer,
quick-hull i radnomizirani algoritam, Cronecker-Seidel-ovi Chan-ov algoritam). Planarni grafovi i
dvostruko povezane liste ivica. Preseci poluravni i linearno programiranje. Dualna ravan i veza između
konveksnog omotača i preseka poluravni. Konveksni omotač u 3D: (gift-wrapping i inkrementalni
algoritam). Triangulacija poligona. Voronoi dijagrami. Delaunay trijangulacija. Efikasne strukture
podataka za upite vezane za broj tačaka u nekoj oblasti . Efikasne strukture za rad sa intervalima.
Praktična nastava
Implementacija algoritama i struktura podataka koji su obrađeni na predavanjima. Implementacija
strukture dvostruko povezane liste ivica (double connected edge list, DCEL) koja se koristi za
reprezentovanje podele ravni u povezane podoblasti. Implementacija algoritma za određivanje preseka
duži u ravni. Implementacija raznih algoritama za određivanje konveksnog omotača, algoritma za
trijangulaciju prostog poligona, algoritma za određivanje Voronoi dijagrama za zadati skup tačaka,
algoritma za određivanje Deloni trijangulacije. Implementacija nekih struktura podataka:kd -stablo,R –
stablo, intervalna stabla, segmentna stabla. Dizajn i analiza algoritama za razne probleme iz oblasti
geometrije primenom tehnika računarske geometrije: tehnika brišuće prave, inkrementalni algoritmi,
dualna ravan i transformacija problema od problema u primarnoj ravni do problema u dualnoj ravni.
Korišćenje pogodnih struktura za rešavanje raznih problema računarske geometrije.