Mathesis Wiki

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Gebirgsrouten ======

===== Teilnehmer =====

Magdalena Schürks, \\
Anton Raasch und \\
Peter Bunse


===== Projektidee =====

Hier soll es, wie der Name schon sagt, um optimale Gebirgsrouten gehen. Das Ziel ist, mit realen Geodaten optimale Routen durch existierende Gebirgszüge zu finden. Dabei sollen unterschiedliche Verkehrsträger betrachtet werden: Wanderer zum Beispiel zum Anfang. Später sollen Schienen- und Pkw-Routen generiert werden. Dabei sollen auch Brücken und Tunnel erstellt werden und auch unter dem Kostenpunkt betrachtet werden, sodass so wenig wie möglich und so viel wie nötig ausgegeben werden soll. Es soll auch erkannt werden, wann es unumgänglich ist Brücken/Tunnel zu bauen.\\
=====Quellen/Literatur=====

https://open-elevation.com/ \\
https://www.koordinaten-umrechner.de/ \\
https://e4ftl01.cr.usgs.gov/MEASURES/SRTMGL1.003/2000.02.11/\\

=====Projektplanung=====

1. vernünfitge Datensätze zu Geodaten finden:
Programm ruft Website auf (https://www.koordinaten-umrechner.de/) um Ortskoordinaten zu finden\\
open street map mit open elavation\\
2. Daten einlesen (und gegebenenfalls umwandeln)\\
2.1 input Möglichkeit(maybe Programm liest Webdatenbank aus)\\
2.1.1 Start und Zielpunkt und bedingtes quadrat zwischen ihnen\\
2.2 Umarbeitung der daten zu nutzbaren Datensätzen(Gelände,Steigung,Bodenmaterialien)\\
3. Graphisch darstellen (output n Form einer Karte)\\
3.1 muss veränderbar sein und über die daten erstellbar sein\\

4. Wegoptimierung(unter gegebenen Vorgaben)\\
4.1 Geschwindigkeit?\\
4.1.1 Steigung\\
4.2 Strecke?\\
4.2.1 ein Start ein Zielpunkt\\ 
4.3 Kosten?\\
4.3.1 Steigung\\
4.3.2 Streckenlänge\\
4.3.3 Bodenmaterialien?\\






=====Protokoll=====

[[ws2425:gebirgsrouten:Protokoll]]

=====Dokumentation=====


=====Einführung=====

Eine Einführung stellt die grundsätzlichen Ideen, Ziele, Fragen eures Projekts vor und stellt sie in
einen wissenschaftlichen Zusammenhang:

===== Ziel des Projekts =====

Das Ziel dieses Projekts ist die Entwicklung eines Algorithmus zur optimalen Routenplanung in hochalpinen Regionen unter Verwendung realer Geodaten. Zu Beginn wurde der Höhenunterschied als einziger Optimierungsparameter für die Streckenführung verwendet. Später wurden der zusätzliche Faktor der horizontalen Streckenlänge, in die Modellierung integriert, um eine praxisnahe und leistungsfähige Lösung zu gewährleisten. Durch die iterative Verbesserung der Algorithmen wurde das System weiter optimiert, um eine möglichst effiziente und realitätsnahe Berechnung zu ermöglichen.

Zusätzlich sollte das System durch eine grafische Benutzeroberfläche intuitiv bedienbar sein und verschiedene Eingabeoptionen bieten. Dies schließt die manuelle Eingabe von Start- und Zielkoordinaten sowie die interaktive Auswahl auf einer Karte per Mausklick mit ein. Die Entwicklung eines Visualisierungssystems zur Darstellung der Routen und Höhenprofile war ein weiteres zentrales Ziel des Projekts.

===== Motivation =====

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 =====
1. Datenbeschaffung (November 2024): Identifikation geeigneter Höhenmodelle und Geodatenquellen

2. Algorithmusentwicklung (Dezember 2024 - Januar 2025): Implementierung des Dijkstra-Algorithmus und Anpassung an Höhenmetriken

3. Optimierung und Tests (Februar 2025): Verbesserung der Berechnungseffizienz und Validierung der Ergebnisse

4. 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
===== 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

===== 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, Rettungsdienste)
  * Optimierung der Laufzeit für große Kartenbereiche durch effizientere Algorithmen
Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Seiten-Werkzeuge
