Geometria obliczeniowa

Opis przedmiotu

Wykład:
2 semestr INF MU — wtorek 09:45-11:15 (co dwa tygodnie), sala B101A

Laboratorium:
2 semestr INF MU — poniedziałek 11:30-13:00, sala B101A

Zajęcia poświęcone będą podstawowym algorytmom geometrii obliczeniowej. Główne tematy poruszane na zajęciach to:

• wprowadzenie do geometrii obliczeniowej,
• otoczka wypukła zbioru punktów,
• problem galerii sztuki i triangulacja wielokąta,
• diagramy Voronoi,
• triangulacja Delaunay,
• binarne podziały przestrzeni,
• znajdowanie przecięcia odcinków,
• nakładanie się map,
• programowanie liniowe,
• przeszukiwanie obszarów ortogonalnych,
• lokalizacja punktu,
• okienkowanie,
• otoczka wypukła w 3D,
• planowanie ruchu robota,
• drzewa ćwiartek,
• grafy widzialności,
• przeszukiwanie obszarów sympleksowych.

Zasady panujące na zajęciach oraz zaliczenie

Warunkiem zaliczenia zajęć jest pozytywna ocena z projektu zaliczeniowego.

Propozycje projektów zaliczeniowych

Ogólne uwagi odnośnie zajęć:

• nad zadaniami można pracować pojedynczo lub w zespołach dwuosobowych,
• każdy zespół pracuje nad zadaniami samodzielnie,
• dozwolone jest douczanie się nawzajem oraz dzielenie się informacjami; za informacje nie uznaje się cudzego kodu, więc kopiowanie kodu jest traktowane jako oszustwo,
• należy przestrzegać zasad uczciowości akademickiej,
• wszelkie próby oszustwa, np. oddawanie cudzego kodu, skutkują brakiem zaliczenia przedmiotu.

Uwagi dotyczące projektu zaliczeniowego:

• projekty można wykonywać pojedynczo lub w parach,
• język programowania — dowolny,
• algorytmy używane w projekcie powinny być zaimplementowane w taki sposób, aby działały w rozsądnym czasie,
• w kodzie projektu należy umieszczać komentarze ułatwiające zrozumienie kodu osobie z ,,zewnątrz'',
• jakość kodu (czytelność, odpowiednie nazwy zmiennych i funkcji itp.) będzie miała wpływ na ocenę,
• do każdego projektu powinien być dołączony opis (czego projekt dotyczy, możliwości programu, opis obsługi, użyte dodatkowe biblioteki); szablon ze strukturą dokumentu z opisem projektu: szablon.pdf, szablon.tex
• kompletny projekt (kod źródłowy + wszystkie pliki potrzebne do kompilacji, opis projektu w pliku pdf, wersja wykonywalna) w postaci archiwum zip lub 7z należy przesłać/dostarczyć do prowadzącego do 23:59:59 30.01.2026; struktura katalogów w archiwum powinna być następująca:
  • bin — katalog z wersją wykonywalną projektu,
  • doc — katalog z plikiem pdf z opisem oraz inne pliki prezentujące projekt,
  • src — katalog ze źródłami, bibliotekami potrzebnymi do kompilacji itp.,
• oddanie projektu w terminie późniejszym niż wymieniony w poprzednim punkcie, ale nie później niż 23:59:59 20.02.2026, skutkuje obniżeniem oceny projektu o 0,5 stopnia,
• oddanie projektu w terminie późniejszym niż wymieniony w poprzednim punkcie skutkuje oceną niedostateczną w pierwszym terminie oraz obniżeniem oceny w drugim terminie o 1 stopień,
• projekty na ocenę w drugim terminie można przesyłać do 23:59:59 08.03.2026,
• nie ma możliwości przesunięcia ostatecznego terminu oddawania projektów.