Геометријски алгоритми

Циљ и исход предмета

Стицање знања из геометријских алгоритама (компјутерске геометрије). По завршетку, студент зна да користи основне и сложеније геометријске структуре података и алгоритме. Разуме и зна да решава геометријске проблеме у вези са Рачунарском геометријом, рачунарском графиком, графичким корисничким интерфејсом, рачунарским играма и сличним применама.

Теоријска настава

Представљање геометријских објеката. Проблем одређивања пресека н дужи. Проблем одређивања најближег пара тачака међу n тачака. Конвексни омотач у 2D (Jarvis-ов, Graham-ов, divide-and-conquer, quick-hull и рандомизирани алгоритам, Cronecker-Seidel-ови Chan-ов алгоритам). Планарни графови и двоструко повезане листе ивица. Пресеци полуравни и линеарно програмирање. Дуална раван и веза између конвексног омотача и пресека полуравни. Конвексни омотач у 3D: (gift-wrapping и инкрементални алгоритам). Триангулација полигона. Воронои дијаграми. Delaunay тријангулација. Ефикасне структуре података за упите везане за број тачака у некој области . Ефикасне структуре за рад са интервалима.

Практична настава

Имплементација алгоритама и структура података који су обрађени на предавањима. Имплементација структуре двоструко повезане листе ивица (double connected edge list, DCEL) која се користи за репрезентовање поделе равни у повезане подобласти. Имплементација алгоритма за одређивање пресека дужи у равни. Имплементација разних алгоритама за одређивање конвексног омотача, алгоритма за тријангулацију простог полигона, алгоритма за одређивање Воронои дијаграма за задати скуп тачака, алгоритма заодређивање Делони тријангулације. Имплементација неких структура података:кд -стабло,R - стабло, интервална стабла, сегментна стабла. Дизајн и анализа алгоритама за разне проблеме из области геометрије применом техника рачунарске геоемтрије: техника бришуће праве, инкрементални алгоритми, дуална раван и трансформација проблема од проблема у примарној равни до проблема у дуалној равни. Коришћење погодних структура за решавање разних проблема рачунарске геометрије.