Циљ и исход предмета
Стицање знања из геометријских алгоритама (компјутерске геометрије).
По завршетку, студент зна да користи основне и сложеније геометријске структуре података и алгоритме.
Разуме и зна да решава геометријске проблеме у вези са Рачунарском геометријом, рачунарском графиком,
графичким корисничким интерфејсом, рачунарским играма и сличним применама.
Теоријска настава
Представљање геометријских објеката. Проблем одређивања пресека н дужи. Проблем одређивања
најближег пара тачака међу н тачака. Конвексни омотач у 2D (Jarvis-ов, Graham-ов, divide-and-conquer,
quick-hull и радномизирани алгоритам, Cronecker-Seidel-ови Chan-ов алгоритам). Планарни графови и
двоструко повезане листе ивица. Пресеци полуравни и линеарно програмирање. Дуална раван и веза између
конвексног омотача и пресека полуравни. Конвексни омотач у 3D: (gift-wrapping и инкрементални
алгоритам). Триангулација полигона. Voronoi дијаграми. Delaunay тријангулација. Ефикасне структуре
података за упите везане за број тачака у некој области . Ефикасне структуре за рад са интервалима.
Практична настава
Имплементација алгоритама и структура података који су обрађени на предавањима. Имплементација
структуре двоструко повезане листе ивица (double connected edge list, DCEL) која се користи за
репрезентовање поделе равни у повезане подобласти. Имплементација алгоритма за одређивање пресека
дужи у равни. Имплементација разних алгоритама за одређивање конвексног омотача, алгоритма за
тријангулацију простог полигона, алгоритма за одређивање Voronoi дијаграма за задати скуп тачака,
алгоритма за одређивање Делони тријангулације. Имплементација неких структура података:кд -стабло,Р –
стабло, интервална стабла, сегментна стабла. Дизајн и анализа алгоритама за разне проблеме из области
геометрије применом техника рачунарске геометрије: техника бришуће праве, инкрементални алгоритми,
дуална раван и трансформација проблема од проблема у примарној равни до проблема у дуалној равни.
Коришћење погодних структура за решавање разних проблема рачунарске геометрије.