• Willkommen im Geoclub - dem größten deutschsprachigen Geocaching-Forum. Registriere dich kostenlos, um alle Inhalte zu sehen und neue Beiträge zu erstellen.

Dateiformat für Vektorkarten

A

Anonymous

Guest
Hallo zusammen,

für eine mobile Anwendung möchte ich Landkarten als Vektordaten speichern. Nachdem die Karten doch recht umfangreich sein können, suche ich nach einer Möglichkeit, die Daten so zu speichern, dass beim Darstellen eines Kartenausschnittes die Daten schnell gefunden werden können.
Zum Thema habe ich mir auch schon viele Gedanken gemacht und dabei mal Vor- und Nachteile aufgeschrieben:

1. Die Darstellung soll wie bei gängigen Navi funktionieren:
* kleiner Zoom -> grosser Kartenausschnitt -> wenige Details (Küsten, polit. Grenzen, Autobahnen, größere Städte)
* größerer Zoom -> kleinerer Kartenausschnitt -> mehr Details (gleiche Details wie bei kleinerem Zoom, zusätzlich jedoch kleinere Strassen, evtl. Rad- und Wanderwege, Stromleitungen, etc.)
Damit ergibt sich der Effekt, dass Daten redundant gespeichert werden. Bspw. finden sich Autobahnen dann in den Daten für alle Zoomstufen

2. Um diese Redundanzen zu vermeiden, enthält eine Zoomstufe nur die Daten, die im Vergleich zur nächst geringeren neu hinzugekommen sind. Zum Zeichnen der Karten werden die Zoomstufen dann von der geringsten bis zur aktuellen durchlaufen und die Daten dargestellt.

3. Eine Karte besteht aus mehreren Ebenen. Jede Ebene enthält bestimmte Karteninformationen. So werden Wälder und Gewässer in einer Ebene gespeichert, Strassen in einer neuen, Rad- und Wanderwege in einer weiteren Ebene. Damit lassen sich unerwünschte Kartendaten leicht ausblenden.

Anregungen und Kritiken zu diesen Punkten sind ausdrücklich erwünscht!

Meine Frage zielt jedoch auf etwas anderes ab: Damit nun nicht immer alle Daten durchlaufen werden müssen, möchte ich neben den Ebenen und Zoomstufen noch die Karte in einzelne Ausschnitte, ähnlich den Tiles von OpenStreetMap, aufteilen. Es gibt einen Kartenausschnitt für einen niedrigen Zoom. Für die nächste Zoomstufe wird der Kartenausschnitt unterteilt (bei OSM in Breite und Höhe geteilt). Damit werden die Kartenausschnitte mit zunehmendem Zoom kleiner. Die Folge: Autobahnen würden dann nur in einem großen Ausschnitt (z. B. mit 200 x 200 km) mit niedrigem Zoom gespeichert (-> Vermeidung redundater Daten). Zum Zeichnen eines Ausschnitts von 100m x 100m müssen damit aber die Autobahndaten des großen Ausschnitts durchlaufen werden.

Hat hier jemand einen besseren Vorschlag? Wie ist das bei den "großen" System von Garmin, Navigon, etc. gelöst?

Ich hoffe, ich konnte meine Überlegungen halbwegs verständlich rüberbringen und möchte mich schon jetzt für jede Anregung / Kritik / Antwort bedanken.


VG,

Markus
 

kiozen

Geomaster
cipher1978 schrieb:
1. Die Darstellung soll wie bei gängigen Navi funktionieren:
* kleiner Zoom -> grosser Kartenausschnitt -> wenige Details (Küsten, polit. Grenzen, Autobahnen, größere Städte)
* größerer Zoom -> kleinerer Kartenausschnitt -> mehr Details (gleiche Details wie bei kleinerem Zoom, zusätzlich jedoch kleinere Strassen, evtl. Rad- und Wanderwege, Stromleitungen, etc.)
Damit ergibt sich der Effekt, dass Daten redundant gespeichert werden. Bspw. finden sich Autobahnen dann in den Daten für alle Zoomstufen

2. Um diese Redundanzen zu vermeiden, enthält eine Zoomstufe nur die Daten, die im Vergleich zur nächst geringeren neu hinzugekommen sind. Zum Zeichnen der Karten werden die Zoomstufen dann von der geringsten bis zur aktuellen durchlaufen und die Daten dargestellt.

Das ist nur ein vermeintlicher Gewinn, da du bei einem gröberen Zoom erst die ganze Polylinie einlesen musst, um sie dann vereinfacht darzustellen. Z.B. eine Autobahn durch DE mit allen Details ist eine menge Holz. Bei einer Deutschlandübersicht braucht es aber nur sehr einfache und grobe Linien. Den Speicher, den Du sparen würdest, verheizt du damit in Form von Programmcode und Zyklen.

cipher1978 schrieb:
3. Eine Karte besteht aus mehreren Ebenen. Jede Ebene enthält bestimmte Karteninformationen. So werden Wälder und Gewässer in einer Ebene gespeichert, Strassen in einer neuen, Rad- und Wanderwege in einer weiteren Ebene. Damit lassen sich unerwünschte Kartendaten leicht ausblenden.

So wird es ja auch schon gemacht. Jedes Polygon bzw jede Polylinie hat einen Typ. Die Typen werden in einer vorbestimmten Reihenfolge gezeichnet. Einen Typen zu überspringen oder alle Elemente vom gleichen Typ zu extrahieren ist kein Problem. Das macht aber nur bei Polylinien Sinn.

cipher1978 schrieb:
Hat hier jemand einen besseren Vorschlag? Wie ist das bei den "großen" System von Garmin, Navigon, etc. gelöst?

http://tinyurl.com/38jsntw

http://www.navit-project.org/

Viel Spaß beim Lesen

Oliver
 
OP
A

Anonymous

Guest
Danke für Kommentare. Über die Beschreibung des Garmin-Formats bin ich auch schon gestolpert. Leider finde ich die Beschreibung etwas ungenau. Hier wird zwar erklärt, dass für jede Zoomstufe ein Kartenlevel existiert. Es wird aber nicht erklärt, wie die Karten eingeteilt wird. Beim Lesen hörte sich das für mich an, also ob der geringste Zoom die komplette Karte abdeckt.
Ich hatte auch schon mal den Gedanken, Kartenausschnitte für jede Zoomstufe zu berechnen und die darin enthaltenen Objekte an den Rändern zu beschneiden (wobei sich die Ausschnitte um 10% überlappen sollen) und vorzuverarbeiten (Douglas-Peucker um die Knoten zu verringern, Sorten für schnelleres und leichteres Rendering, etc.). Hatte diesen Ansatz aber dann verworfen, da die Karten dann richtig schön groß werden.
Navit werd ich mir auf jeden Fall mal genauer ansehen.

thx,

Markus
 

kiozen

Geomaster
cipher1978 schrieb:
Danke für Kommentare. Über die Beschreibung des Garmin-Formats bin ich auch schon gestolpert. Leider finde ich die Beschreibung etwas ungenau. Hier wird zwar erklärt, dass für jede Zoomstufe ein Kartenlevel existiert. Es wird aber nicht erklärt, wie die Karten eingeteilt wird. Beim Lesen hörte sich das für mich an, also ob der geringste Zoom die komplette Karte abdeckt.

Die Doku ist an für sich recht akkurat. Lediglich bei der Polygondekodierung haben sich Fehler eingeschlichen.

Man darf sich allerdings nicht von den verschiedenen Definitionen für Zoomstufen verwirren lassen. Da ist zum einen die Zoomstufe, wie man sie aus MapSource kennt. Hier wird die Skalierung logarithmisch in ~30 Stufen geändert. In den IMG Dateien gibt es in der Regel so um die 3 bis 5 Stufen. Jede dieser Stufen hat eine bestimmt Auflösung in Bits. Und anhand dieser Bits wird die jeweilige MapSpource Zoomstufe auf die IMG interne Zoomstufe (map level) reduziert. Der Rest ist reine Skalierung.

Jeder "map level" beinhaltet die komplette Karte, und ist damit unabhängig von den anderen "map levels". Wobei die Daten in den oberen Levels deutlich reduziert sind. Nicht nur durch die geringere Auflösung sondern auch durch die Vereinfachung der Kartenstruktur.

Wenn Du meine persönliche Meinung hören willst, verschwendest Du deine Zeit, wenn Du um jeden Preis die Datenmenge von Redundanz befreien willst. In Zeiten von 8-16GB SD Ram ist die Dateigröße von untergeordnetem Interesse. Heute stellt das schnelle Darstellen von möglichst vielen Details, bei möglichst geringen Zyklen- und Arbeitsspeicherverbrauch, die weitaus größere Herausforderung dar. Ob die resultierende Datei 2 oder 3 GB hat ist fast schon egal.

Außerdem würde ich Dir empfehlen bei Garmin genau hinzusehen und zu überlegen, warum Garmin es gerade so und nicht anders gemacht hat. Im Gegensatz zum Rest der Firmware bietet das IMG Format im Kern nur wenig Anlass zur Kritik. Die Materie ist sehr komplex und vieles was bei Garmin auf den ersten Blick komisch oder schlecht aussieht ist bei näherem Hinsehen durchaus sinnvoll. Einiges ist aber auch schlicht überflüssige Altlast, weil auch Garmin im Lauf der Zeit einige seiner Konzepte an die Realität anpassen musste.

Ich würde an deiner Stelle die bestehenden quelloffenen Decoder sehr genau analysieren, um ein Gefühl dafür zu bekommen was Arbeitsspeicher und Zyklen frisst und wie sich beides sparen ließe, wenn das Format anders wäre. Auch wenn im Encoder und im Format die Intelligenz steckt, so bestimmt immer der Decoder, ob ein Format was taugt. Und codiere den ruhig auf einem ollen PDA mit 200-400MHz. ö.ä. Dann merkst Du sehr schnell wo die Grenzen sind.

Grüße

Oliver
 
Oben