Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ws2425:gebirgsrouten [2025/03/12 22:09]
magdalenaps [Zwischenziele]
+++ ws2425:gebirgsrouten [2025/03/13 19:36] (aktuell)
anton_raasch
@@ Zeile 1: / Zeile 1: @@
 ====== Gebirgsrouten ======
+https://tubcloud.tu-berlin.de/s/Aw9Zb6qpXZZg6no\\
+{{:ws2425:gebirgsrouten_abgabe_ver.zip|{{:ws2425:gebirgsrouten_abgabe_ver.zip|}}}}
 ===== Teilnehmer =====
@@ Zeile 16: / Zeile 18: @@
 https://www.koordinaten-umrechner.de/ \\
 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=====
@@ Zeile 66: / Zeile 102: @@
 Die Planung von Wegen und Routen in komplexen topografischen Gegebenheiten stellt eine herausfordernde Optimierungsaufgabe dar. Während herkömmliche Navigationssysteme vor allem Straßennetzwerke betrachten, sind in Gebirgsregionen andere Parameter, wie die Minimierung von Höhenmetern entscheidend. Während das primäre Anwendungsgebiet des Projekts zunächst auf Wanderwege fokussiert ist, könnte der entwickelte Algorithmus in Zukunft auch für infrastrukturelle Planungen im Schienen- oder Straßenbau eingesetzt werden.
+===== Theoriegrundlagen =====
+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.\\ 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.
+Da unser Projekt in einer gebirgigen Umgebung arbeitet, wurde der Algorithmus angepasst, um Höhenunterschiede stärker zu gewichten und so die topografische Realität besser zu erfassen. Eine zentrale Herausforderung bestand darin, realistische Bewegungsmöglichkeiten abzubilden. In diesem Zusammenhang wurden verschiedene Gewichtungsstrategien erprobt, um eine optimale Balance zwischen Höhen- und Streckenoptimierung zu finden. Eine naive Implementierung des Algorithmus, die nur den Höhenunterschied minimiert, führt zu extrem langen und ineffizienten Routen.
+Ein weiteres wichtiges Element des Projekts war die Topographiedatenverarbeitung. Die SRTM-Daten enthalten Höhenangaben in einem regelmäßigen Rasterformat, das in Python verarbeitet wurde. Dabei mussten die Koordinaten interpretiert und in ein Graphensystem überführt werden, damit die Algorithmen darauf angewendet werden konnten.
 ===== Zwischenziele =====
 . Datenbeschaffung (November 2024): Identifikation geeigneter Höhenmodelle und Geodatenquellen
@@ Zeile 74: / Zeile 122: @@
 . Finalisierung und Präsentation (März 2025): Letzte Anpassungen und Dokumentation des Projekts
+===== Projektstruktur =====
+Das System besteht aus mehreren Python-Modulen mit spezifischen Aufgabenbereichen:
+  * __config_gebirgsrouten.py__: Datenbeschaffung und -verarbeitung
+  * __dijkstra_gebirgsrouten.py__: Implementierung des Dijkstra-Algorithmus zur Routenberechnung
+  * __heightdifferences_gebirgsrouten.py__: Berechnung der Höhenunterschiede zwischen Rasterpunkten
+  * __multiple_maps_test_gebirgsrouten.py__: Testen verschiedener Kartenausschnitte
+  * __path_height_calculation_gebirgsrouten.py__:  Erstellung von Höhenprofilen entlang der Route
+  * __read_topography_gebirgsrouten.py__:  Einlesen und Verarbeiten der .hgt-Höhendaten
+  * __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 =====
+Die finale Version des Programms erlaubt:
+  * Das Einlesen und Verarbeiten von Höhendaten
+  * Die Routenberechnung unter Berücksichtigung von Höhenunterschieden und Streckenlängen
+  * Die interaktive Auswahl von Start- und Zielpunkten
+  * Die Visualisierung der berechneten Route mit farbkodierten Höhenunterschieden
+  * 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 =====
+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
+  * Erweiterung für unterschiedliche Nutzergruppen (z. B. Wanderer, Radfahrer, Züge)
+  * Optimierung der Laufzeit für große Kartenbereiche durch effizientere Algorithmen

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge