Łączenie cech linii i określanie długości najdłuższej linii

12

Mam operację liniową (patrz zdjęcie) reprezentującą rzekę, którą utworzyłem za pomocą narzędzia Stream_to_Feature. Tabela atrybutów zawiera kilka rekordów reprezentujących różne linie - problemem jest najdłuższa linia (łatwa do odróżnienia wizualnie) nie jest reprezentowana jako pojedyncza linia w tabeli, w rzeczywistości składa się z wielu mniejszych linii. Linie wydają się dotykać, chociaż się nie przecinają.

Jak scalić te linie, a następnie określić długość najdłuższej linii za pomocą ArcObjects lub metod ręcznych, które mogę przekonwertować na ArcObjects? Jeszcze lepsze rozwiązanie polegałoby na pozbyciu się wszystkich dopływów i pozostawieniu mnie z samym tylko kanałem rzeki.

Cecha linii - rzeka

Radar
źródło
1
Czy w ogóle się łączą? Powiedziałeś, że się nie krzyżują, ale czy to znaczy, że nie dzielą wierzchołka?
Nathanus
1
Przepraszam - powinienem być bardziej jasny. Mają wspólne wierzchołki, ale nie krzyżują się całkowicie.
Radar
Czy wiesz, gdzie jest ujście rzeki? Czy rzeka jest zawsze drzewem (jedna unikalna ścieżka z każdego punktu wody do ujścia)?
Kirk Kuykendall
3
W rzeczywistości nie chcesz długości „najdłuższej linii”. Może to być droga od jednego górnego zasięgu do drugiego zdalnego górnego zasięgu. Stanie się tak, gdy dwie główne gałęzie strumienia połączą się w pobliżu ujścia. Zamiast tego potrzebujesz najdłuższej trasy między ujściem a dowolnym innym punktem końcowym strumienia. (Ta charakterystyka nie wymaga nawet przedstawienia strumienia jako drzewa: może warkoczyć i mieć wyspy.)
whuber
@ whuber - Twoja ocena jest poprawna - masz pomysł, jak to zrobić, korzystając z tras?
Radar

Odpowiedzi:

18

Najpierw małe tło, aby wskazać, dlaczego nie jest to trudny problem. Przepływ przez rzekę gwarantuje, że jej segmenty, jeśli są prawidłowo zdigitalizowane, zawsze mogą być zorientowane w celu utworzenia ukierunkowanego wykresu acyklicznego (DAG). Z kolei wykres można uporządkować liniowo tylko wtedy, gdy jest to DAG, przy użyciu techniki znanej jako sortowanie topologiczne . Sortowanie topologiczne jest szybkie: jego wymagania dotyczące czasu i przestrzeni wynoszą O (| E | + | V |) (E = liczba krawędzi, V = liczba wierzchołków), co jest tak dobre, jak to tylko możliwe. Stworzenie takiego liniowego uporządkowania ułatwiłoby znalezienie głównego złoża strumienia.

Oto szkic algorytmu . Ujście strumienia leży wzdłuż jego głównego koryta. Przejdź w górę rzeki wzdłuż każdej gałęzi przymocowanej do ujścia (może istnieć więcej niż jedna, jeśli ujście jest przecięciem) i rekurencyjnie znajdź główne złoże prowadzące do tego odgałęzienia. Wybierz gałąź, dla której całkowita długość jest największa: jest to „link zwrotny” wzdłuż głównego łóżka.

Aby to wyjaśnić, oferuję trochę (nieprzetestowany) pseudokod . Dane wejściowe to zestaw segmentów liniowych (lub łuków) S (zawierający digitalizowany strumień), z których każdy ma dwa różne punkty końcowe: początek (S) i koniec (S) oraz dodatnią długość, długość (S); i ujście rzeki p , które jest punktem. Wyjście jest sekwencją segmentów łączących usta z najbardziej odległym punktem powyżej.

Będziemy musieli pracować z „zaznaczonymi segmentami” (S, p). Składają się one z jednego z segmentów S wraz z jednym z jego dwóch punktów końcowych, str . Musimy znaleźć wszystkie segmenty S, które dzielą punkt końcowy z punktem sondującym q , oznaczyć te segmenty innymi punktami końcowymi i zwrócić zestaw:

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

Jeśli nie można znaleźć takiego segmentu, Wyodrębnij musi zwrócić pusty zestaw. Jako efekt uboczny, ekstrakt musi usunąć wszystkie segmenty, które zwraca, z zestawu A, modyfikując w ten sposób sam A.

Nie podam implementacji Extract: twój GIS zapewni możliwość wyboru segmentów S współdzielących punkt końcowy z q . Oznaczenie ich polega po prostu na porównaniu zarówno początku (S), jak i końca (S) zq i zwrócenie dowolnego z dwóch punktów końcowych, który nie jest zgodny.

Teraz jesteśmy gotowi rozwiązać problem.

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

Procedura „append (S, B0)” przykleja segment S na końcu tablicy B0 i zwraca nową tablicę.

(Jeśli strumień naprawdę jest drzewem: bez wysp, jezior, warkoczy itp. - możesz zrezygnować z kroku kopiowania A do A0 .)

Odpowiedź na pierwotne pytanie polega na utworzeniu połączenia segmentów zwróconych przez LongestUpstreamReach.

Aby to zilustrować , rozważmy strumień na oryginalnej mapie. Załóżmy, że jest on zdigitalizowany jako zbiór siedmiu łuków. Łuk a biegnie od ujścia w punkcie 0 (u góry mapy, po prawej stronie na poniższym rysunku, który jest obrócony) powyżej pierwszego zlewu w punkcie 1. To długi łuk, powiedzmy 8 jednostek długości. Łuk b rozgałęzia się w lewo (na mapie) i jest krótki, około 2 jednostek długości. Łuk c rozgałęzia się po prawej stronie i ma długość około 4 jednostek itp. Niech „b”, „d” i „f” oznaczają gałęzie po lewej stronie, gdy przechodzimy od góry do dołu na mapie, i „a”, „c”, „e” i „g” pozostałe gałęzie, a numerując wierzchołki od 0 do 7, możemy abstrakcyjnie przedstawić wykres jako zbiór łuków

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

Przypuszczam, że mają one odpowiednio długości 8, 2, 4, 1, 2, 2, 2 dla a do g . Usta mają wierzchołek 0.

Postać

Pierwszym przykładem jest wywołanie funkcji Extract (5, {f, g}). Zwraca zestaw zaznaczonych segmentów {(f, 6), (g, 7)}. Zauważ, że wierzchołek 5 znajduje się u zbiegu łuków f i g (dwa łuki na dole mapy) i że (f, 6) i (g, 7) oznaczają każdy z tych łuków ich górnymi punktami końcowymi.

Następnym przykładem jest wywołanie LongestUpstreamReach (0, A). Pierwszym działaniem, jakie podejmuje, jest wywołanie Wyodrębnij (0, A). Zwraca zestaw zawierający zaznaczony segment (a, 1) i usuwa segment a ze zbioru A0 , który teraz jest równy {b, c, d, e, f, g}. Jest jedna iteracja pętli, gdzie (S, q) = (a, 1). Podczas tej iteracji następuje wywołanie LongestUpstreamReach (1, A0). Rekurencyjnie musi zwrócić sekwencję (g, e, c) lub (f, e, c): oba są jednakowo ważne. Zwracana długość (M) wynosi 4 + 2 + 2 = 8. (Zauważ, że LongestUpstreamReach nie modyfikuje A0 .) Na końcu pętli segment azostał dołączony do koryta strumienia, a jego długość została zwiększona do 8 + 8 = 16. Zatem pierwsza wartość zwrotna składa się z sekwencji (g, e, c, a) lub (f, e, c, a), w obu przypadkach o długości 16 dla drugiej wartości zwracanej. To pokazuje, jak LongestUpstreamReach po prostu porusza się w górę rzeki od ujścia, wybierając przy każdym zbiegu gałąź o największej jeszcze odległości do przebycia, i śledzi odcinki przemierzane wzdłuż trasy.

Bardziej wydajna implementacja jest możliwa, gdy istnieje wiele warkoczy i wysp, ale w większości przypadków nie będzie zmarnowanego wysiłku, jeśli LongestUpstreamReach zostanie wdrożony dokładnie tak, jak pokazano, ponieważ przy każdym zbiegu nie ma nakładania się wyszukiwań w różnych gałęziach: komputerowych czas (i głębokość stosu) będzie wprost proporcjonalny do całkowitej liczby segmentów.

Whuber
źródło
+1 Teraz, gdyby tylko wiedzieli o tym przed nazwaniem rzeki Missouri.
Kirk Kuykendall
1
@Kirk Rekursywna eksploracja amerykańskiego Zachodu na początku 1800 roku nie była łatwa :-).
whuber
jest to niezwykle pomocne! Zobaczę, czy mogę wprowadzić tę konfigurację do mojego GIS i udostępnić jakiś użyteczny kod, gdy zacznę działać. Twoje zdrowie!
Radar
Niezła odpowiedź
Ragi Yaser Burhum,
2

Narzędzie Unsplit Line może być pomocne w tym, co próbujesz zrobić, chociaż będziesz musiał opracować metodę rozróżniania jednej gałęzi strumienia od drugiej (dla pola rozpuszczania). Zakłada się jednak, że masz licencję ArcInfo.

Jeśli nie masz takiej licencji, możesz rozważyć podejście ArcObjects biorąc XY każdego wierzchołka, wypełniając IPointCollectionje, a następnie tworząc IGeometryjako PolyLineClass.

Natanus
źródło
1

Możesz użyć RivEX, to jest to narzędzie ArcGIS 9.1 (które będzie działać w 9.3 i 10). Posiada narzędzia do identyfikowania problemów topologicznych z sieciami rzecznymi i wiele narzędzi do przetwarzania. Jedno z takich narzędzi znajduje główny trzon .

Hornbydd
źródło