Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Geometria komputerowa
Tok studiów:
2018/2019
Kod:
JIS-2-016-GK-s
Wydział:
Fizyki i Informatyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Grafika komputerowa i przetwarzanie obrazów
Kierunek:
Informatyka Stosowana
Semestr:
0
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Osoba odpowiedzialna:
prof. dr hab. Kaprzyk Stanisław (kaprzyk@wfitj12e.ftj.agh.edu.pl)
Osoby prowadzące:
prof. dr hab. Kaprzyk Stanisław (kaprzyk@wfitj12e.ftj.agh.edu.pl)
Krótka charakterystyka modułu

Student poznaje podstawy teoretyczne geometrii komputerowej i podstawowe sposoby realizacji algorytmów stosowanych w tej dziedzinie.

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 klasyczne podstawy geometrii Euklidesa i posiada wiedzę o abstrakcyjnych obiektach z geometrii Hilberta IS2A_W01, IS2A_W03 Aktywność na zajęciach
M_W002 Student posiada wiedzę o algorytmach i kodach komputerowych stosowanych w geometrii dyskretnej, oraz i ich efektywności obliczeniowej w praktycznych aplikacjach IS2A_W08, IS2A_W03 Udział w dyskusji,
Wykonanie ćwiczeń,
Wykonanie ćwiczeń laboratoryjnych
Umiejętności
M_U001 Student potrafi dokonać krytycznej analizy problemu i sformułować odpowiedni model w języku abstrakcyjnych pojęć geometrycznych IS2A_U01, IS2A_U04 Sprawozdanie,
Wykonanie ćwiczeń laboratoryjnych
M_U002 Student potrafi zaprojektować, uruchomić i ocenić efektywność obliczeniową kodu komputerowego w praktycznych zastosowaniach IS2A_U02, IS2A_U04 Udział w dyskusji,
Wykonanie ćwiczeń laboratoryjnych
Kompetencje społeczne
M_K001 Student potrafi współpracować twórczo w zespole rozwiązującym problemy praktyczne z wykorzystaniem pojęć i twierdzeń z geometrii IS2A_K01, IS2A_K02 Aktywność na zajęciach
M_K002 Student aktywnie uczestniczy w dyskusjach w grupie, jak również z prowadzącym, potrafi racjonalnie formułować myśli i jasno argumentować IS2A_K02 Aktywność na zajęciach
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 klasyczne podstawy geometrii Euklidesa i posiada wiedzę o abstrakcyjnych obiektach z geometrii Hilberta + - - - - - - - - - -
M_W002 Student posiada wiedzę o algorytmach i kodach komputerowych stosowanych w geometrii dyskretnej, oraz i ich efektywności obliczeniowej w praktycznych aplikacjach + - - - - - - - - - -
Umiejętności
M_U001 Student potrafi dokonać krytycznej analizy problemu i sformułować odpowiedni model w języku abstrakcyjnych pojęć geometrycznych - - + - - - - - - - -
M_U002 Student potrafi zaprojektować, uruchomić i ocenić efektywność obliczeniową kodu komputerowego w praktycznych zastosowaniach - - + - - - - - - - -
Kompetencje społeczne
M_K001 Student potrafi współpracować twórczo w zespole rozwiązującym problemy praktyczne z wykorzystaniem pojęć i twierdzeń z geometrii - - + - - - - - - - -
M_K002 Student aktywnie uczestniczy w dyskusjach w grupie, jak również z prowadzącym, potrafi racjonalnie formułować myśli i jasno argumentować - - + - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  1. Podstawy geometrii klasycznej i geometrii Hilberta (2 godz.)

    Postulaty i pewniki Euklidesa. Aksjomaty Hilberta o incydencjach, o porządku, o kongruencjach, o równoległości i ciągłości.

  2. Incydencje i poglądowe ujęcie geometrii rzutowej (2 godz.)

    Pojęcia pierwotne i aksjomaty. Przecięcia prostych i płaszczyzn. Rzut środkowy na płaszczyźnie i w przestrzeni. Współrzędne kartezjańskie i współrzędne rzutowe

  3. Abstrakcja w geometrii i informatyce (2 godz.)

    Grafy abstrakcyjne i grafy geometryczne. Przykłady różnych grafów i ich związek z obiektami geometrycznymi.

  4. Konfiguracje i inne obiekty geometryczne (2 godz.)

    Elementarne własności konfiguracji. Czworobok zupełny. Konfiguracje regularne.

  5. Wielokąty, triangulacja i analiza efektywności algorytmów obliczeniowych. (2 godz.)

    Zapis wielokąta. Problem monitorowania galerii sztuki. Przekątne wielokąta i podział rekurencyjny. Triangulacja zwykła i grafy dualne.

  6. Otoczki wypukłe na płaszczyźnie (2 godz.)

    Określenia i definicje. Punkty i krawędzie skrajne. Algorytmy „Gift wrapping”, „QuickHull”, Grahama, progresywny i „divide et impera”

  7. Diagramy Voronoi na płaszczyźnie (3 godz.)

    Przykłady, określenia i definicje. Tesselacja Voronoi i triangulacja Delaunay. Przegląd algorytmów. Diagramy Voronoi a otoczka wypukłą. Dualność triangulacji Delaunay i tesselacji Voronoi.

  8. Otoczki wypukłe w przestrzeni ( 2godz.)

    Przykłady, określenia i definicje. Wielościany, kompleksy regularne i wielowymiarowe komórki proste. Formuła Eulera.

  9. Przegląd algorytmów przestrzennych i ich implementacja (3 godz.)

    Wielościenna reprezentacja brzegów. Struktura danych w formie uskrzydlonych krawędzi. Struktura danych w formie kwartetów krawędziowych. Twierdzenie o optymalności algorytmu
    „divide et impera”

  10. Otoczki i diagramy Voronoi w przykładach (2 godz.)

    Problem najbliższych sąsiadów. Optymalna triangulacja względem najmniejszego kąta. Największy pusty okrąg. Minimalne drzewo rozgałęzione i marszruta komiwojażera.

  11. Kompozycje geometryczne. Przykłady zastosowań kompozycji. (2godz.)

    Kombinatoryka kompozycji. Algorytm progresywny do konstrukcji kompozycji. Kompozycje i odwzorowania dualne.

  12. Diagramy Voronoi wyższego rzędu. (2 godz.)

    Jednowymiarowe i dwuwymiarowe diagramy wyższego rzędu. Wielowymiarowe diagramy Voronoi najbliższego i najdalszego punktu. Abstrakcyjne diagramy Voronoi z różnymi regułami wagowymi

  13. Najbliższe n-sąsiedztwo, widoczność i cienie obiektów geometrycznych. (2 godz.)

    Lokalne rozwiązywanie problemów bliskości. Usuwanie powierzchni niewidocznych. Grafy aspektowe. Najmniejszy cień obiektów geometrycznych.

  14. Modelowanie układów geometrycznych w ruchu. (2 godz.)

    Elementy kinematyczne w geometrii. Przestrzeń konfiguracyjna. Kodowanie ruchu postępowego i ruchu obrotowego. Zastosowanie sum Minkowskiego do kodowania ruchu z przeszkodami.

Ćwiczenia laboratoryjne:
  1. Proste konstrukcje na płaszczyźnie i elementarne algorytmy geometryczne

    Efekty kształcenia:
    - student potrafi zaprogramować i znaleźć incydencje w płaskich obiektach geometrycznych
    - student potrafi wygenerować w postscripcie i zobrazować wyniki graficznie
    - student potrafi napisać całą dokumentację zadania w LaTeXu

  2. Konstrukcja incydencji w kwartecie harmonicznym i konfiguracji Brianchona-Pascala

    Efekty kształcenia:
    - student potrafi znaleźć analitycznie i wygenerować obrazy graficzne regularnych konfiguracji geometrycznych
    - student potrafi wykonać prezentacje, z uwypukleniem szczególnych własności wygenerowanych obiektów geometrycznych.

  3. Triangulacja zwykła wielokąta prostego

    Efekty kształcenia:
    - student potrafi wykonać analitycznie i przedstawić graficznie triangulację dowolnego wielokąta
    - student potrafi zweryfikować empirycznie efektywność opracowanego algorytmu

  4. Algorytmy i kody komputerowe na pole powierzchni wielokąta

    Efekty kształcenia:
    - student potrafi napisać procedurę i znaleźć pole wielokąta, korzystając ze wzoru, w którym pole jest wyrażone za pomocą antysymetrycznej formy dwuliniowej
    - student pozna własności i strukturę form dwuliniowych, badając niezmienniczość pola względem translacji i obrotów.

  5. Konstrukcja otoczki wypukłej zbioru punktów na płaszczyźnie

    Efekty kształcenia:
    - student potrafi skonstruować otoczkę wypukłą punktów na płaszczyźnie
    - student posiądzie umiejętność oceny efektywności i wyszukiwania kodów optymalnych.

  6. Konstrukcja przestrzennej otoczki wypukłej metodą progresywną

    Efekty kształcenia:
    - student potrafi znaleźć analitycznie i skonstruować graficznie otoczkę wypukłą obiektów w przestrzeni
    - student zdobędzie umiejętność analizy efektywności algorytmów przestrzennych

  7. Triangulacja Delaunay i tesselacja Voronoi na płaszczyźnie

    Efekty kształcenia:
    - student potrafi wykonać analitycznie i graficznie triangulację Delaunay i skonstruować diagramy Voronoi dla dowolnego zbioru punktów na płaszczyźnie
    - student udoskonali umiejętności w dobieraniu efektywnych algorytmów geometrycznych do rozwiązywania problemów praktycznych

  8. Implementacja kodu komputerowego QHULL do konstrukcji diagramów Voronoi w przestrzeni

    Efekty kształcenia:
    - student potrafi wykonać tesselację Delaunay i skonstruować diagramy Voronoi dla zbioru punktów w przestrzeni 3-wymiarowej
    - student zdobędzie umiejętność rozwiązywania problemów geometrycznych w przestrzeniach wyżej wymiarowych, analizując podobne problemy w przestrzeniach niżej wymiarowych

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 104 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 30 godz
Udział w ćwiczeniach laboratoryjnych 30 godz
Samodzielne studiowanie tematyki zajęć 22 godz
Przygotowanie sprawozdania, pracy pisemnej, prezentacji, itp. 22 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena końcowa = 0.9*(średnia ocena z ćwiczeń laboratoryjnych) + 0.1 (aktywność i innowacyjność) Na ocenę każdego ćwiczenia składają się w równym stopniu następujące czynniki: opis problemu w LaTeXu, kod komputerowy w znanym języku, kompilacja i wykonanie pod Unixem całego zadania, oraz wnioski i ocena efektywności algorytmu.

Wymagania wstępne i dodatkowe:

1. Znajomość geometrii analitycznej
2. Znajomość algebry wyższej
3. Biegłość w programowaniu w różnych językach i na różnych platformach komputerowych.

Zalecana literatura i pomoce naukowe:

1. D. Hilbert i S.Cohn-Vossen, Geometria Poglądowa, PWN Warszawa 1956.
2. K. Borsuk i W.Szmielew, Podstawy Geometrii, PWN Warszawa 1970.
3. H.S.M. Coxeter, Wstęp do Geometrii Dawnej i Nowej, PWN Warszawa 1967
4. F.P. Preparata i M.I. Shamos, Geometria Obliczeniwa. Wprowadzenie, Helion Gliwice
5. M.de Berg, M.van Kreveld, M. Overmas i O. Schwarzkopf, Geometria Obliczeniowa.
Algorytmy i Zastosowania, W N-T Warszawa 2007.
6. A. Okabe, B. Boots, K. Sugihara I Sung Nok Chiu, Spatial Tessellations. Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, New York 2000.
7. http://www.qhull.org

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

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Sposób i tryb wyrównania zaległości powstałych wskutek nieobecności na zajęciach student uzgadnia bezpośrednio z osobą prowadzącą odpowiednie zajęcia