Wie beschreibe ich eine besondere Beziehung zwischen verbundenen Kanten?

Stellen Sie sich diese einfache Situation vor, in der drei Kanten an einem Knoten verbunden sind:

Ich möchte eine kurze und klare Beschreibung der Beziehung zwischen A und B schreiben, die sie von der Beziehung zwischen A und C unterscheidet. Etwas wie „Wenn Sie den Knoten im Uhrzeigersinn durchqueren, ist A benachbart? zu B, aber A ist nicht benachbart? zu C. ” Aber es ist nicht wirklich Nachbarschaft.

Anders gesagt: Stellen Sie sich vor, Sie stehen auf dem Knoten und stehen in Richtung A. Sie drehen sich im Uhrzeigersinn. Die nächste Kante, zu der Sie kommen, ist B, nicht C.

Gibt es eine Möglichkeit, diese Beziehung zwischen A und B prägnanter, formaler oder korrekter zu beschreiben, als ich oben geschrieben habe?

Es muss gerichtet sein (eine Beziehung dieses Typs besteht im Uhrzeigersinn von A und eine andere im Gegenuhrzeigersinn). Und es muss auf Fälle skaliert werden, in denen mehr als drei Kanten am Knoten verbunden sind. Vielleicht hat es etwas mit Routing zu tun? (Ich denke darüber im Zusammenhang mit Straßennetzen nach.)

Zwei Ansätze, die ich bereits ausprobiert habe, mit denen ich aber noch nicht weit gekommen bin:

1. 9IM-ähnliche Topologie-Referenzen : Ich habe mir das DE-9IM angesehen , und obwohl ich kein Mathematiker bin, kann ich anhand der Diagramme und Begriffe immer noch erkennen, dass es diese Art von Beziehung nicht abdeckt. Ich finde es noch nicht in den Topologiebeschreibungen der ESRI-Hilfe oder der Oracle-Hilfe . (Vielleicht gibt es da etwas, aber ich finde es einfach noch nicht!)

2. Gesichter : Ich habe damit herumgespielt, dass das Gesicht auf der „Nordseite“ von A möglicherweise auch von B, aber nicht von C begrenzt wird. Wie Sie in der Abbildung hier sehen können, ist dies jedoch nicht immer der Fall. Stellen Sie sich vor, mein Diagramm ist ein Auszug aus einem Straßennetz, in dem A und C Ausfallstraßen und B eine kurze Sackgasse sind.

Ich vermute, es gibt möglicherweise keinen einzigen Begriff für das, was ich zu sagen versuche. Zumindest möchte ich in der Lage sein, eine solche Beziehung einfacher zu beschreiben als oben. Dies ist eine plattformunabhängige Frage. Im Moment suche ich nur nach den richtigen Worten. Später werde ich versuchen, das Konzept in Python (pyqgis oder arcpy) in einem Shapefile zu implementieren, sodass Antworten mit diesem Endpunkt besonders interessant, aber nicht notwendig sind.

Ich weiß, dass ich hier etwas zu spät zur Party komme, aber das ist ziemlich interessant, und ich hoffe, dass meine Antwort von Nutzen sein kann.

Was Sie fragen, ist eine qualitative Beziehung; das oft ignorierte Geschwister der quantitativen Beziehung. Qualitatives Denken kommt in der Geowissenschaft häufig vor. Beispielabfragen umfassen: Welche Pakete grenzen an dieses an? Welche Merkmale befinden sich innerhalb der Überlappung von Region A und Region B? Welche Regionen sind konkav? Welche Straße befindet sich links? Die Beziehungen sind: neben, innerhalb, konkav und links von. Qualitative Abfragen werden im Vergleich zu quantitativen Fragen, die größer, kürzer oder zahlreicher sind, häufig übersehen oder unterbewertet.

Eine qualitative Beziehung, die zwei Eingaben benötigt, wird als binäre Beziehung bezeichnet. Hierfür gibt es zwei gebräuchliche Notationen: - isLeftOf (A, B) Dies ist die Präfixnotation. - A isLeftOf B Dies ist die Infix-Notation.

In den obigen Beispielen gab es auch eine unäre Beziehung: isConcave. Diese Beziehung bezieht eine Region auf sich selbst und würde einen booleschen Wert zurückgeben.

Alle räumlichen Prädikate von Egenhofer im 9-Schnittpunkt-Modell (im 9EIM referenziert) sind binäre Beziehungen zwischen zwei Regionen. Sie könnten auch an Randell, Cui und Cohns RCC interessiert sein (http://en.wikipedia.org/wiki/Region_connection_calculus). Die in diesem Untersuchungsbereich angegebenen qualitativen (topologischen) Beziehungen beziehen Regionen auf Regionen, und spätere Arbeiten beziehen Linien auf Regionen und Linien auf Linien. Dies ist jedoch nicht ganz das, wonach Sie suchen.

OK, entschuldigen Sie den Exkurs, aber hoffentlich hilft das beim terminologischen Aspekt Ihrer Frage.

@whuber war auf dem richtigen Weg, die doppelt verbundene Kantenliste (DCEL) vorzuschlagen. Dies ist ein enger Verwandter von kombinatorischen Karten, die in CAD-Systemen häufig unter der Decke verwendet werden, und von geflügelten Kanten. Das Konzept der geflügelten Kante (http://en.wikipedia.org/wiki/Winged_edge) beschreibt, wie der Standard für bekannten Text ein Loch in einem Polygon definiert (http://en.wikipedia.org/wiki/Well-known_text) #Geometric_objects). Beachten Sie auf dem Polygon, dass die Reihenfolge der äußeren Punkte gegen den Uhrzeigersinn und für die inneren Punkte im Uhrzeigersinn ist. Eine kleine Fee, die in dieser Reihenfolge die Grenze entlang ging, sah immer das Innere der Region zu ihrer Linken.

Bei kombinatorischen Karten und DCEL ist der entscheidende Punkt, dass diese Objekte auf einer Oberfläche definiert werden, die orientierbar ist. Wir müssen uns nicht mit den mathematischen Formalitäten befassen - die Idee ist ziemlich einfach: Wenn Sie die Richtung auf der Oberfläche definieren können, wie Sie es mit jedem räumlichen Bezugssystem in einem GIS können, haben Sie eine orientierbare Oberfläche. Wenn Sie also eine Richtung definieren können, können Sie eine Richtungsreihenfolge um einen beliebigen Punkt auf der Oberfläche definieren. Mit der Richtungsreihenfolge können Sie isLeftOf (A, B), isRotationallyAdjacentTo (A, B) usw. definieren.

Das Definieren der Reihenfolge um einen Scheitelpunkt in einem auf einer Oberfläche eingebetteten Diagramm erfordert zwei Zuweisungen: 1) Zuweisen von Beschriftungen zu Kantenendpunkten und 2) Zuweisen einer Konvention für die Reihenfolge um einen Scheitelpunkt. Wenn die Elementreihenfolge in einem Array (z. B. [A, B, C] in Ihrem Bild) im Uhrzeigersinn ist, können wir erkennen, welche Kante links von B liegt.

In Ihrem Beispiel grenzt jedes Element an die anderen an. Diese Tatsache ist auch im Array sichtbar, da das Array tatsächlich eine Permutation darstellt, dh die Reihenfolge ist wichtig, aber welches Element zuerst ist, nicht. [A, B, C] entspricht also [C, A, B]. Mit anderen Worten, das Array umschließt das letzte Element neben dem ersten.

Wenn Sie sich Topologie- und Konnektivitätsdiagramme ansehen, die Sie von Anbietern wie Teleatlas, Navteq, ESRI usw. erhalten, sehen Sie ein Muster (natürlich hat jeder seine eigene "spezielle" Vorgehensweise).

Persönlich , obwohl 1) Geospatial Topologie und 2) Routing Graphen ist nur Graphen und kann verallgemeinert werden , in der gleichen Datenstruktur dargestellt werden, versuche ich zu vermeiden , dass so viel wie möglich.

Ich versuche in meinem Kopf einen Unterschied zu machen.

• Wenn ich "Geodatentopologie" (1) sage, meine ich eine Diagrammstruktur zur Darstellung geometrischer Beziehungen der Merkmale (z. B. was von Kante A übrig bleibt, welche Fläche von Kanten [A, B, C] gebildet wird, was von Fläche enthalten ist B usw.).
• Wenn ich "Routing Graph" (2) sage, meine ich eine Graphstruktur zur Lösung von Routing-Problemen (z. B. kürzester Weg, um von A-> B mit [X] Einschränkungen / Bedingungen zu gelangen)

Sie sind nur Graphen, und sie gehören zur Breite der Wissenschaft , aber es gibt einen klaren Vorteil, nicht als dasselbe zu verallgemeinern. Sie dienen unterschiedlichen Zwecken, und es ist viel einfacher, Vorgänge zu optimieren und anzuwenden, wenn sie auf diesen bestimmten Zweck spezialisiert sind.

ESRI macht das. Sie haben eine Diagrammstruktur für die Geodatentopologie (TopologyGraph) und eine andere Diagrammstruktur für Routingprobleme (Netzwerkdatensatz). Sie haben sogar eine ältere Graphstruktur - Geometric Networks -, die sich gut für Flussprobleme in Versorgungsnetzen eignet.

In der PostgreSQL / PostGIS-Welt begegnen wir dem wohl auch. Es gibt eine Datenstruktur für das Routing und eine andere für die räumliche Topologie .

In Ihrer Frage sprechen Sie über Diagramme und deren Navigation im Uhrzeigersinn und gegen den Uhrzeigersinn sowie über Gesichter, weshalb ich eine spezielle Struktur für (1) haben möchte.

Für "Geospatial Topology" ist eine gute Möglichkeit, diese Art von Topologie darzustellen, die Art und Weise, wie das UK Hydrographic Office dies in seiner S57-Topologiebeschreibung der vollständigen Topologie tut .

Sehr ähnlich zu dem, was alle Hauptimplementierungen tun.

Wenn Sie nun nach Routing suchen, unterscheidet sich das Diagramm je nachdem, ob Sie eine Konnektivität in einer Richtung oder in zwei Richtungen benötigen. Am Ende läuft es darauf hinaus:

• Mit FROM Knoten verbunden zu Knoten , die schaffen Kanten
• Die Kanten haben Attribute für die linke und rechte Seite (z. B. Adressbereiche).
• Die Junctions (dh die Knoten, an denen die Kanten verbunden sind) können eine Reihe von Einschränkungen aufweisen. Sie hätten also im Grunde einen Master-Junction-Eintrag, um die Junction selbst darzustellen, und einzelne Einträge mit FROM- und TO- Einträgen, um die Flussbeschränkungen darzustellen.

Viel Glück und lassen Sie uns wissen, wie Ihr Projekt ausgeht.