Image Server에서 이용 가능
거리 누적 및 거리 할당 도구는 레거시 비용 거리 도구를 대체합니다. 이 새로운 도구는 셀 중심 네트워크를 통해 경로를 찾는 대신 연속 누적 표면을 재생성하여 모든 방향에서 비용 거리를 측정합니다. 입력 비용 마찰 표면 및 기타 매개변수로부터 결과 누적 비용 표면을 생성할 수 있습니다. 다른 표면과 마찬가지로 등고선 라인(누적 비용이 동일한 라인)을 추가하고, 3D로 시각화하고, 할당 유역과 결합하여 시각화하여 결과를 보다 정확하게 파악할 수 있습니다. 일반적으로 이 표면을 구성하는 것은 가장 가파른 내리막 경로인 최저 비용 경로를 플롯하기 위한 것입니다.
누적 비용 표면
이러한 도구에서 사용하는 알고리즘은 경사로부터 표면을 재생성합니다.
표면 재생성 접근 방식
거리 누적 및 거리 할당 도구를 사용하면 최저 누적 비용 찾기는 더 이상 네트워크 문제가 아니게 됩니다. 결과 누적 비용 래스터는 알 수 없는 모양의 표면입니다. 연구 영역의 각 셀에서 주어진 경사만을 사용해 해당 모양을 검색하고자 합니다. 이러한 접근 방식은 차등 지오메트리의 개념을 사용하여 모든 방향의 실제 거리 및 비용을 계산합니다.
누적 비용 표면은 다음 세 가지 중요한 질문에 답합니다.
- 거리 함수로 비용이 급격히 증가하는 위치는 어디입니까?
- 주어진 비시작지점 셀에 가장 가까운 시작지점 셀은 어디입니까?
- 비시작지점으로부터 가장 가까운 시작지점 셀까지 따라야 하는 경로는 무엇입니까?
결과 표면과 함께 3D 뷰 및 등고선 라인을 사용하여 이러한 질문에 대한 답을 확인할 수 있습니다. 거리 할당 및 라인 형식 최적 경로 도구를 사용하여 보다 정확한 답을 확인할 수 있습니다.
아래의 하위 섹션에서는 단순 입력 비용 마찰 표면 및 결과 누적 비용 표면 간의 관계를 설명합니다.
단순 입력 비용 마찰 표면
비용 = 3인 중앙 섹션, 비용 = 2인 중간 섹션, 비용 = 1인 외부 섹션이 있는 단순 비용 마찰 래스터가 있다고 가정해 봅시다.
비용 마찰 래스터와 결과 누적 비용 표면 간의 관계를 이해하는 데 3D 해석을 사용할 수 있습니다. 셀 c에서 표면 높이 h는 입력 비용 래스터의 경사에 해당 경사가 활성화된 거리를 곱한 값의 합입니다(h = 3 * d1 + 2 * d2 + 1 * d3).
동일한 결과 표면의 평면도는 등고선 라인이 누적 비용 변화를 묘사하는 방식을 보여줍니다. 셀 위치 c의 경사 및 경사면 방향 값도 나와 있습니다. 경사면 방향(가장 가파른 내리막 방향)은 항상 등고선 라인에 직각입니다.
최소 누적 비용 통합
약간 더 복잡한 사례가 아래에 나와 있습니다. 비시작지점 셀의 누적 비용(고도)은 최저 비용으로 해당 셀에 도착하는 시작지점에서 나옵니다.
비용 래스터에는 두 가지 값이 있으며, 1은 연한 회색이고 3은 진한 회색입니다. 시작지점 포인트는 S1 및 S2입니다. 비시작지점 셀 D는 누적 비용 측면에서 S1에 더 가깝습니다.
누적 비용 표면에 등고선 라인을 추가하면 시작지점에서 멀어질수록 비용이 얼마나 빨리 변하는지 시각화할 수 있습니다. 비시작지점 위치에서 시작하여 등고선 라인에 직각으로 이동하면 가장 가까운 시작지점 셀로 다시 돌아오게 됩니다. 기하학적으로 가장 가까운 시작지점 주변의 비용이 높으므로 이 경로는 해당 시작지점으로 이동하지 않습니다.
아래는 동일한 최저 누적 비용 표면을 보여주는 3D 뷰입니다. 표면은 비용이 높은 시작지점 주변에서 훨씬 더 가파릅니다(비용이 더 빠르게 누적됨) 해당 시작지점은 최저 비용 표면을 매우 가까운 위치에서만 소유합니다. 연구 영역의 다른 모든 셀에서 표면은 좌측 시작지점에서 소유합니다.
유역으로 지역 할당
입력 비용 마찰 표면 및 결과 누적 비용 표면이 한층 복잡해졌지만, 여전히 등고선 라인, 경사, 경사면 방향을 사용하여 누적 비용 표면의 동작을 이해할 수 있습니다. 또한 시작지점 주변의 할당 지역은 누적 비용 결과 표면의 유역으로 기능합니다. 할당 지역 내의 모든 최저 비용 경로는 동일한 시작지점으로 흐릅니다. 아래 예시에서 할당 유역은 등고선 라인 및 3D 뷰와 결합됩니다.
이 이동 시간 표면과 같이 보다 복잡한 누적 비용 표면은 등고선 라인(이 경우 등시선)을 사용하여 2D 및 3D로 정확하게 시각화할 수 있습니다.
다음 이미지는 동일한 표면의 3D 뷰입니다. 배경의 절벽은 강으로 인해 생긴 장애물입니다.
최저 비용 경로는 다음 이미지에 표시된 대로 할당 구역(유역)을 정의하는 시작지점을 향해 누적 비용 표면 아래로 흐릅니다.
네트워크 알고리즘의 확장인 표면 재생성 알고리즘
각 셀에서 가장 가파른 경사 값만 알고 있을 때 누적 비용 표면을 찾으려면 표면 재생성 알고리즘을 사용할 수도 있습니다. 이 알고리즘은 레거시 비용 거리 도구에서 사용하는 최단 경로 알고리즘과 유사하지만, 8개의 네트워크 방향 중 하나를 따르지 않는 누적 비용 근사치를 제공하는 추가 단계가 있습니다. 이를 Eikonal 단계라고 합니다. 간단한 설명은 다음과 같으며 자세한 내용은 Sethian, 1999에서 확인할 수 있습니다.
이 단계를 컨텍스트상에서 이해하기 위해, 아래에 중앙 셀에 대한 누적 비용 z5를 찾아보겠습니다. 인접한 모든 누적 비용 zi를 알고 있다고 가정합니다. 또한 입력 비용 래스터에서 중앙 셀의 경사 값 S를 알 수 있습니다.
예를 들어, z5에 대한 근사치 중 하나는 아래 그림과 같이 z3 및 z5 간의 대각선을 따라 있을 수 있습니다. 여기서 z5 = z3 + 1.4 * 셀 크기 * S입니다. 이 경우 입력 비용 래스터 값인 S는 삼각형 abc의 경사로 해석됩니다. 이러한 모든 네트워크 스타일 근사치의 경우 z5의 경사만 사용하여 z5의 누적 비용을 근사화합니다. 이는 셀 쌍의 평균 비용을 사용하는 레거시 네트워크 알고리즘과는 다릅니다.
아래 세 그림의 순서에 나와 있는 대로 기존 높이 쌍을 사용하는 4개의 네트워크 근사치를 포함하여 8개의 네트워크 근사치를 만들 수 있습니다. 이 경우 셀 z5의 위치에서 입력 비용 래스터의 값은 두 기지점 및 알 수 없는 고도 z5를 통과하는 평면 기울기의 크기 S로 해석됩니다. 이 관계를 사용해 z5를 도출할 수 있습니다. 이 단계가 Eikonal 단계입니다.
평면 기울기의 크기가 계산됩니다.
기울기의 방향이 계산됩니다.
Eikonal 단계에서는 z5에서 경사면 방향 정보 또한 복구하며 이를 역방향이라고 합니다.
이제 중앙 셀의 고도에 대한 12개의 근사치가 있습니다. 그중 최소값이 선택되어 중앙 셀의 누적 비용 값 z5로 기록됩니다. 역방향 래스터를 요청한 경우 기울기의 경사면 방향(이전 단락에서 설명)이 결과 역방향 래스터의 해당 위치에 기록됩니다.
이 과정은 해당 인접 피처 중 하나에 대한 새 고도 값을 얻을 때마다 각 셀에 반복됩니다. 결과적으로 고도 값 변경이 중지되고 알고리즘이 종료됩니다. 초기 고도는 시작지점에서 제공합니다. 즉, 0이거나 시작지점당 초기 누적 값입니다. 다른 초기 고도 값은 무한대로 설정됩니다. 자세한 내용은 Sethian(1999)에 설명되어 있습니다. 이에 대한 Esri 구현은 Sethian(1999) 및 Zhao(2004)에 설명된 기술의 조합입니다.
요약하자면, 이 단계는 각 셀의 경사에서 시작해 누적 비용 표면의 고도와 가장 가파른 내리막 방향 모두를 재생성합니다.
최저 비용 경로
최저 비용 경로는 누적 비용 표면에서 가장 가파른 내리막 방향을 따릅니다. 하나의 셀에 대한 해당 방향이 위의 그림 8에 나와 있습니다. 결과 역방향 래스터는 각 셀에 대한 해당 방향을 저장합니다. 역방향 래스터를 입력으로 사용하는 라인 형식 최적 경로 도구를 통해 비시작지점 셀에서 시작하는 이러한 경로를 플롯할 수 있습니다.
아래 그림에는 오른쪽 상단의 파란색 비시작지점 셀 d에서 시작하여 하단 시작지점 셀 s로 이동하는 곡선 최저 비용 경로가 나와 있습니다. d는 기하학적으로 상단 시작지점에 더 가깝지만, 해당 시작지점 주변의 높은 비용 때문에 곡선 경로를 따라 s로 이동하는 것이 더 저렴합니다.
목적지 d는 파란색 사각형입니다. 비용이 더 저렴한 영역을 통과하여 가장 저렴하게 접근할 수 있는 시작지점까지 이동하며, 이를 위해 비용이 높은 시작지점 주변으로 우회합니다.
이름이 의아하게 생각될 수도 있지만, 최저 비용 경로 구성을 위한 입력 위치를 목적지라고 합니다. 시작지점은 표면을 구성하는 데 사용되었으며 최저 비용 경로가 종료되는 위치입니다.
시작지점 주변의 할당 구역은 목적지에서 최저 비용 경로가 상단 시작지점이 아닌 하단 시작지점으로 이동하는 것을 더욱 명확히 합니다. 다음으로는 선택한 영역이 확대되어 역방향 래스터의 셀 값이 어떻게 해석되는지 보여줍니다.
역방향 셀 중심을 연결하는 격자 구조는 진한 회색으로 표시됩니다. 셀 장애물은 연한 회색으로 표시되며 셀 값은 방위각 화살표로 표시됩니다. 최저 비용 경로는 격자 구조 라인을 통과하므로 이동 방향에서 가장 가까운 역방향 셀의 방위각을 사용하여 해당 방향을 업데이트합니다. 셀 a 옆의 상단 경로 버텍스에서 a에 저장된 역방향 값은 해당 버텍스를 떠나는 라인의 방향을 지정하는 데 사용됩니다. 교차할 다음 격자 구조 라인은 셀 b에 가장 가깝기 때문에 해당 방위각은 두 번째 버텍스를 나가는 데 사용되는 식입니다.
요약하자면 최저 비용 경로는 셀 중심에서 시작하고 종료됩니다. 다른 경로 버텍스는 셀 중심을 통과하는 수평 및 수직 라인 격자 구조의 어느 지점에나 있을 수 있습니다.
유효 경사 계산
이전 섹션에서 설명한 경사 값은 반드시 입력 비용 마찰 래스터에서 나온 값은 아닙니다. 표면 재생성 알고리즘에서 사용되는 유효 경사를 함께 결정하는 다른 입력이 몇 가지 있습니다. 셀을 통과하는 이동 방향 및 시작지점에서 또는 시작지점으로의 이동 방향을 고려하는 것의 중요성을 비롯하여 이러한 입력에 대한 자세한 설명은 다른 항목에서 확인할 수 있습니다. 여기서는 표면 재생성 알고리즘에서 입력을 사용하는 방법에 중점을 둡니다. 입력은 다음과 같습니다.
- 비용 마찰 입력, C
- 표면 입력, S
- 시작지점 비용 승수, M
- 수평 계수 함수, HF
- 수직 계수 함수, VF
재생성 알고리즘에서 사용되는 유효 경사의 일반적인 형식은 다음과 같습니다.
유효 경사 = C * S * M * HF * VF
그런 다음 이 값에 셀 크기 또는 sqrt(2) * 셀 크기를 곱하고 기존 높이에 더해 네트워크 방향 높이 추정치 중 하나를 얻습니다. Eikonal 단계의 높이 추정치는 더 복잡한 유효 경사 함수를 사용하여 얻습니다.
유효 경사에는 누적 비용 단위를 선형 거리로 나눈 비율이 있어야 합니다. 예를 들어 누적 비용 표면이 이동 시간을 시간 단위로 측정하고 분석 셀 크기가 미터 단위인 경우 유효 경사에는 시간/미터 단위가 있어야 합니다.
유효 경사는 여러 항의 곱이므로 올바른 유효 경사 단위를 생성하려면 개별 항의 단위를 결합해야 합니다. 예를 들어 방향과 관계없이 이동 시간을 설명하기 위해 단순 비용 마찰 래스터만 사용하는 경우 비용 마찰 래스터 셀 값은 시간/미터 단위를 가져야 합니다. 또는 Tobler의 하이킹 함수를 수직 계수 함수로 사용하는 경우 하이킹 함수의 단위는 시간/미터이며, 비용 마찰 표면(있는 경우)은 단위 없는 가중치로 해석해야 합니다. 그런 다음 비용 마찰 셀 값이 해당 방식으로 해석될 수 있는지 확인해야 합니다. 즉, 수직 계수와 비용 마찰이 둘 다 비율일 수는 없습니다.
표면 입력(S)은 직접 제어하지 않습니다. 이 입력은 셀 중심 간의 실제 3D 표면 거리를 다루기 위해 셀 크기를 늘리는 단위 없는 가중치입니다. 그림 2에서 표면 재생성 알고리즘은 인접 피처 셀에 대해 가정된 알려진 높이와 중앙 셀에서 입력 비용 마찰 래스터의 경사를 함께 사용하여 해당 높이에 대한 여러 근사치를 만들어 중앙 셀에 대한 높이 z5를 계산합니다.
장애물은 엣지로 연결됨
거리 누적 및 거리 할당 도구의 장애물은 통과할 수 없는 입력 셀입니다. 이러한 장애물은 계산 중에 NoData 셀로 표시됩니다. 이는 도구 매개변수로 명시적으로 표시되거나, 다른 래스터 입력(예시: 비용 마찰 래스터) 중 하나에서 암시적으로 NoData 값으로 표시됩니다. 첫 번째 경우 이러한 장애물은 래스터화되어 비용 래스터에서 NoData로 전환됩니다. 재생성 알고리즘은 장애물 셀의 높이 추정치를 낮출 수 없으므로 대신 그 주변을 돌아가는 방법을 찾습니다.
표면 재생성 알고리즘은 셀의 8개 인접 피처 모두를 사용하여 높이 추정치를 찾습니다. 모서리가 연결된 장애물 인접 피처는 대각선 인접 피처가 높이 추정치를 얻는 데 사용되지 못하도록 방지하지 않습니다. 아래 이미지를 보면 셀 z2 및 z6이 장애물인 경우에도 z3에서 z5에 대한 높이 추정치를 얻을 수 있습니다.
z2 및 z6이 운하나 강과 같은 선형 장애물 피처의 일부인 경우 이러한 동작은 장애물의 의도를 무효화합니다. 이를 방지하기 위해 표면 재생성 알고리즘은 비장애물 셀 연결보다 장애물 셀 연결을 선호합니다. 즉, 추가 NoData 셀이 비용 래스터에 도입되어 모든 기존 장애물 셀이 엣지를 공유하도록 합니다. 위 이미지에서는 셀 z5 또는 셀 z3도 장애물 셀이 됩니다.
분석에서 장애물을 사용하는 경우, 이러한 동작을 검토하고 그에 따라 분석 셀 크기를 조정하여 의도한 장애물 주변 연결이 유지되도록 합니다. 포컬 통계 도구를 통해 선형 피처의 래스터 버전을 강화하여 인접한 장애물 셀에 의해 중단되어서는 안 되는 장애물 또는 선형 네트워크로 사용할 수 있습니다.
참조
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, pages 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 (June 1, 1999)
Warntz, W. "Transportation, Social Physics, and the Law Of Refraction", The Professional Geographer, 1957, Vol. 9, No. 4, pp. 2-7.
Zhao, H. "A fast sweeping method for Eikonal equations", Mathematics of Computation, 2004, Vol. 74, No. 250, pages 603-627