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.
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.
