Module also offered within study programmes:
General information:
Name:
Geometria komputerowa
Course of study:
2018/2019
Code:
JIS-2-016-GK-s
Faculty of:
Physics and Applied Computer Science
Study level:
Second-cycle studies
Specialty:
Grafika komputerowa i przetwarzanie obrazów
Field of study:
Applied Computer Science
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
prof. dr hab. Kaprzyk Stanisław (kaprzyk@wfitj12e.ftj.agh.edu.pl)
Academic teachers:
prof. dr hab. Kaprzyk Stanisław (kaprzyk@wfitj12e.ftj.agh.edu.pl)
Module summary

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

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
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 Activity during classes
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 Activity during classes
Skills
M_U001 Student potrafi dokonać krytycznej analizy problemu i sformułować odpowiedni model w języku abstrakcyjnych pojęć geometrycznych IS2A_U01, IS2A_U04 Report,
Execution of laboratory classes
M_U002 Student potrafi zaprojektować, uruchomić i ocenić efektywność obliczeniową kodu komputerowego w praktycznych zastosowaniach IS2A_U02, IS2A_U04 Participation in a discussion,
Execution of laboratory classes
Knowledge
M_W001 Student zna klasyczne podstawy geometrii Euklidesa i posiada wiedzę o abstrakcyjnych obiektach z geometrii Hilberta IS2A_W01, IS2A_W03 Activity during classes
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 Participation in a discussion,
Execution of exercises,
Execution of laboratory classes
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
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ć - - + - - - - - - - -
Skills
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 - - + - - - - - - - -
Knowledge
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 + - - - - - - - - - -
Module content
Lectures:
  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.

Laboratory classes:
  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

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 104 h
Module ECTS credits 4 ECTS
Participation in lectures 30 h
Participation in laboratory classes 30 h
Realization of independently performed tasks 22 h
Preparation of a report, presentation, written work, etc. 22 h
Additional information
Method of calculating the final grade:

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.

Prerequisites and additional requirements:

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.

Recommended literature and teaching resources:

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

Scientific publications of module course instructors related to the topic of the module:

Additional scientific publications not specified

Additional information:

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