Narzędzia Akumulacja odległości i Przydział odległości zastępują starsze narzędzia odległości kosztu. Te nowe narzędzia mierzą odległość kosztu we wszystkich kierunkach przez rekonstrukcję ciągłej powierzchni akumulacyjnej zamiast znajdowania ścieżek przez sieć środków komórek Można tworzyć wynikowe powierzchnie akumulowanych kosztów na podstawie wejściowych powierzchni tarcia kosztów i innych parametrów. Podobnie jak w przypadku innych powierzchni, można dokładniej zrozumieć wyniki, dodając warstwice (linie o równym akumulowanym koszcie), wizualizując je w 3D i wizualizując je w połączeniu ze zlewniami przydziału. Zazwyczaj celem konstruowania tej powierzchni jest wykreślenie ścieżek najmniejszego kosztu, które są ścieżkami o najbardziej stromym spadku.
Powierzchnia akumulowanych kosztów
Algorytm wykorzystywany przez te narzędzia rekonstruuje powierzchnię na podstawie jej nachylenia.
Podejście oparte na rekonstrukcji powierzchni
Dzięki narzędziom Akumulacji odległości i Przydziału odległości znalezienie najmniejszego akumulowanego kosztu w sieci nie jest już problemem. Wynikowy raster akumulowanych kosztów jest powierzchnią o nieznanym kształcie. Celem jest odkrycie kształtu, biorąc pod uwagę tylko jego nachylenie w każdej komórce analizowanego obszaru. To podejście wykorzystuje koncepcje z geometrii różniczkowej do obliczania prawdziwej odległości i kosztów we wszystkich kierunkach.
Powierzchnia akumulowanych kosztów odpowiada na trzy ważne pytania:
- Gdzie koszt gwałtownie rośnie w funkcji odległości?
- Które komórki źródłowe znajdują się najbliżej danej komórki nieźródłowej?
- Którą ścieżką należy podążać od komórki nieźródłowej do najbliższej komórki źródłowej?
Do znalezienia odpowiedzi na te pytania można użyć widoków 3D i warstwic z powierzchnią wynikową. Do uzyskania bardziej dokładnych odpowiedzi można użyć narzędzi Przydział odległości i Ścieżka optymalna jako linia.
Poniższe podsekcje zawierają opis relacji między prostą wejściową powierzchnią tarcia kosztów a wynikową powierzchnią akumulowanych kosztów.
Prosta wejściowa powierzchnia tarcia kosztów
Rozważ prosty raster tarcia kosztów, który ma centralną sekcję o koszcie = 3, środkową sekcję o koszcie = 2 i zewnętrzną sekcję o koszcie = 1.
Do zrozumienia relacji między rastrem tarcia kosztów, a wynikową powierzchnią akumulowanych kosztów można wykorzystać interpretację 3D. Wysokość h powierzchni w komórce c jest sumą nachylenia z wejściowego rastra kosztów pomnożoną przez odległości, na których te nachylenia występują (h = 3 * d1 + 2 * d2 + 1 * d3).
Widok z góry tej samej powierzchni wynikowej pokazuje, jak warstwice przedstawiają zmianę akumulowanych kosztów. Pokazane są również wartości nachylenia i ekspozycji w lokalizacji komórki c. Ekspozycja (kierunek najbardziej stromego spadku) jest zawsze prostopadła do warstwicy.
Uwzględnienie najmniejszego akumulowanego kosztu
Poniżej przedstawiono nieco bardziej skomplikowany przypadek. Akumulowany koszt (wysokość) w komórce nieźródłowej będzie pochodził ze źródła, które dociera do tej komórki przy najmniejszym koszcie.
Raster kosztów ma dwie wartości: 1 jako jasnoszary i 3 jako ciemnoszary. Punkty źródłowe to S1 i S2. Komórka nieźródłowa D jest bliższa punktowi S1 pod względem akumulowanego kosztu.
Dodanie warstwic do powierzchni akumulowanych kosztów może pomóc zwizualizować, jak szybko zmienia się koszt w miarę oddalania się od źródeł. Zaczynając od lokalizacji nieźródłowej i poruszając się pod kątem prostym do warstwic, podróżujesz z powrotem do najbliższej komórki źródłowej. Ścieżka nie prowadzi do najbliższego geometrycznie źródła ze względu na wysoki koszt wokół tego źródła.
Poniżej przedstawiono widok 3D pokazujący tę samą powierzchnię najmniejszych akumulowanych kosztów. Powierzchnia jest znacznie bardziej stroma wokół drogiego źródła (koszt kumuluje się szybciej). To źródło jest właścicielem minimalnej powierzchni kosztów tylko bardzo blisko niego. W przypadku wszystkich innych komórek analizowanego obszaru powierzchnia jest własnością źródła po lewej stronie.
Regiony przydziału jako zlewnie
Gdy wejściowa powierzchnia tarciakosztów i wynikowa powierzchnia akumulowanych kosztów stają się bardziej skomplikowane, nadal można używać warstwic, nachylenia i ekspozycji, aby zrozumieć zachowanie powierzchni akumulowanych kosztów. Ponadto regiony przydziału wokół źródeł działają jak zlewnie na wynikowej powierzchni akumulowanych kosztów. Wszystkie ścieżki najmniejszego kosztu w regionie przydziału płyną do tego samego źródła. W poniższych przykładach zlewnie przydziału połączono z warstwicami i widokiem 3D.
Bardziej skomplikowane powierzchnie akumulowanych kosztów, takie jak ta powierzchnia czasu podróży, mogą być precyzyjnie wizualizowane w 2D i 3D przy użyciu warstwic (w tym przypadku izochron).
Na poniższym obrazie przedstawiono widok 3D tej samej powierzchni. Klify w tle to bariery spowodowane obecnością rzeki.
Ścieżki najmniejszego kosztu spływają po powierzchni akumulowanych kosztów w kierunku źródła, które definiuje strefę przydziału (zlewnię), jak pokazano na poniższym obrazie:
Algorytm rekonstrukcji powierzchni jako rozszerzenie algorytmu sieciowego
Do znalezienia powierzchni akumulowanych kosztów przy użyciu jedynie wiedzy o najbardziej stromej wartości nachylenia w każdej komórce można również użyć algorytmu rekonstrukcji powierzchni. Algorytm ten jest podobny do algorytmu najkrótszej ścieżki używanego przez starsze narzędzia odległości kosztu, ale z dodatkowym etapem zapewniającym przybliżenie akumulowanego kosztu, który nie podąża za jednym z ośmiu kierunków w sieci. Nazywa się to etapem eikonału. Poniżej znajduje się krótki opis, a więcej szczegółów można znaleźć w pracy Sethiana z 1999 r.
Aby zrozumieć ten etap w kontekście, poniżej określono akumulowany koszt z5 dla komórki środkowej. Załóżmy, że znane są wszystkie sąsiednie akumulowane koszty zi. Ponadto na podstawie wejściowego rastra kosztów znana jest wartość nachylenia S w komórce środkowej.
Na przykład, jedno przybliżenie dla z5 może być wzdłuż przekątnej między z3 i z5, gdzie z5 = z3 + 1,4 * wielkość komórki * S, jak pokazano na poniższym rysunku. W tym przypadku S — wartość z wejściowego rastra kosztów — jest interpretowana jako nachylenie trójkąta abc. W przypadku wszystkich takich przybliżeń typu sieciowego, do przybliżenia akumulowanego kosztu w z5 używane jest tylko nachylenie w z5. Różni się to od starszego algorytmu sieciowego, który wykorzystuje średnią kosztów z par komórek.
Można wykonać osiem przybliżeń sieci, w tym cztery wykorzystujące pary istniejących wysokości, jak pokazano na sekwencji trzech poniższych rysunków. W tym przypadku wartość wejściowego rastra kosztów w lokalizacji komórki z5 jest interpretowana jako wielkość S gradientu płaszczyzny przechodzącej przez dwa znane punkty i nieznaną wysokość z5. Na podstawie tej relacji można wyznaczyć z5. To jest właśnie etap eikonału.
Obliczana jest wielkość gradientu płaszczyzny.
Kierunek gradientu jest obliczany.
Etap eikonału pozwala również uzyskać informacje o ekspozycji w komórce z5, która nazywana jest kierunkiem powrotnym.
Istnieje teraz dwanaście przybliżeń wysokości w komórce środkowej. Minimalna z nich jest wybierana i zapisywana jako wartość akumulowanego kosztu z5 dla komórki środkowej. Jeśli zażądano rastra kierunku powrotnego, ekspozycja gradientu (jak opisano w poprzednim akapicie) jest zapisywana w odpowiedniej lokalizacji w wynikowym rastrze kierunku powrotnego.
Proces ten jest powtarzany dla komórki za każdym razem, gdy uzyskana zostanie nowa wysokość dla jednego z jej sąsiadów. Ostatecznie wysokość przestaje się zmieniać i algorytm kończy działanie. Początkowe wysokości są dostarczane przez źródła: wynoszą one zero lub stanowią początkową wartość akumulacji dla każdego źródła. Pozostałe początkowe wartości wysokości są ustawione na nieskończoność. Szczegóły zostały opisane w pracy Sethiana (1999). Implementacja Esri jest połączeniem technik opisanych w pracach Sethiana (1999) i Zhao (2004).
Podsumowując, zaczynając od nachylenia każdej komórki, etapy te rekonstruują zarówno wysokość powierzchni akumulowanych kosztów, jak i kierunek najbardziej stromego spadku.
Ścieżki najmniejszego kosztu
Ścieżki najmniejszego kosztu podążają w kierunku najbardziej stromego spadku po powierzchni akumulowanych kosztów. Kierunek ten, dla jednej komórki, pokazano powyżej na rysunku 8. Wynikowy raster kierunku powrotnego przechowuje ten kierunek dla każdej komórki. Można użyć narzędzia Ścieżka optymalna jako linia, z rastrem kierunku powrotnego jako danymi wejściowymi, aby wykreślić te ścieżki zaczynając od komórki nieźródłowej.
Na poniższych rysunkach pokazana jest zakrzywiona ścieżka najmniejszego kosztu, zaczynająca się od niebieskiej komórki nieźródłowej d w prawym górnym rogu i prowadząca do dolnej komórki źródłowej s. Podczas gdy d jest geometrycznie bliżej górnego źródła, ze względu na wysokie koszty wokół tego źródła, taniej jest podróżować do s po zakrzywionej ścieżce.
Miejsce docelowe d to niebieski kwadrat. Podróżuje przez obszar o niższym koszcie do źródła, do którego może dotrzeć najtaniej, omijając w tym celu źródło o wysokich kosztach.
Choć może się wydawać, że określenie jest nieintuicyjne, lokalizacje wejściowe dla konstrukcji ścieżki najmniejszego kosztu są nazywane miejscami docelowymi. Źródła są używane do skonstruowania powierzchni i są lokalizacjami, w których kończą się ścieżki najmniejszego kosztu.
Strefy przydziału wokół źródeł dodatkowo wyjaśniają, że ścieżka najmniejszego kosztu z miejsca docelowego będzie biegła do dolnego źródła, a nie do górnego. Następnie wybrany obszar zostanie powiększony, aby pokazać, jak interpretowane są wartości komórek w rastrze kierunku powrotnego.
Krata łącząca środki komórek kierunku powrotnego jest pokazana w kolorze ciemnoszarym. Granice komórek są wyświetlane w kolorze jasnoszarym, a wartości komórek są wyświetlane jako strzałki azymutu. Gdy ścieżka najmniejszego kosztu przecina linie kraty, wykorzystuje azymut w najbliższej komórce kierunku powrotnego w kierunku podróży do zaktualizowania swojego kierunku. W górnym wierzchołku ścieżki obok komórki a, wartość kierunku powrotnego zapisana w komórce a zostanie użyta do skierowania linii wychodzącej z tego wierzchołka. Następna przecinana linia kraty znajduje się najbliżej komórki b, więc azymut zostanie użyty do wyjścia z drugiego wierzchołka i tak dalej.
Podsumowując, ścieżki najmniejszego kosztu zaczynają się i kończą w środkach komórek. Inne wierzchołki ścieżki mogą znajdować się w dowolnym miejscu na kracie poziomych i pionowych linii przebiegających przez środki komórek.
Obliczanie efektywnego nachylenia
Wartości nachylenia opisane w poprzedniej sekcji nie pochodzą ściśle z wejściowego rastra tarcia kosztów. Istnieje kilka innych danych wejściowych, które razem określają efektywne nachylenie wykorzystywane przez algorytm rekonstrukcji powierzchni. Szczegółowy opis tych danych wejściowych, w tym znaczenie uwzględnienia kierunku ruchu przez komórkę i kierunku podróży od lub do źródła, przedstawiono w innych tematach. Tutaj skupiono się na tym, w jaki sposób dane wejściowe są wykorzystywane przez algorytm rekonstrukcji powierzchni. Dane wejściowe są następujące:
- Wejściowe tarcie kosztów, C
- Wejściowa powierzchnia, S
- Mnożnik kosztu źródła, M
- Funkcja składnika poziomego, HF
- Funkcja składnika pionowego, VF
Efektywne nachylenie wykorzystywane przez algorytm rekonstrukcji ma następującą postać ogólną:
Efektywne nachylenie = C * S * M * HF * VF
Wartość ta jest następnie mnożona przez wielkość komórki lub sqrt(2) * wielkość komórki i dodawana do istniejącej wysokości w celu uzyskania jednego z oszacowań wysokości kierunku sieci. Bardziej skomplikowana funkcja efektywnego nachylenia jest używana do uzyskania szacunkowej wysokości dla etapu eikonału.
Efektywne nachylenie musi mieć jednostki akumulowanego kosztu podzielonego przez odległość liniową — wskaźnik. Jeśli na przykład powierzchnia akumulowanych kosztów ma mierzyć czas podróży w godzinach, a wielkość komórki analizy w metrach, efektywne nachylenie musi mieć jednostki godziny/metr.
Ponieważ efektywne nachylenie jest iloczynem kilku wartości, należy się upewnić, że jednostki poszczególnych wartości łączą się, aby uzyskać prawidłowe jednostki efektywnego nachylenia. Jeśli na przykład używany jest tylko prosty raster tarcia kosztów do opisania czasu podróży niezależnie od kierunku, wartości komórek rastra tarcia kosztów muszą mieć jednostki godziny/metr. Alternatywnie, jeśli używana jest również funkcja wędrówki Toblera jako funkcja składnika pionowego, ta funkcja wędrówki będzie miała jednostki godziny/metr, a powierzchnia tarcia kosztów, jeśli istnieje, musi być interpretowana jako waga bez jednostki. Następnie należy się upewnić, że wartości komórek tarcia kosztów mogą być interpretowane w ten sposób. Innymi słowy, funkcja składnika pionowego i tarcie kosztów nie mogą być jednocześnie wskaźnikami.
Nie kontroluje się bezpośrednio wejściowej powierzchni (S). Jest to bezjednostkowa waga, która rozciąga wielkość komórki, aby objąć rzeczywistą odległość powierzchniową 3D między środkami komórek. Na rysunku 2 algorytm rekonstrukcji powierzchni oblicza wysokość z5 dla komórki środkowej przez wielokrotne przybliżenie tej wysokości przy użyciu nachylenia z wejściowego rastra tarcia kosztów w komórce środkowej, wraz z zakładanymi znanymi wysokościami dla komórek sąsiednich.
Bariery są połączone krawędziami
Bariery w narzędziach Akumulacja odległości i Przydział odległości to komórki wejściowe, przez które nie można przejść. Podczas obliczeń są one reprezentowane jako komórki o wartości Brak danych. Są one przedstawiane jawnie jako parametr narzędzia lub niejawnie jako wartości Brak danych w jednym z innych rastrów wejściowych (takich jak raster tarcia kosztów). W pierwszym przypadku są one rasteryzowane i przekształcane w wartości Brak danych w rastrze kosztów. Ponieważ algorytm rekonstrukcji powierzchni nie może obniżyć oszacowania wysokości dla komórki bariery, znajdzie sposób na jej obejście.
Algorytm rekonstrukcji powierzchni wykorzystuje wszystkich ośmiu sąsiadów komórki w celu oszacowania jej wysokości. Narożnie położone sąsiadujące komórki bariery nie uniemożliwią wykorzystania komórki sąsiadującej po przekątnej do uzyskania oszacowania wysokości. Na poniższym obrazie oszacowanie wysokości dla z5 można uzyskać z z3, nawet jeśli komórki z2 i z6 są barierami.
Jeśli z2 i z6 miałyby być częścią liniowego obiektu bariery, takiego jak kanał lub rzeka, takie zachowanie zniweczyłoby zamierzenie bariery. Aby temu zapobiec, algorytm rekonstrukcji powierzchni faworyzuje łączenie komórek barierowych w stosunku do łączenia komórek niebędących barierami. Oznacza to, że do rastra kosztów wprowadzane są dodatkowe komórki o wartościach Brak danych, aby wszystkie istniejące komórki barier miały wspólną krawędź. Na powyższym obrazie komórka z5 lub komórka z3 również stałaby się komórką bariery.
Używając barier w analizie, należy wziąć pod uwagę to zachowanie i odpowiednio dostosować wielkość komórki analizy, aby zachować zamierzoną łączność wokół komórek bariery. Za pomocą narzędzia Statystyki z punktami centralnymi, aby zagęścić rastrowe wersje obiektów liniowych w celu użycia ich jako barier lub jako sieci liniowych, które nie powinny być przerywane przez sąsiednie komórki barier.
Odniesienia
Douglas, D. „Least-cost Path in GIS Using an Accumulated Cost Surface and Slopelines”, Cartographica: The International Journal for Geographic Information and Geovisualization, 1994, Vol. 31, No. 3, DOI: 10.3138/D327-0323-2JUT-016M
Goodchild, M.F. „An evaluation of lattice solutions to the problem of corridor location”, Environment and Planning A: Economy and Space, 1977, vol. 9, strony 727–738
Sethian, J.A. Level Set Methods and Fast Marching Methods (Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science) 2nd Edition, Cambridge University Press, 2nd Edition (1 czerwca 1999 r.)
Warntz, W. „Transportation, Social Physics, and the Law Of Refraction”, The Professional Geographer, 1957, Vol. 9, No. 4, strony 2–7.
Zhao, H. „A fast sweeping method for Eikonal equations”, Mathematics of Computation, 2004, Vol. 74, No. 250, strony 603–627