Wie beschreibe ich eine besondere Beziehung zwischen verbundenen Kanten?

11

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

Randbeziehungen

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.

Andytilia
quelle
Warum fügen Sie nicht jedem Knoten die nach Richtung geordnete Liste der damit verbundenen Kanten hinzu?
Julien
1
Es hört sich so an, als ob Sie nach einem DCEL suchen . Beachten Sie, dass beim Dualisieren eines planaren Diagramms die Flächen zu Knoten werden. In der Abbildung sind Teile von drei Flächen Alpha , Beta und Gamma dargestellt , wobei Kante A Beta von Gamma trennt, Kante B Gamma von Alpha trennt und Kante C Alpha von Beta trennt . Das ergibt einen zyklischen Graphen, der alle Informationen enthält, nach denen Sie suchen - und tatsächlich ist es wirklich die Nachbarschaft im dualen Graphen.
whuber
@ Julien, danke - das ist eine anständige Implementierungsidee; Ich werde es ausprobieren. Aber zuerst ... Ich suche nach einem Wort oder einer Phrase, um diese Art von Beziehung zu beschreiben.
Andytilia
@whuber, danke für den Tipp. Ich bin DCEL noch nie begegnet. Es sieht so aus, als ob B die "nächste" halbe Kante der nach Norden gerichteten, nach Westen gerichteten halben Kante von A ist. Hm: Wenn ich dann gegen den Uhrzeigersinn gehen möchte, dann betrachte ich die nach Süden gerichtete halbe Kante von A. Und "nach Westen" wird durch den gemeinsamen Knoten impliziert. Ich frage mich, ob es funktionieren wird, wenn B keine Gesichtsgrenze ist (dh Sackgasse). Ich werde es weiter untersuchen.
Andytilia
@ Julien, ich lese deinen Kommentar noch einmal. Ich kann jetzt sehen, dass Sie mir auch eine vorgeschlagene Formulierung geben. :-) Vielleicht könnte ich "nach Richtung geordnet" verwenden, um die Beziehung zu beschreiben. Ich muss ein bisschen damit herumspielen.
Andytilia

Antworten:

1

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.

Katahdin
quelle
Vielen Dank! Ich mag den Begriff "Rotational benachbart". Es muss nur, wie Sie sagen, um die Konvention zum Ordnen um einen Scheitelpunkt erweitert werden. In meinem Fall muss ich diese Konvention von Fall zu Fall definieren. Also werde ich daran arbeiten, etwas wie isRotationallyAdjacentTo (A, B, Direction) mit einer Permutation zu codieren, wie Sie es vorschlagen. Oder in Bezug auf den obigen Fall "A ist im Uhrzeigersinn neben B und A ist nicht im Uhrzeigersinn neben C".
Andytilia
Übrigens hatte ich mich noch nicht mit Region Connection Calculus befasst. Es ist zwar nicht ganz das, was dieses Problem löst (wie Sie erwähnen), aber es ist dennoch interessant. Können Sie mich auf die „späteren Arbeiten“ von Randell, Cui und Cohn hinweisen? (hm: die RC & C Charaktere haben ein Framework namens RCC erstellt)
andytilia
4

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 .

UKHO Vollständige Topologie

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.

Ragi Yaser Burhum
quelle
Vielen Dank für die klare Unterscheidung zwischen zwei Arten von Grafiken. Halten Sie es für eine faire Unterscheidung, zu sagen, dass Routing-Diagramme im Allgemeinen einige Informationen zu den Kanten und / oder Knoten enthalten, während die Geodatentheorie niemals eine Zuordnung zu den Kanten und Knoten benötigt (sie basiert nur auf den räumlichen Beziehungen zwischen Objekten)? Ich denke, mein Problem passt gut in den Bereich der Geodatentopologie: Die Beziehung zwischen den Kanten A und B besteht unabhängig von einer Zuordnung an den Kanten. Aber ich vermisse immer noch eine prägnante Art, diese Beziehung zu benennen ...
Andytilia
Ich denke, es ist eine zu starke Aussage, um zu sagen, dass "Geospatial Topology niemals eine Zuordnung an den Kanten und Knoten benötigt", sondern wirklich von Fall zu Fall. Ich habe Topologiediagramme gesehen, die eine Zuordnung enthalten, die von Features mit diesem Knoten gemeinsam genutzt wird. Beispiele sind Z- oder Temperaturwerte. Ich würde sagen, sagen Sie einfach, nennen Sie es einfach Knoten und unterscheiden Sie den verbundenen Knoten, wenn nötig, aber natürlich habe ich nicht genug Kontext für das Gesamtproblem, das Sie lösen möchten.
Ragi Yaser Burhum
Ah, richtig, danke: eine planare grafische Darstellung von zwei Straßen, die sich an einer Brücke kreuzen. Es könnte einen Knoten mit vier Kanten geben, aber nicht alle Kanten sind miteinander verbunden. Der Knoten muss also Informationen über Kreuzungsebenen enthalten, um diese Situation von einer Bahnüberquerung zu unterscheiden.
Andytilia
1
Genau :). Deshalb erwähne ich Junctions. Ich habe über diesen Fall nachgedacht. Eine Möglichkeit besteht darin, die Kreuzung als "Hauptknoten" mit den FROM-TO-Einträgen darzustellen. Über- / Unterführungssituationen treten ständig auf. Am schlimmsten sind Fälle wie die Bay Bridge oder in Chicago, in denen Kanten im 2D-Raum übereinstimmen (sie liegen effektiv übereinander), wobei eine Reihe von Kanten in die eine Richtung fließt, während die andere in die andere Richtung fließt.
Ragi Yaser Burhum