Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Geometria obliczeniowa
Tok studiów:
2014/2015
Kod:
IIN-1-782-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
7
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr inż. Głut Barbara (glut@agh.edu.pl)
Osoby prowadzące:
dr inż. Głut Barbara (glut@agh.edu.pl)
Krótka charakterystyka modułu

Wprowadzenie do problematyki geometrii obliczeniowej

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Student zna i rozumie pojęcia oraz problemy występujące w geometrii obliczeniowej omawiane w ramach przedmiotu IN1A_W04, IN1A_W03 Wynik testu zaliczeniowego
M_W002 Student ma uporządkowaną wiedzę na temat struktur danych i algorytmów geometrycznych służących przeszukiwaniu obszarów, lokalizacji obiektów, poligonizacji obiektów, planowaniu ruchu obiektów, optymalizacji geometrycznej IN1A_W04, IN1A_W03 Wynik testu zaliczeniowego
M_W003 Student dysponuje wiedzą na temat zastosowań geometrii obliczeniowej w modelowaniu rzeczywistości, symulacjach komputerowych, grafice komputerowej, robotyce oraz ogólnie w projektowaniu i tworzeniu systemów informatycznych IN1A_W04, IN1A_W03 Wynik testu zaliczeniowego
Umiejętności
M_U001 Student potrafi dobrać strukturę danych i algorytm geometrii obliczeniowej adekwatny do opracowywanego zagadnienia IN1A_U11, IN1A_U09, IN1A_U07, IN1A_U08 Wykonanie projektu,
Wykonanie ćwiczeń laboratoryjnych
M_U002 Student potrafi właściwie zaimplementować algorytm geometrii obliczeniowej zwracając uwagę na efektywność obliczeniową IN1A_U11, IN1A_U09, IN1A_U07, IN1A_U08 Wykonanie projektu,
Wykonanie ćwiczeń laboratoryjnych
M_U003 Student potrafi korzystać z bibliotek geometrii obliczeniowej oraz posłużyć się właściwie dobranymi środowiskami programistycznymi IN1A_U13, IN1A_U11, IN1A_U09, IN1A_U07, IN1A_U08 Wykonanie projektu,
Wykonanie ćwiczeń laboratoryjnych
M_U004 Student potrafi zaprojektować oraz tworzyć efektywne aplikacje wykorzystujące algorytmy geometrii obliczeniowej IN1A_U13, IN1A_U06, IN1A_U05, IN1A_U03, IN1A_U11, IN1A_U12, IN1A_U09, IN1A_U07, IN1A_U08 Wykonanie projektu,
Wykonanie ćwiczeń laboratoryjnych
Kompetencje społeczne
M_K001 Student potrafi pracować w grupie, odpowiednio określić priorytety dla realizacji celu, adekwatnie zaplanować pracę IN1A_K03, IN1A_K04 Aktywność na zajęciach,
Prezentacja,
Udział w dyskusji,
Wykonanie projektu,
Zaangażowanie w pracę zespołu
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Student zna i rozumie pojęcia oraz problemy występujące w geometrii obliczeniowej omawiane w ramach przedmiotu + - - - - - - - - - -
M_W002 Student ma uporządkowaną wiedzę na temat struktur danych i algorytmów geometrycznych służących przeszukiwaniu obszarów, lokalizacji obiektów, poligonizacji obiektów, planowaniu ruchu obiektów, optymalizacji geometrycznej + - - - - - - - - - -
M_W003 Student dysponuje wiedzą na temat zastosowań geometrii obliczeniowej w modelowaniu rzeczywistości, symulacjach komputerowych, grafice komputerowej, robotyce oraz ogólnie w projektowaniu i tworzeniu systemów informatycznych + - - - - - - - - - -
Umiejętności
M_U001 Student potrafi dobrać strukturę danych i algorytm geometrii obliczeniowej adekwatny do opracowywanego zagadnienia - - + - - - - - - - -
M_U002 Student potrafi właściwie zaimplementować algorytm geometrii obliczeniowej zwracając uwagę na efektywność obliczeniową - - + - - - - - - - -
M_U003 Student potrafi korzystać z bibliotek geometrii obliczeniowej oraz posłużyć się właściwie dobranymi środowiskami programistycznymi - - + - - - - - - - -
M_U004 Student potrafi zaprojektować oraz tworzyć efektywne aplikacje wykorzystujące algorytmy geometrii obliczeniowej - - + - - - - - - - -
Kompetencje społeczne
M_K001 Student potrafi pracować w grupie, odpowiednio określić priorytety dla realizacji celu, adekwatnie zaplanować pracę - - + - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

1. Wprowadzenie do geometrii obliczeniowej. Rys historyczny, zastosowania geometrii obliczeniowej, podstawowe pojęcia, sposoby reprezentacji obiektów geometrycznych, podstawowe metody rozwiązywania problemów geometrycznych, przegląd typów algorytmów stosowanych w geometrii obliczeniowej. Omówienie często stosowanego algorytmu geometrycznego – algorytmu zamiatania na przykładzie problemu przecinania odcinków w 2D.
2. Zagadnienie otoczki wypukłej. Przegląd i analiza algorytmów, charakterystyka ich efektywności, omówienie zastosowania problemu.
3. Problem monitorowania galerii. Opis zagadnienia, triangulacja wielokątów w 2D, wielokąty monotoniczne, podział wielokąta na wielokąty monotoniczne, triangulacja wielokąta monotonicznego.
4. Diagramy Voronoi i triangulacja Delaunay’a. Omówienie własności konstrukcji, zastosowania, przegląd algorytmów generowania wielościanów Voronoi (szczegółowy opis algorytmu Fortune’a) i triangulacji Delaunay’a (szczegółowy opis algorytmów iteracyjnych).
5. Lokalizacja punktu na płaszczyźnie. Metody rozwiązywania zagadnienia: warstwowa, trapezowa, separatorów, doskonalenia triangulacji, opis algorytmów, analiza złożoności.
6. Przeszukiwanie geometryczne. Przeszukiwanie obszarów ortogonalnych (Kd-drzewa, drzewa obszarów, kaskadowanie cząstkowe), okienkowanie (drzewa przedziałów, przeszukiwań priorytetowych, odcinków), binarne podziały przestrzeni – drzewa BSP.
7. Generowanie siatek dla obszarów dwuwymiarowych. Definicja siatki, topologia siatek, problemy informatyczne związane z konstrukcją siatek, podział metod konstrukcji siatek, omówienie metod konstrukcji siatek strukturalnych i niestrukturalnych.
8. Planowanie ruchu robota. Omówienie zagadnienia i problemów z nim związanych, podział metod – ze względu na wiedzę o otoczeniu w fazie planowania ruchu oraz na sposób reprezentacji środowiska, przestrzeń robocza i konfiguracyjna, sumy Minkowskiego, planowanie ruchu postępowego i planowanie ruchu z obrotami – omówienie algorytmów.
9. Dyskretyzacja powierzchni 3D i generowanie siatek objętościowych. Omówienie problemu, przegląd metod, wstęp do modelowania geometrycznego

Ćwiczenia laboratoryjne:

1. Implementacja podstawowych predykatów geometrycznych, przeprowadzenie testów, wizualizacja i opracowanie wyników
2. Implementacja wybranych algorytmów wyznaczania otoczki zbioru punktów w 2D, przeprowadzenie testów, wizualizacja i opracowanie wyników
3. Implementacja algorytmu wyznaczania przecięć odcinków na płaszczyźnie, przeprowadzenie testów, wizualizacja i opracowanie wyników
4. Implementacja algorytmu sprawdzania, czy dany wielokąt jest monotoniczny oraz algorytmu triangulacji wielokąta monotonicznego, przeprowadzenie testów, wizualizacja i opracowanie wyników
5. Przy wykorzystaniu udostępnionego oprogramowania opracowanie programu wyznaczającego diagramy Voronoi dla chmury punktów oraz triangulację Delaunay’a dla zadawanych wielokątów (constrained triangulation), przeprowadzenie testów, wizualizacja i opracowanie wyników
6. Wykorzystanie wieloboków Voronoi i triangulacji Delaunay’a – np. poszukiwanie sąsiedztwa, wyznaczanie Medial Axis dla zadawanych wieloboków, opracowanie programów, przeprowadzenie testów, wizualizacja i opracowanie wyników
7. Indywidualne projekty – prezentacja zagadnienia oraz podstaw teoretycznych projektu; wyszukanie dostępnych bibliotek; ocena istniejącego oprogramowania; dobór algorytmów, struktur danych i komponentów oprogramowania; opracowanie projektu aplikacji; implementacja zagadnienia, przygotowanie dokumentacji, prezentacja programu oraz omówienie wyników
W ramach pracy własnej studenci opracowują interfejs graficzny pozwalający na wprowadzanie danych dla poszczególnych ćwiczeń oraz wizualizujący wyniki.
Ćwiczenia laboratoryjne prowadzone są z elementami e-learningu.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 78 godz
Punkty ECTS za moduł 3 ECTS
Udział w wykładach 14 godz
Samodzielne studiowanie tematyki zajęć 15 godz
Udział w ćwiczeniach laboratoryjnych 14 godz
Dodatkowe godziny kontaktowe z nauczycielem 15 godz
Przygotowanie do zajęć 10 godz
Wykonanie projektu 10 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

1. Aby uzyskać pozytywną ocenę końcową niezbędne jest uzyskanie pozytywnej oceny z laboratorium oraz kolokwium zaliczeniowego z wykładu.
2. Ocena „sr” wyliczana jest jako średnia ważona z ocen z laboratorium (2/3) i wykładów (1/3) uzyskanych we wszystkich terminach.
3. Ocena końcowa OK po spełnieniu warunków punktu 1 wyliczana jest na podstawie zależności:
if sr>4.75 then OK:=5.0 else
if sr>4.25 then OK:=4.5 else
if sr>3.75 then OK:=4.0 else
if sr>3.25 then OK:=3.5 else OK:=3

Wymagania wstępne i dodatkowe:

Podstawy informatyki, języki i techniki programowania, algorytmy i struktury danych, podstawy grafiki komputerowej

Zalecana literatura i pomoce naukowe:

1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Geometria obliczeniowa. Algorytmy i zastosowania, WNT 2007
2. F.P. Preparata, M.I. Shamos, Geometria obliczeniowa. Wprowadzenie, Helion 2003
3. J. O’Rourke, Computational Geometry in C, Cambridge University Press 2008
4. J.-D. Boissonnat, M. Yvinec, Algorithmic geometry, Cambridge University Press 1998
5. P. Schneider, D. Eberly, Geometric tools for computer graphics, Elsevier Science 2003
6. E. D. Demaine, J. O’Rourke, Geometric Folding Algorithms, Cambridge University Press 2007

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. T. Jurczyk and B. Głut. Preparation of control space for remeshing polygonal surfaces, Computer
Science, 2013, 14(4), 559-561. ISSN 1508-2806
2. B. Głut and T. Jurczyk. Preparation of the Sizing Field for Volume Mesh Generation, Proc. of the 13h
International Conference on Civil, Structural and Environmental Engineering Computing, paper 115, 6-9
September 2011, Chania, Crete, Greece.
3. T. Jurczyk and B. Głut. The Insertion of Metric Sources for Three-dimensional Mesh Generation, Proc.
of the 13h International Conference on Civil, Structural and Environmental Engineering Computing,
paper 116, 6-9 September 2011, Chania, Crete, Greece.
4. B. Głut and T. Jurczyk. Automated Recognition of Adaptation Regions for FEM Meshes in 3D Problems,
Proc. of Seventh International Conference on Engineering Computational Technology, September 14-17,
2010, Valencia, Spain.

Informacje dodatkowe:

Brak