Verbindungslinienmerkmale und Bestimmen der Länge der längsten Linie

12

Ich habe ein Linien-Feature (siehe Bild), das einen Fluss darstellt, den ich mit dem Stream_to_Feature-Tool erstellt habe. Die Attributtabelle enthält mehrere Datensätze, die verschiedene Zeilen darstellen - das Problem ist, dass die längste Zeile (visuell leicht zu unterscheiden) nicht als einzelne Zeile in der Tabelle dargestellt wird, sondern tatsächlich aus vielen kleineren Zeilen besteht. Die Linien scheinen sich zu berühren, obwohl sie sich nicht kreuzen.

Wie kann ich diese Linien zusammenführen und dann die Länge der längsten Linie mithilfe von ArcObjects oder manuellen Methoden bestimmen, die ich in ArcObjects konvertieren kann? Eine noch bessere Lösung wäre, alle Nebenflüsse loszuwerden und mich nur noch mit dem Flusskanal als Linie zu belassen.

Leitungsmerkmal - Fluss

Radar
quelle
1
Verbinden sie sich überhaupt? Sie sagten, dass sie sich nicht kreuzen, aber bedeutet das, dass sie keinen Scheitelpunkt teilen?
Nathanus
1
Entschuldigung - ich hätte klarer sein sollen. Sie teilen Scheitelpunkte, kreuzen sich jedoch nicht vollständig.
Radar
Wissen Sie, wo die Flussmündung ist? Ist der Fluss immer ein Baum (ein einziger Weg von jedem Quellpunkt zur Mündung)?
Kirk Kuykendall
3
Eigentlich wollen Sie nicht die Länge der "längsten Linie". Dies könnte eine Route von einer stromaufwärtigen Reichweite zu einer anderen entfernten stromaufwärtigen Reichweite sein. Dies geschieht, wenn sich zwei Hauptarme des Baches in der Nähe seiner Mündung vereinigen. Stattdessen möchten Sie die längste Route zwischen der Mündung und einem beliebigen anderen Endpunkt im Stream. (Diese Charakterisierung erfordert nicht einmal, dass der Bach als Baum dargestellt wird: Er kann flechten und Inseln haben.)
whuber
@whuber - deine Einschätzung ist richtig - hast du eine Idee, wie ich das mithilfe von Routen erreichen kann?
Radar

Antworten:

18

Zunächst ein kleiner Hintergrund , der zeigt, warum dies kein schweres Problem ist. Die Strömung durch einen Fluss garantiert, dass seine Segmente bei korrekter Digitalisierung immer so ausgerichtet werden können, dass sie einen gerichteten azyklischen Graphen (DAG) bilden. Ein Diagramm kann wiederum genau dann linear geordnet werden, wenn es sich um eine DAG handelt, wobei eine als topologische Sortierung bekannte Technik verwendet wird . Die topologische Sortierung ist schnell: Ihr zeitlicher und räumlicher Bedarf beträgt O (| E | + | V |) (E = Anzahl der Kanten, V = Anzahl der Eckpunkte) und ist so gut wie es nur geht. Das Erstellen einer solchen linearen Anordnung würde es leicht machen, das Hauptstrombett zu finden.

Hier ist also eine Skizze eines Algorithmus . Die Mündung des Baches liegt entlang seines Hauptbettes. Bewegen Sie sich flussaufwärts entlang jedes Zweigs, der am Mund befestigt ist (es kann mehr als einen geben, wenn der Mund zusammenfließt) und finden Sie rekursiv das Hauptbett, das zu diesem Zweig hinunterführt. Wählen Sie den Zweig, für den die Gesamtlänge am größten ist: Dies ist Ihr "Backlink" entlang des Hauptbetts.

Um dies zu verdeutlichen, biete ich einen (nicht getesteten) Pseudocode an . Die Eingabe ist ein Satz von Liniensegmenten (oder Bögen) S (umfassend den digitalisierten Strom), die jeweils zwei unterschiedliche Endpunkte Anfang (S) und Ende (S) und eine positive Länge, Länge (S) aufweisen; und die Flussmündung p , die ein Punkt ist. Die Ausgabe ist eine Folge von Segmenten, die den Mund mit dem am weitesten stromaufwärts gelegenen Punkt verbinden.

Wir müssen mit "markierten Segmenten" (S, p) arbeiten. Diese bestehen aus einem der Segmente S zusammen mit einem seiner beiden Endpunkte, p . Wir müssen alle Segmente S finden , die einen Endpunkt mit einem Prüfpunkt q gemeinsam haben , diese Segmente mit ihren anderen Endpunkten markieren und die Menge zurückgeben:

Procedure Extract(q: point, A: set of segments): Set of marked segments.

Wenn kein solches Segment gefunden werden kann, muss Extract die leere Menge zurückgeben. Als Nebeneffekt muss Extract alle Segmente entfernen, die es aus der Menge A zurückgibt , und dabei A selbst ändern .

Ich gebe keine Implementierung von Extract: Ihr GIS bietet die Möglichkeit, Segmente S auszuwählen, die einen Endpunkt mit q teilen . Um sie zu markieren, müssen nur Anfang (S) und Ende (S) mit q verglichen und der jeweils nicht passende der beiden Endpunkte zurückgegeben werden.

Jetzt sind wir bereit, das Problem zu lösen.

Procedure LongestUpstreamReach(p: point, A: set of segments): (Array of segments, length)
    A0 = A                        // Optional: preserves A
    C = Extract(p, A0)            // Removes found segments from the set A0!
    L = 0; B = empty array
    For each (S,q) in C:          // Loop over the segments meeting point p
        (B0, M) = LongestUpstreamReach(q, A0)
        If (length(S) + M > L) then
            B = append(S, B0)
            L = length(S) + M
        End if
    End for
    Return (B, L)
End LongestUpstreamReach

Die Prozedur "Anhängen (S, B0)" klebt das Segment S am Ende des Arrays B0 und gibt das neue Array zurück.

(Wenn der Bach wirklich ein Baum ist: keine Inseln, Seen, Zöpfe usw. - dann können Sie auf den Schritt des Kopierens von A nach A0 verzichten .)

Die ursprüngliche Frage wird durch Bilden der Vereinigung der von LongestUpstreamReach zurückgegebenen Segmente beantwortet.

Betrachten wir zur Veranschaulichung den Stream in der ursprünglichen Karte. Angenommen, es wird als Sammlung von sieben Bögen digitalisiert. Bogen a geht vom Mund am Punkt 0 (oben auf der Karte, rechts in der Abbildung unten, die gedreht wird) stromaufwärts bis zur ersten Einmündung am Punkt 1. Es ist ein langer Bogen, etwa 8 Einheiten lang. Bogen b verzweigt sich nach links (in der Karte) und ist kurz, ungefähr 2 Einheiten lang. Bogen c zweigt nach rechts ab und ist ungefähr 4 Einheiten lang usw. Wenn "b", "d" und "f" die linken Zweige bezeichnen, während wir auf der Karte von oben nach unten gehen, und "a", "c", "e" und "g" der anderen Zweige und die Nummerierung der Scheitelpunkte 0 bis 7 können den Graphen abstrakt als Sammlung von Bögen darstellen

A = {a=(0,1), b=(1,2), c=(1,3), d=(3,4), e=(3,5), f=(5,6), g=(5,7)}

Ich nehme an, sie haben Längen von 8, 2, 4, 1, 2, 2, 2 für a bis g . Der Mund ist der Scheitelpunkt 0.

Zahl

Das erste Beispiel ist der Aufruf von Extract (5, {f, g}). Es gibt die Menge der markierten Segmente {(f, 6), (g, 7)} zurück. Beachten Sie, dass sich der Scheitelpunkt 5 am Zusammenfluss der Bögen f und g befindet (die beiden Bögen am unteren Rand der Karte) und dass (f, 6) und (g, 7) jeden dieser Bögen mit ihren stromaufwärtigen Endpunkten markieren .

Das nächste Beispiel ist der Aufruf von LongestUpstreamReach (0, A). Die erste Aktion ist der Aufruf von Extract (0, A). Dies gibt eine Menge mit dem markierten Segment (a, 1) zurück und entfernt das Segment a aus der Menge A0 , die nun gleich {b, c, d, e, f, g} ist. Es gibt eine Iteration der Schleife, wobei (S, q) = (a, 1). Während dieser Iteration wird LongestUpstreamReach (1, A0) aufgerufen. Rekursiv muss entweder die Folge (g, e, c) oder (f, e, c) zurückgegeben werden: Beide sind gleichermaßen gültig. Die zurückgegebene Länge (M) ist 4 + 2 + 2 = 8. (Beachten Sie, dass LongestUpstreamReach A0 nicht ändert .) Am Ende der Schleife wird Segment a angezeigtwurde an das Flussbett angehängt und die Länge wurde auf 8 + 8 = 16 erhöht. Somit besteht der erste Rückgabewert entweder aus der Folge (g, e, c, a) oder (f, e, c, a), mit einer Länge von 16 in jedem Fall für den zweiten Rückgabewert. Dies zeigt, wie sich LongestUpstreamReach gerade stromaufwärts von der Mündung bewegt, wobei bei jedem Zusammenfluss der Zweig mit der längsten noch verbleibenden Entfernung ausgewählt wird und die Segmente verfolgt werden, die entlang seiner Route durchlaufen werden.

Eine effizientere Implementierung ist möglich, wenn es viele Geflechte und Inseln gibt, aber für die meisten Zwecke wird wenig Aufwand verschwendet, wenn LongestUpstreamReach genau wie gezeigt implementiert wird, da bei jedem Zusammenfluss keine Überlappung zwischen den Suchvorgängen in den verschiedenen Zweigen auftritt: dem Computing Zeit (und Stapeltiefe) sind direkt proportional zur Gesamtzahl der Segmente.

whuber
quelle
+1 Wenn sie das nur gewusst hätten, bevor sie den Missouri River benannt haben.
Kirk Kuykendall
1
@Kirk Die rekursive Erforschung des amerikanischen Westens im frühen 19. Jahrhundert war nicht einfach :-).
whuber
das ist unglaublich hilfreich! Ich werde sehen, ob ich dieses Setup in mein GIS integrieren und nützlichen Code freigeben kann, sobald es funktioniert. Prost!
Radar
Nette Antwort whuber
Ragi Yaser Burhum
2

Das Werkzeug Aufgeteilte Linie kann hilfreich sein, wenn Sie versuchen, etwas zu tun, obwohl Sie eine Methode zur Unterscheidung eines Stream-Zweigs von einem anderen (für das Auflösungsfeld) festlegen müssen. Dies setzt jedoch voraus, dass Sie über eine ArcInfo-Lizenz verfügen.

Wenn Sie nicht über eine solche Lizenz verfügen, können Sie den ArcObjects-Ansatz in Betracht ziehen, indem Sie das XY jedes Scheitelpunkts verwenden, einen IPointCollectionmit ihnen füllen und dann einen IGeometryals erstellen PolyLineClass.

Nathanus
quelle
1

Sie können RivEX verwenden , ein 9.1 ArcGIS-Tool (das in 9.3 und 10 funktioniert). Es verfügt über Tools zur Identifizierung topologischer Probleme mit Flussnetzen und viele Verarbeitungswerkzeuge. Ein solches Werkzeug findet den Hauptschaft .

Hornbydd
quelle