Kapitel 0 – Einführung
Folien: 📄 00-intro.pdf
Das Einführungskapitel ist rein organisatorisch: Wer liest, wann und wo, wie man den Schein und die Note bekommt und was inhaltlich kommt.
Dozent
Prof. Dr. Georg Umlauf, Institut für Optische Systeme, HTWG Konstanz – Schwerpunkte Computergrafik und geometrische Algorithmen. Büro E 407.
Termine
| Veranstaltung | Zeit | Raum |
|---|---|---|
| Vorlesung | Montag 14:00–15:30 | F 023 |
| Praktikum | Montag 15:45–17:15 | F 033 |
Folien gibt es kapitelweise im Moodle-Kurs, ebenso das Material und die Deadlines für die Praktikumsaufgaben.
Praktikum
- Programmierübungen in C++ mit OpenGL. Die Folien sagen noch Qt6; das aktuelle Template ist auf SDL3 und Dear ImGui umgestellt.
- Aufgabenblätter und Deadlines stehen im Moodle.
- Ablauf: Jede:r löst die Aufgaben einzeln und stellt die Lösung dann dem Professor vor und diskutiert sie mit ihm.
- Keine Teamabgaben und keine Kopien existierender Lösungen. Man muss also jede Zeile seines Codes erklären können.
Die vier Praktikumsaufgaben
| # | Thema | Kapitel | Deadline |
|---|---|---|---|
| 1 | Konvexe Hülle in 2D: Graham's Scan und Jarvis' March | §2 | 02.11.2026 |
| 2 | Schnitt von Liniensegmenten: iso-orientierte Segmente | §3 | 23.11.2026 |
| 3 | Bereichssuche: 2d-Bäume | §4 | 21.12.2026 |
| 4 | Delaunay-Triangulierung: randomisierter Algorithmus | §5 | 18.01.2027 |
Prüfung
- Unbenoteter Schein: erfolgreiche, eigenständige Lösung der Praktikumsaufgaben.
- Benotete Prüfung: mündlich, Einzeltermin im Prüfungszeitraum (ca. Februar). Die Terminliste kommt etwa im Dezember/Januar ins Moodle.
Weil die Prüfung mündlich ist, lohnt es sich, nicht nur die Algorithmen zu kennen, sondern auch Begründungen: Warum ist das korrekt? Warum diese Laufzeit? Was passiert in Sonderfällen?
Inhalte der Vorlesung
| § | Thema |
|---|---|
| 0 | Einführung |
| 1 | Motivation, Grundlagen |
| 2 | Konvexe Hüllen in 2D |
| 3 | Schnitt von Liniensegmenten |
| 4 | Bereichsanfragen: kd-Bäume, Range-Trees, Ball-Trees |
| 5 | Voronoi-Diagramme & Delaunay-Triangulierungen |
| 6 | Punktlokalisierung |
| 7 | Polygon-Triangulierung |
| 8 | Konvexe Hüllen in 3D |
| 9 | Triangulierung von Punktwolken |
Literatur
- M. de Berg, O. Schwarzkopf, M. van Kreveld, M. Overmars: Computational Geometry – Algorithms and Applications, Springer. Das Hauptlehrbuch, auf dem auch viele Abbildungen der Folien basieren. Die konvexe Hülle ist dort Kapitel 1.
- F. P. Preparata, M. I. Shamos: Computational Geometry – An Introduction, Springer, 2. Aufl. 1988. Der Klassiker.
- R. Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen, Springer, 2. Aufl. 2005. Ein deutschsprachiges Lehrbuch.