Abschnittsübersicht

  • Allgemeines

    Alles einklappen Alles aufklappen

  • Vorlesung Algorithmen für geographische Informationssysteme

    Umfang: 5 ECTS, 2+2 SWS [T:2,P:0]
    Zeit und Ort: Vorlesung: donnerstags, 10:15–11:45 Uhr, M2, SE III (ab dem 27.4.23)
    Übung: montags, 10:15–11:45 Uhr, M2, SE II (ab dem 8.5.23)

    Die Veranstaltung entfällt an den folgenden Tagen:
    V: 11.5., 18.5., 8.6.
    Ü: 1.5., 29.5.
    Mdl. Prüfungen:   tba
    Zielgruppe: Master Informatik, Master Mathematik, Master Computational Mathematics, Master Luft-und Raumfahrtinformatik
    Dozent: Prof. Alexander Wolff
    Übung: Diana Sieper

    Kursinhalte

    Diese Vorlesung befasst sich mit den algorithmischen Grundlagen geographischer Informationssysteme (GIS) und deren Anwendung in ausgewählten Problemen bei der Erfassung, Verarbeitung, Analyse und Präsentation raumbezogener Information. Im Vordergrund stehen Verfahren der diskreten und kontinuierlichen Optimierung. Zu den besprochenen Anwendungen gehören die Erstellung digitaler Höhenmodelle, die Arbeit mit GPS-Trajektorien, Aufgaben der räumlichen Planung sowie die kartographische Generalisierung.

    Voraussetzung, Übung & Prüfung

    Die Vorlesung richtet sich an Studierende im Master-Studiengang Informatik sowie Studierende verwandter Disziplinen (Mathe, Geografie, ...). Grundlagenkenntnisse in Algorithmen und Datenstrukturen werden vorausgesetzt.

    Es gibt wöchentliche Übungsblätter zu Verfahren und Algorithmen aus der Vorlesung, mit Aufgaben wie z.B.:
    • Formalisierung eines Problems,
    • Berechnungen ("zu Fuß", kleinere Programme schreiben),
    • Fragen zur Theorie.
    Bearbeitung in 2er-Gruppen ist erlaubt und bevorzugt; einreichen über WueCampus. Bearbeitungszeit ist in der Regel 1 Woche. Wenn Sie am Ende mindestens 50% der Punkte auf den Übungsblättern haben, erhalten Sie 0,3 Bonus auf Ihre Note (falls Sie die Prüfung bestanden haben).

  • Vorlesungsfolien


    Woche Thema Material
    0 Begrüßungsvideo Playlist
    1 Einführung Geographische Informationswissenschaft
    • Was ist Geoinformatik?
    • Was ist Geodäsie?
    • Kartenabbildungen
    		 Playlist
    Folien: Überblick, Geodäsie
    Mercator puzzle
    2 Map Matching, Ansatz 1
    • Was ist Map Matching?
    • Hausdorff-Distanz
    • Fréchet-Distanz
    • Map Matching mit Fréchet-Distanz
    		 Playlist
    Folien
    Interactive Fréchet-Distanz-Parameterraum Demo
    Film zur Berechnung des Fréchetabstands
    3 Map Matching, Ansatz 2
    • Map Matching nach Newson & Krumm (Einführung)
    • Maximum-Likelihood Explanation (MLE)
    • Markov Chains
    • Hidden Markov Models
    • Map Matching nach Newson & Krumm (diesmal wirklich)
    		 Playlist
    Folien: Newson & Krumm, HMM-Beispiel
    4 Vereinfachung von Streckenzügen
    • Kartografische Generalisierung
    • Der Algorithmus von Douglas-Peucker
    • Der Algorithmus von Imai-Iri [20.07.: Pseudocode sichtbar gemacht]
    • Der Algorithmus von Chan-Chin
    • Zusammenfassung und Ausblick
    		 Playlist
    Folien
    5 Automatisierte Beschriftungsplatzierung
    • Einführung
    • Beschriftungskriterien nach Imhof
    • Problemstellung
    • Ein Greedy Algorithmus
    • Ein Approximationsalgorithmus
    		 Playlist
    Folien
    6 Terrains
    • Einführung
    • Raster vs. TIN
    • Sichtbarkeitsbereich
    • Berechnung im diskreten und kontinuierlichen Fall
    		 Folien
    Druckversion
    7 Clustering
    • Einführung
    • DBSCAN: Definition und Laufzeitbehauptung
    • "Faster DBSCAN": Algorithmus von De Berg, Gunawan, Roeloffzen
      [21.7.: erwähnt, dass DT von n Punkten nur O(n) Kanten hat]
    		 Playlist
    Folien
    Druckversion
    externe Diskussion
    8 Methode der kleinsten Quadrate (Least Squares Adjustment)
    • Einführung
    • historischer Kontext
    • Definitionen
    • Gauß-Normalgleichung
    • Beispiel: Höhenmessungen
    		 Playlist
    Folien
    9 Randbeschriftungen
    • Einführung
    • Beschriftungen mit po-Leadern
    • Sweepline-Algorithmus
    • DP für beliebige Zielfunktion [nachträgliche Änderung: BAD -> T]
    		 Folien
    Druckversion
    10 Kartogramme
    • Einführung
    • Diffusionskartogramme
    • Kreiskartogramme
    • Rechteckskartogramme
    		 Folien
    Druckversion
    11 Ausgleichen trotz Ausreißern
    • Einstiegsbeispiel
    • RANSAC-Algorithmus
    • Wahl der Steuerparameter
    		 Folien

  • Übungsblätter