Digital Tourism Blog

Wenn wir wissen wollen, ob der Chiemsee in Oberbayern liegt oder welche Unterkünfte – ruhig gelegen und fußläufig vom Seeufer entfernt – für unseren nächsten Urlaub in die engere Auswahl zu ziehen sind, greifen wir aus Gewohnheit zu Google Maps oder konsultieren ganz „old style“ die Landkarte oder den Ortsplan und haben die Antwort quasi auf den ersten Blick parat. Was rein visuell kognitiv von unserem Hirn in Blitzesschnelle erfasst und verarbeitet wird, muss einem Computersystem per Rechenvorschrift erst beigebracht werden. Das ist gar nicht so einfach. Auf welche Dinge geachtet werden muss, soll im Folgenden näher betrachtet werden.

Grundlage aller geografisch-geometrischen Fragestellungen ist die Verortung: Wo befindet sich ein Objekt? Wir beschränken uns der Einfachheit halber noch auf die Erde. Wer weiß – möglicherweise müssen wir irgendwann mal Flugbahnen und geografische Angaben auf anderen Planeten noch mit einbeziehen. Typischerweise werden Positionsangaben als Koordinaten in einem Koordinatensystem definiert. Und hier beginnt schon das erste Problem: Spätestens seit dem Mittelalter hat sich das Wissen durchgesetzt, dass die Erde eine Kugel ist (genauer: ein Ellipsoid) und keine flache, zweidimensionale Scheibe. Das bedeutet allerdings, dass ein Punkt oder Ort auf der Kugel zur Darstellung (oder auch zur einfacheren geometrischen Berechnung) auf eine zweidimensionale Fläche (Bildschirm oder Karte) projiziert werden muss.

Erdmodelle und Koordinatensysteme

Ein exaktes Erdmodell und ein darauf projiziertes Koordinatensystem spielen dann eine elementare Rolle, wenn es darum geht, zu bestimmen, wie weit Punkte auseinanderliegen oder wie groß eine Fläche ist. Voraussetzung ist, dass die Beschreibung des Erdkörpers möglichst exakt ist. Weit verbreitet und de facto Standard in der Geodäsie ist hier das WGS-84-Referenzmodell. Durch die Angabe der Koordinaten in Form von geografischer Breite (Latitude) und geografischer Länge (Longitude) lässt sich jeder Punkt auf dem Erdellipsoiden beschreiben (zum Beispiel 47.77 / 12.45 für Grassau). Doch Vorsicht, was auf dem ersten Blick nach einer Punkt-Koordinate mit x/y-Wert im allseits bekannten kartesischen Koordinatensystem aussieht, entpuppt sich als Grad-Gitternetz ausgehend vom Erdellipsoid-Mittelpunkt in Richtung Pole und in Richtung Meridian. Das bedeutet konkret, dass die Fläche zwar begrenzt ist, es aber – wenn man es genauer betrachtet – zwei gerade Strecken zwischen zwei Punkten existieren (lapidar gesprochen: links um die Erde oder rechts rum). Und nicht immer ist auf den ersten Blick klar, was kürzer ist. Das Gute ist: Je kleiner die betrachtete Distanz ist, desto mehr nähern wir uns einem orthogonalen Koordinatensystem an, mit dem wir (unserer Schulmathematik sei Dank) ganz gut umgehen können. Hier reicht es meistens einen konstanten Umrechnungsfaktor von Grad auf Kilometer einzusetzen – und zwar pro Longitude und Latitiude. In Deutschland entspricht ein Längengrad (West–Ost) etwa 71,44 Kilometer, ein Breitengrad (Nord–Süd) etwa 111,13 Kilometer. Hiermit lässt sich dann recht einfach ein Abstand berechnen (ja, da war doch was: Satz des Pythagoras: a² + b² = c²).

Beispiel Abstand zwischen Grassau (47,77 / 12,45) und Prien (47,85 / 12,34)

Distanz d = Sqrt ( ((47,85 – 47,77) x 111,13 km)2 
                  + ((12,34 – 12,45) x 71,44 km)2 ) 
         = Sqrt ( (9,0504 km)2 + (-7,8584 km)2 ) 
         = 11,99 km

Das kann aber für großräumige Messungen nicht mehr in dieser Form angewendet werden. Allein der Längengrad-Faktor-Unterschied zwischen Hamburg (66 Kilometer) und München (74,16 Kilometer) ist beträchtlich, und je näher wir uns hier den Polen nähern, desto größer wird die Ungenauigkeit. Hier sind dann exaktere Projektionen auf ein kartesisches Koordinatensystem notwendig.

Der Vollständigkeit halber sei noch erwähnt, dass es neben den Koordinaten in Grad-Angaben auch Angaben auf metrischer Basis schon projizierter kartesischer Koordinatensysteme gibt. Bekanntestes Beispiel ist hier das UTM-Gittersystem oder (auf älteren topografischen Karten der Landesvermessungsämter) das Gauss-Krüger-System.

Geometrische Fragestellungen und Objekte

Geografische Fragestellungen lassen sich häufig auf geometrische reduzieren. Hierzu hat das Open Geospatial Consortium (OGC) einige wichtige Standards definiert, die sich auf unterschiedlichsten Systemen wiederfinden. Am wichtigsten ist in dem Zusammenhang sicherlich die Simple Feature Access Spezifikation.

Dort werden zum Beispiel geometrische Objekttypen definiert, wichtige geometrische Methoden, die darauf anwendbar sind und verschiedene Repräsentationsarten von geometrischen Objekten. Die meisten GIS-Systeme, aber auch Datenbanken mit GIS-Unterstützung, orientieren sich stark an diesen Standard und unterstützen die wichtigsten Features.

Geometrische Objekttypen und Methoden

Für die Repräsentation von geometrischen Objekten stehen eine Reihe von Objekttypen (Geometry) zur Verfügung:

• Point: ein einzelner Punkt im Koordinatensystem
• LineString: ein Linienzug bestehend aus Anfangs-, Endpunkt und ggf. mehreren Zwischenpunkten; zum Beispiel für die Darstellung von Touren, Routen etc.
• Polygon: ein geschlossener Linienzug mit gegebenenfalls weiteren enthaltenen geschlossenen Linienzügen; zum Beispiel Flächen, gegebenenfalls mit inneren Aussparungen (See mit Inseln). Interessant ist hierbei, dass es sich bei der Erdoberfläche um eine mathematische Sphäre, einer geschlossenen Mannigfaltigkeit (also quasi ohne Rand), handelt und somit durch einen geschlossenen Linienzug zwei Polygone beschrieben werden: „außen“ oder „innen“. Zur Feststellung, welche Fläche gemeint ist, muss der äußere Linienzug immer entgegen dem Uhrzeigersinn orientiert sein, während der innere Linienzug im Uhrzeigersinn verläuft.
• Außerdem existieren dazu noch mehrfache Varianten: MultiPoint, MultiLineString, MultiPolygon und letztendlich eine Zusammenfassung mehrerer beliebiger Objekte zu eine GeometryCollection

Auf diese Objekte lassen sich eine Reihe von Methoden und Fragestellungen anwenden. Man kann aus einer oder mehreren Geometrien neue Geometrien erzeugen. Das können die Bounding Box (=Envelope) sein, eine konvexe Hülle, die Schnittmenge oder Vereinigungsmenge mehrerer Geometrien. Aber es kann auch die Frage sein, ob eine Geometrie sich mit einer anderen schneidet (intersects), sie berührt (touches), in ihr enthalten (contains) oder mit ihr identisch (equals) ist, oder auch der kürzeste Abstand zwischen zwei Geometrien (distance).

Repräsentation von Geometrie-Objekten

Auch für die Darstellung von Koordinatendaten gibt es Standards. Verbreitet und vielfach bekannt ist das WKT (Well-known-Text)-Format. Für jeden Geometrietyp ist dabei festgelegt, wie er repräsentiert wird. Beispiele:

POINT (12.443 47.785) für eine Punkt-Koordinate

MULTIPOLYGON (((12.443 47.785 12.576 47.834 12.588 47.832 …)),((…))) für eine Sammlung mehrerer zusammengehöriger Polygone

Eine kompaktere (leichter maschinenlesbare Variante) ist das WKB (Well-known-Binary)-Format. Hierbei wird das Geometrie-Objekt in einem Binärformat gespeichert, dessen textuelle Repräsentation gewöhnlich im Hexcode geschieht. Beispiel:

0x010600000001000000010300000001000000920500008393..

Achtung: Die Reihenfolge der Koordinatenwerte ist im WKT-/WKB-Standard nicht festgelegt. Man spricht hier zwar von x / y als ersten und zweiten Wert, aber bezogen auf die Geo-Koordinaten ist das nicht übertragbar. Hier zeigen sich etablierte Systeme sehr unterschiedlich. Meistens wird auf die spezifizierte Reihenfolge des CRS (Coordinate-Reference-System) zurückgegriffen, doch wenn kein CRS angegeben ist hilft nur die Konsultation der Dokumentation des Systems. Während MySQL und Google Maps die Latitude/Longitude-Reihenfolge präferieren, ist das bei den meisten anderen Systemen (zum Beispiel PostGIS, Oracle) umgekehrt.

Dieses Problem hat GeoJSON, ein weiteres verbreitetes Format zur Geometrie-Repräsentation, nicht. Wie der Name schon sagt, handelt es sich um eine JSON-Repräsentation für Geometrie-Objekte und findet gerne in JSON-basierten APIs Verwendung. Unterstützt werden auch hier die geläufigen Geometrien, und die Reihenfolge der Koordinatenwerte ist hier tatsächlich klar festgelegt: Lon/Lat.

Beispiel:

"geoCenter": { 
    "type": "Point",
    "coordinates": [
        13.22967781,
        52.75439422    
    ]  
}

Der Vollständigkeit halber seien noch die verbreiteten Dateiformate für Geometrie-Inhalte erwähnt: GPS Exchange Format (GPX), Keyhole Markup Language (KML) und auch ESRI-Shapefile.

Im Maschinenraum …

Zurück zu unseren eigentlichen Fragestellungen rund um Geo-Objekte. Viele dieser Probleme lassen sich – wie eingangs erwähnt – rein visuell und kognitiv durch eine Person schnell erfassen, und man neigt unwillkürlich dazu, mit den Schultern zu zucken und sich zu fragen: „Wo ist da das Problem?“. Tatsächlich ist das, was durch die menschliche Wahrnehmung einfach erscheint, technisch gar nicht so trivial lösbar. Gehen wir hier auf ein paar Standard-Use-Cases ein.

Ist ein Geometrie-Objekt in einem Polygon enthalten?

Wir bilden ein Polygon ab und das Geometrie-Objekt, zum Beispiel einen Punkt, und auf  den ersten Blick ist ersichtlich, ob der Punkt im Polygon enthalten ist oder eben nicht.

Wie macht man das technisch? Polygone werden repräsentiert durch eine Folge von Koordinatenpunkten, von denen der letzte Punkt identisch ist mit dem ersten Punkt. Um nun festzustellen, ob ein gegebener Punkt innerhalb des Polygons liegt, muss man einen gedachten (am besten horizontalen nach rechts gerichteten) Strahl, ausgehend vom Punkt, bilden und die (echten) Schnittpunkte zu den das Polygon bildenden Strecken (zwischen zwei benachbarten Punkten) zählen. Bei welchen Strecken zum horizontalen Strahl ein Schnittpunkt existiert, ist nicht so schwer feststellbar: Vereinfacht gesprochen geht man alle Strecken des Polygons durch und prüft genau die Strecken auf „schneidend“, die einen y-Koordinatenpunkt größer und einen y-Koordinatenpunkt kleiner dem y-Wert des zu prüfenden Punktes haben, sowie mindestens einen x-Wert besitzen, der größer dem x-Wert des Punktes ist. Der Schnittpunkt zweier Strecken lässt sich einfach per analytischer Geometrie errechnen. Noch effizienter ist es, wenn wir – wie in unserem Fall – keinen Schnittpunkt benötigen, sondern nur die Information, ob sich zwei Strecken schneiden. Dann reicht es, die relative Orientierung der jeweiligen Streckenpunkte zueinander zu prüfen. Wie auch immer: Ist die Anzahl der Schnittpunkte eines Strahls vom zu prüfenden Punkt aus ungerade, dann befindet sich der Punkt im Polygon.

Aus dem skizzierten Algorithmus kann man schon erkennen, dass die Prüfung bei einem Polygon mit mehreren Millionen Punkten mitunter aufwendig ist – bei der Definition größerer Länder ist diese Größenordnung durchaus üblich. Hier muss wirklich jede einzelne Strecke getestet werden, um dann zu entscheiden, ob der Punkt enthalten ist. Ein erster grober Ausschluss kann aber mithilfe der Minimum Bounding Box erreicht werden, bei der man die jeweils größten und kleinsten x/y-Werte festhält und dann prüft, ob der Punkt überhaupt drin ist. Erst dann muss man in die Detailanalyse gehen.

Finde alle Punkte einer Punktemenge im maximalen Abstand zu einem Punkt (=Umkreissuche)

Um alle Punkte innerhalb eines bestimmten Abstands zu einem Referenzpunkt zu finden, gibt es zwei grundsätzliche Vorgehensweisen – doch nur eine ist effizient umsetzbar.

Ein erster (naiver) Ansatz wäre, sich alle Punkte vorzunehmen, für jeden dieser Punkte die Entfernung zum Referenzpunkt zu berechnen und dann zu entscheiden, ob die Entfernung unterschritten ist. Das funktioniert, hat aber den Haken, dass das Ermitteln der Entfernung eine relativ rechenintensive Operation ist, insbesondere, wenn man dann viele Punkte zu prüfen hat. Wesentlich effizienter ist hier der zweite Ansatz: Man bildet ein Polygon, welches einen Kreis mit dem gegebenen Abstand um den Referenzpunkt darstellt, wendet das Bounding-box-Verfahren an und führt dann für die übrig gebliebenen Kandidaten die oben geschilderte Prüfung durch, ob der Punkt im Polygon enthalten ist. Die eigentliche Entfernung zum Referenzpunkt ist dabei unerheblich.

Letztgenanntes Verfahren lässt sich analog auch für Linienzüge oder Polygone erweitern. Beispielsweise eine Korridorsuche entlang einer gegebenen Route („alle Herbergen mit höchstens 3 Kilometer Abstand entlang einer Radtour“) oder eine Umkreissuche um eine Fläche („alle Restaurants im Umkreis von 5 Kilometer vom Chiemseeufer“).

Günstige und ungünstige Konstellationen

Viele Geo-Fragestellungen drehen sich um die Beziehung zwischen den Geo-Objekten (zum Beispiel das „Enthaltensein“ etc.). Bei großen Datenmengen kommt man nicht umhin, sich die Geometrien schon in optimierten Strukturen zu halten. Auf Datenbank-Ebene sind das oft Indexe, die auf effiziente Suche ausgerichtet sind. Anders allerdings als bei Standarddaten, auf die sich über eine lineare Sortierung effiziente Zugriffsmechanismen abbilden lassen (das kennen wir aus dem täglichen Gebrauch, zum Beispiel das Telefonbuch früher), befinden sich unsere Geo-Objekte auf einer zweidimensionalen Ebene, die hier nicht mehr eine klassische Sortierung hergibt. Insbesondere löst die Sortierung nicht die Frage, ob ein Objekt in einem anderen enthalten ist. Was also tun? Hier kann man leider nur mit Kompromissen hantieren. Relativ effizient funktioniert das Arbeiten mit Rechtecken. Zwischen Rechtecken lässt sich sehr schnell feststellen, ob eines im anderen enthalten ist oder ob sich Rechtecke schneiden. Da genügt es, jeweils die minimalen und maximalen x/y-Werte miteinander zu vergleichen. Außerdem lassen sich Rechtecke in eine günstig geordnete Struktur überführen: dem sogenannten R-Baum (oder in Varianten R⁺/R^*-Baum). Hierbei werden Rechtecke hierarchisch so angeordnet, dass sie immer in übergeordneten Rechtecken komplett „eingeschachtelt“ sind.

Doch was nützt uns das Rechteck, wenn wir es mit Linienzügen und Polygonen zu tun haben? Ganz einfach: Wir ermitteln zu jedem Geo-Objekt zusätzlich auch das dieses umgebende minimale Rechteck (die sogenannte Minimum Bounding Box). Somit lässt sich immerhin schon mal feststellen, welche der Geo-Objekte bei einer Entscheidung, ob sie enthalten sind, ausscheiden. Was aber immer noch notwendig ist: Alle positiven Kandidaten müssen dann tatsächlich en détail geprüft werden, und das kann bei großen Polygonen sehr aufwendig sein. Eine ungünstige Struktur liegt vor, wenn zum Beispiel eine große Menge an Linienzügen existiert, die mehr oder weniger stark diagonal verlaufen oder bei denen zumindest die Bounding Box sehr groß wird. Gleiches gilt für Polygone, die sehr groß sind und wenn dann zudem sehr viele weitere große Polygone mit enthaltenen Bounding Boxes existieren. Allein die Ermittlung, welche von vielen Tausend Regionen in Deutschland (mit circa 1 Million Polygonpunkten) liegen, lässt sich nur mehr schwer in Echtzeit mit den genannten Algorithmen und Strukturen durchführen. Hier ist es notwendig, derartige Relationen dann vorzuberechnen und explizit festzulegen.