Benutzer-Werkzeuge
ws2425:gebirgsrouten
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen gezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
|
ws2425:gebirgsrouten [2025/03/12 22:32] magdalenaps [Theoriegrundlagen] |
ws2425:gebirgsrouten [2025/03/13 19:36] (aktuell) anton_raasch |
||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| ====== Gebirgsrouten ====== | ====== Gebirgsrouten ====== | ||
| + | https://tubcloud.tu-berlin.de/s/Aw9Zb6qpXZZg6no\\ | ||
| + | {{:ws2425:gebirgsrouten_abgabe_ver.zip|{{:ws2425:gebirgsrouten_abgabe_ver.zip|}}}} | ||
| ===== Teilnehmer ===== | ===== Teilnehmer ===== | ||
| Zeile 16: | Zeile 18: | ||
| https://www.koordinaten-umrechner.de/ \\ | https://www.koordinaten-umrechner.de/ \\ | ||
| https://e4ftl01.cr.usgs.gov/MEASURES/SRTMGL1.003/2000.02.11/\\ | https://e4ftl01.cr.usgs.gov/MEASURES/SRTMGL1.003/2000.02.11/\\ | ||
| + | |||
| + | ===== Requirements ===== | ||
| + | Package Version\\ | ||
| + | --------------- -----------\\ | ||
| + | Bottleneck 1.4.2\\ | ||
| + | contourpy 1.3.1\\ | ||
| + | cycler 0.11.0\\ | ||
| + | fonttools 4.51.0\\ | ||
| + | kiwisolver 1.4.4\\ | ||
| + | matplotlib 3.9.2\\ | ||
| + | mkl_fft 1.3.11\\ | ||
| + | mkl_random 1.2.8\\ | ||
| + | mkl-service 2.4.0\\ | ||
| + | numexpr 2.10.1\\ | ||
| + | numpy 2.1.3\\ | ||
| + | packaging 24.2\\ | ||
| + | pandas 2.2.3\\ | ||
| + | pillow 11.0.0\\ | ||
| + | pip 24.2\\ | ||
| + | ply 3.11\\ | ||
| + | pyglet 2.1.2\\ | ||
| + | pyparsing 3.2.0\\ | ||
| + | PyQt5 5.15.10\\ | ||
| + | PyQt5_sip 12.13.0\\ | ||
| + | python-dateutil 2.9.0.post0\\ | ||
| + | pytz 2024.1\\ | ||
| + | scipy 1.14.1\\ | ||
| + | setuptools 72.1.0\\ | ||
| + | sip 6.7.12\\ | ||
| + | six 1.16.0\\ | ||
| + | tornado 6.4.2\\ | ||
| + | tzdata 2023.3\\ | ||
| + | wheel 0.44.0\\ | ||
| + | |||
| =====Projektplanung===== | =====Projektplanung===== | ||
| Zeile 70: | Zeile 106: | ||
| Zur Routenberechnung verwenden wir den Dijkstra-Algorithmus, ein klassisches Verfahren zur Bestimmung des kürzesten Pfads in einem Graphen. Dieser Algorithmus wurde erstmals von Edsger W. Dijkstra im Jahr 1956 vorgestellt und bildet eine fundamentale Grundlage der Graphentheorie. | Zur Routenberechnung verwenden wir den Dijkstra-Algorithmus, ein klassisches Verfahren zur Bestimmung des kürzesten Pfads in einem Graphen. Dieser Algorithmus wurde erstmals von Edsger W. Dijkstra im Jahr 1956 vorgestellt und bildet eine fundamentale Grundlage der Graphentheorie. | ||
| - | Der Algorithmus arbeitet auf einem gerichteten, gewichteten Graphen und findet den kürzesten Pfad zwischen einem Startknoten und allen anderen Knoten. In unserem Kontext repräsentieren die Knoten die diskreten Punkte des Höhenmodells, während die Kanten die möglichen Bewegungen zwischen benachbarten Punkten darstellen. (Bild der möglichen Nachbarpunkte) Die Gewichtung der Kanten hängt sowohl von der horizontalen Distanz als auch von den Höhenunterschieden ab. | + | Der Algorithmus arbeitet auf einem gerichteten, gewichteten Graphen und findet den kürzesten Pfad zwischen einem Startknoten und allen anderen Knoten. In unserem Kontext repräsentieren die Knoten die diskreten Punkte des Höhenmodells, während die Kanten die möglichen Bewegungen zwischen benachbarten Punkten darstellen.\\ Die Gewichtung der Kanten hängt sowohl von der horizontalen Distanz als auch von den Höhenunterschieden ab.\\ |
| + | {{:ws2425:ueberpruefungsbereich.png?200|}} | ||
| Die Funktionsweise des Dijkstra-Algorithmus basiert auf einer Buchhaltung über alle überprüften Knoten/ Punkten, dessen Gesamtkosten, Vorgänger und der Frage, ob die niedrigste-möglichen Gesamtkosten für diesen Punkt bereits ermittelt wurden. Außerdem ist eine Prioritätswarteschlange nötig, die nach den geringsten Gesamtkosten sortiert ist. Zu Beginn wird die Zielkoordinate mit Gesamtkosten von unendlich initialisiert, der Startpunkt mit Gesamtkosten von null, da das die Distanz zu sich selbst ist. Anschließend wird der Knoten mit der aktuell geringsten Distanz aus der Warteschlange genommen, und seine Nachbarn werden überprüft. Falls eine neue Route zu einem Nachbarknoten günstiger ist als die bislang gespeicherte, wird der Wert und der Vorgänger aktualisiert, und der Knoten wird in der Warteschlange an eine neue Stelle gesetzt. Dieser Prozess setzt sich fort, bis das Ziel erreicht ist. | Die Funktionsweise des Dijkstra-Algorithmus basiert auf einer Buchhaltung über alle überprüften Knoten/ Punkten, dessen Gesamtkosten, Vorgänger und der Frage, ob die niedrigste-möglichen Gesamtkosten für diesen Punkt bereits ermittelt wurden. Außerdem ist eine Prioritätswarteschlange nötig, die nach den geringsten Gesamtkosten sortiert ist. Zu Beginn wird die Zielkoordinate mit Gesamtkosten von unendlich initialisiert, der Startpunkt mit Gesamtkosten von null, da das die Distanz zu sich selbst ist. Anschließend wird der Knoten mit der aktuell geringsten Distanz aus der Warteschlange genommen, und seine Nachbarn werden überprüft. Falls eine neue Route zu einem Nachbarknoten günstiger ist als die bislang gespeicherte, wird der Wert und der Vorgänger aktualisiert, und der Knoten wird in der Warteschlange an eine neue Stelle gesetzt. Dieser Prozess setzt sich fort, bis das Ziel erreicht ist. | ||
| Zeile 90: | Zeile 127: | ||
| Das System besteht aus mehreren Python-Modulen mit spezifischen Aufgabenbereichen: | Das System besteht aus mehreren Python-Modulen mit spezifischen Aufgabenbereichen: | ||
| - | * config_gebirgsrouten.py: Datenbeschaffung und -verarbeitung | + | * __config_gebirgsrouten.py__: Datenbeschaffung und -verarbeitung |
| - | * dijkstra_gebirgsrouten.py: Implementierung des Dijkstra-Algorithmus zur Routenberechnung | + | * __dijkstra_gebirgsrouten.py__: Implementierung des Dijkstra-Algorithmus zur Routenberechnung |
| - | * heightdifferences_gebirgsrouten.py: Berechnung der Höhenunterschiede zwischen Rasterpunkten | + | * __heightdifferences_gebirgsrouten.py__: Berechnung der Höhenunterschiede zwischen Rasterpunkten |
| - | * multiple_maps_test_gebirgsrouten.py: Testen verschiedener Kartenausschnitte | + | * __multiple_maps_test_gebirgsrouten.py__: Testen verschiedener Kartenausschnitte |
| - | * path_height_calculation_gebirgsrouten.py: Erstellung von Höhenprofilen entlang der Route | + | * __path_height_calculation_gebirgsrouten.py__: Erstellung von Höhenprofilen entlang der Route |
| - | * read_topography_gebirgsrouten.py: Einlesen und Verarbeiten der .hgt-Höhendaten | + | * __read_topography_gebirgsrouten.py__: Einlesen und Verarbeiten der .hgt-Höhendaten |
| - | * show_path_gebirgsrouten.py: Darstellung der berechneten Route und interaktive Benutzerinteraktion | + | * __show_path_gebirgsrouten.py__: Darstellung der berechneten Route und interaktive Benutzerinteraktion |
| + | |||
| + | Zuerst werden topographische Daten mit read_topography_gebirgsrouten.py geladen. Anschließend berechnet heightdifferences_gebirgsrouten.py die Höhenunterschiede. Mit dijkstra_gebirgsrouten.py wird die kürzeste Route zwischen zwei Punkten bestimmt. Path_height_calculation_gebirgsrouten.py analysiert das Höhenprofil der Route, und show_path_gebirgsrouten.py visualisiert den berechneten Weg. Konfigurationen können in config_gebirgsrouten.py angepasst werden. | ||
| ===== Projektergebnisse ===== | ===== Projektergebnisse ===== | ||
| Zeile 105: | Zeile 145: | ||
| * Die Visualisierung der berechneten Route mit farbkodierten Höhenunterschieden | * Die Visualisierung der berechneten Route mit farbkodierten Höhenunterschieden | ||
| * Die Visualisierung des Algorithmusverlaufs | * Die Visualisierung des Algorithmusverlaufs | ||
| + | |||
| + | Vergleich zwischen Google maps Routen und unseren.\\ | ||
| + | {{:ws2425:new_path.png?200 |}} | ||
| + | {{:ws2425:projekt_gebirgsrouten_mapsvergleich3.png?200 |}}\\ | ||
| + | \\ | ||
| + | \\ | ||
| + | \\ | ||
| + | \\ | ||
| + | \\ | ||
| + | \\ | ||
| + | * Zugstrecke\\ | ||
| + | {{:ws2425:path_old_ver.png?200 |}} | ||
| + | {{:ws2425:projekt_gebirgsrouten_mapsvergleich2.png?200 |}}\\ | ||
| + | Fußgänger/Autostrecke\\ | ||
| + | |||
| ===== Fazit und Ausblick ===== | ===== Fazit und Ausblick ===== | ||
| Zeile 110: | Zeile 165: | ||
| Das initiale Ziel der höhenoptimierten Routenplanung wurde erfolgreich umgesetzt. Das System bietet eine interaktive und effiziente Berechnung von Wegen im Gebirge. Potenzielle Erweiterungen umfassen: | Das initiale Ziel der höhenoptimierten Routenplanung wurde erfolgreich umgesetzt. Das System bietet eine interaktive und effiziente Berechnung von Wegen im Gebirge. Potenzielle Erweiterungen umfassen: | ||
| * Integration zusätzlicher Wegkriterien wie Wetterbedingungen und Bodenbeschaffenheit | * Integration zusätzlicher Wegkriterien wie Wetterbedingungen und Bodenbeschaffenheit | ||
| - | * Erweiterung für unterschiedliche Nutzergruppen (z. B. Wanderer, Radfahrer, Rettungsdienste) | + | * Erweiterung für unterschiedliche Nutzergruppen (z. B. Wanderer, Radfahrer, Züge) |
| * Optimierung der Laufzeit für große Kartenbereiche durch effizientere Algorithmen | * Optimierung der Laufzeit für große Kartenbereiche durch effizientere Algorithmen | ||
ws2425/gebirgsrouten.1741815135.txt.gz · Zuletzt geändert: 2025/03/12 22:32 von magdalenaps
Seiten-Werkzeuge
