원가거리분석

Cost distance analysis
이 항목에 대한 자세한 내용은 근접도 분석을 참조하십시오.

공간분석과 지리정보시스템에서 비용거리 분석이나 비용경로 분석은 제약이 없는(2차원) 공간을 통해 하나 이상의 최적 이동경로를 결정하는 방법이다.[1]최적 솔루션은 국지적 요인으로 인해 공간마다 차이가 나는 비용밀도 분야(선형 단위당 비용)를 바탕으로 노선 총비용을 최소화하는 것이다.따라서 거리의 마찰이라는 근본적인 지리적 원리에 기초하고 있다.대부분의 GIS 소프트웨어에서 구현되는 다중 결정론적 알고리즘 솔루션의 최적화 문제다.

비용 거리 분석의 다양한 문제, 알고리즘 및 도구는 제약이 없는 2차원 공간에서 작동하는데, 이는 경로가 어떤 형태든 될 수 있다는 것을 의미한다.제약된 공간, 특히 도로나 통신망과 같은 1차원 선형 네트워크에서도 유사한 비용 최적화 문제가 발생할 수 있다.원칙적으로 비슷하지만 네트워크 공간의 문제들은 주로 그래프 이론에서 채택된 매우 다른 (보통 더 간단한) 알고리즘을 해결해야 한다.이러한 문제를 해결하기 위한 GIS 도구 모음을 네트워크 분석이라고 한다.

역사

인간은 최소한의 노력과 시간으로 여행하려는 선천적인 욕구를 가지고 있는 것 같다.역사적으로, 심지어 고대의 도로도 평평한 공간을 가로질러 곧장 이동하지만 산, 협곡, 그리고 두꺼운 식물을 휘감아 현대적인 계산 알고리즘이 만들어낼 것과 유사한 패턴을 보여준다.

그러나 지리학자들은 20세기에 이르러서야 이 경로 최적화를 설명하기 위한 이론과 이를 재현하기 위한 알고리즘을 개발하였다.1957년 지리 정량적 혁명 동안 윌리엄 워츠는 "힘든" 과학(사회 물리학으로 알려져 있음)으로부터 원리나 수학적인 형식주의를 채택하는 경향과 함께, 여행 비용을 최소화하면 어떻게 두 풍경 사이의 경계에서 교통로가 방향을 바꾸게 되는지에 대한 비유로 굴절을 사용했다.y 서로 다른 거리 마찰(예: 숲에서 대초원으로 부상)[2]비용을 최소화하기 위해 방향을 바꾸는 그의 '파시모닉 운동' 원칙은 널리 받아들여졌지만 굴절 유추와 수학(스넬의 법칙)은 그렇지 않은 것이 보통 복잡한 지리적 상황에 맞게 잘 확장되지 않기 때문이다.[3]

그 후 워츠 등은 우주에 걸쳐 여행 비용이 지속적으로 변동하는 일반적인 상황에서 지형과 비교함으로써 훨씬 더 성공적이라는 것을 증명하는 또 다른 비유를 채택했다.[4]그들은 비용율(즉, 단위 거리당 비용, 시간일 경우 속도의 역방향)을 지형 표면의 기울기(즉, 단위 거리당 고도 변화)와 비교했다. 두 가지 모두 축적된 함수 또는 영역의 수학 파생 모델: 지형의 경우 수직 기준점(해상 수준) 위의 총 고도였다.주어진 출발점에서부터 비용율 필드를 통합하면 해당 지점에서 총 누적 이동비용의 유사한 표면이 생성될 것이다.스트림이 최소 저항 내리막길을 따라가는 것과 마찬가지로, 어떤 지점 "아래"에서 소스로의 비용 축적 표면의 능률화는 최소 비용 경로가 될 것이다.[5][6]1960년대 추가 연구 라인은 다양한 지리적 특성에 의해 그것이 어떻게 영향을 받았는지를 연구하면서 거리의 마찰 개념의 발현으로서 비용율 영역의 성격을 더욱 발전시켰다.[7]

당시 이 솔루션은 이론적인 수준에 그쳐 연속적인 솔루션에 대한 데이터와 컴퓨팅 능력이 부족했다.래스터 GIS는 연속적 통합을 이산적 합계 절차로 전환함으로써 이론적 솔루션을 구현하기 위한 실현 가능한 최초의 플랫폼을 제공했다.다나 톰린은 1986년까지 지도 분석 패키지에서 비용 거리 분석을 실시했고, 로널드 이스트만은 1989년까지 IDRISI에 이를 추가해 보다 효율적인 "푸시브룸" 비용 축적 알고리즘을 적용했다.[8]더글러스(1994)는 축적 알고리즘을 더욱 정교하게 다듬었는데, 이는 기본적으로 현재 대부분의 GIS 소프트웨어에서 구현되는 것이다.[9]

코스트 래스터

일반적인 GIS 비용 경로 분석의 흐름도
참고 항목:거리 마찰

비용 거리 분석에 사용되는 일차 데이터 세트는 통과 비용 표면,[9] 마찰 이미지,[8] 비용 비율 필드 또는 비용 표면이라고도 하는 비용 래스터다.대부분의 구현에서 이것은 래스터 그리드로, 각 셀의 가치가 수평 또는 수직 방향으로 셀을 가로지르는 경로의 비용(즉, 시간, 돈 또는 에너지 등)을 나타낸다.[10]따라서 공간 집약적인 속성인 원가율 분야(선형 단위당 비용)를 탈피한 것이다.이 비용은 거리 마찰 원리의 발현이다.

주어진 라우팅 문제와 관련하여 다양한 유형의 비용이 관련될 수 있다.

  • 이동 비용, 셀을 가로질러 이동하는 데 필요한 자원 지출, 일반적으로 시간 또는 에너지/연료.
  • 도로, 파이프 및 케이블과 같이 이동을 가능하게 하는 기반시설을 건설하는 데 필요한 공사비(일반적으로 통화)일부 공사비(예: 포장재)는 일정하지만, 다른 것은 재산 취득이나 굴착과 같이 공간적으로 변형된 것이다.
  • 환경에 미치는 영향, 기반구조나 그것을 따라 이동하는 여행에 의해 자연 또는 인간 환경에 미치는 부정적인 영향.예를 들어 주택가나 습지를 통한 고속도로 건설은 (환경영향평가, 시위, 소송 등의 형태로) 높은 정치적 비용이 발생할 수 있다.

이러한 비용 중 일부는 운송 시간, 연료 소비량, 건설 비용 등 쉽게 수량화할 수 있고 측정할 수 있기 때문에 자연스럽게 계산 솔루션에 자신을 빌려준다.그렇기는 하지만, 노선을 구현하기 전에 비용을 예측하는 데 상당한 불확실성이 있을 수 있다.다른 비용들은 정치적 항의나 생태학적 영향과 같은 질적 또는 주관적 성격 때문에 측정하기가 훨씬 더 어렵다. 이러한 비용들은 일반적으로 척도 형성을 통한 운영화가 필요하다.[11]

많은 상황에서 복수의 유형의 원가가 동시에 관련될 수 있으며, 총원가는 그 조합이다.서로 다른 원가는 다른 단위로 표시되기 때문에(또는 척도의 경우 전혀 단위가 없기 때문에) 대개는 직접 합계가 불가능하지만 지수를 만들어 결합해야 한다.공통 유형의 지수는 각 요인을 일관된 범위(예: [0,1])로 확장한 다음 가중 선형 결합을 사용하여 결합함으로써 생성된다.이와 같은 인덱스 모델의 생성에서 중요한 부분은 보정(통계)이다. 분석 계층 프로세스와 같은 방법을 사용하여, 모델링된 상대적 비용이 실제 비용과 일치하도록 공식의 매개변수를 조정한다.지수 모델 공식은 일반적으로 래스터 GIS에서 각 비용 요소를 나타내는 래스터 그리드의 지도 대수 도구를 사용하여 구현되며, 단일 비용 래스터 그리드가 발생한다.

방향비용

주요 기사:애니소트로피

전통적인 방법의 한 가지 제한사항은 비용장이 동위원소 또는 전방향이라는 것이다: 주어진 위치에서의 비용은 통과 방향에 따라 달라지지 않는다.이것은 많은 상황에서 적절하지만 다른 상황에서는 적절하지 않다.예를 들어, 바람이 부는 장소에서 날고 있다면, 바람의 방향으로 날고 있는 비행기는 그것에 맞서 날고 있는 비행기보다 훨씬 더 낮은 비용을 초래한다.방향성 비용을 통합하기 위해 비용 거리 분석 알고리즘을 연장하는 연구가 일부 이뤄졌지만 아직 GIS 소프트웨어에서는 광범위하게 구현되지 않고 있다.[12] IDRISI는 음이소트로피를 지지한다.[1]

최소 비용 경로 알고리즘

가장 일반적인 비용 거리 과제는 주어진 원천 위치와 총 누적 비용이 가장 적은 목적지 위치 사이의 공간을 통한 단일 경로를 결정하는 것이다.대표적인 솔루션 알고리즘은 Warntz와 Lindgren의 비용 통합 전략의 이산 래스터 구현으로 결정론적(NP-완전성) 최적화다.[5][10]

  1. 입력: 비용 필드 래스터, 소스 위치, 대상 위치(대부분의 구현으로 여러 소스와 대상을 동시에 해결할 수 있음)
  2. 축적:소스 위치에서 시작하여 그리드의 다른 모든 셀에 도달하는 데 필요한 최저 총 비용을 계산한다.이스트먼과 더글러스에서 발표한 것과 같은 몇 가지 알고리즘이 있지만,[8][9] 일반적으로 비슷한 전략을 따른다.[13]또한 이 과정은 중요한 부산물로서 백링크 그리드(Esri) 또는 이동방향 그리드(GRASS)라고 불리는 두 번째 래스터 그리드를 생성하는데, 이 그리드는 각 셀에 가장 낮은 비용을 가진 이웃 8개 중 어느 쪽을 나타내는 방향 코드(0-7)가 있다.
    1. 이미 할당된 누적 비용이 있는 하나 이상의 셀에 인접한 셀 찾기(초기에는 소스 셀만 해당)
    2. 누적 비용이 가장 낮은 이웃을 결정한다.백링크 그리드에서 타겟에서 최저가 이웃으로 가는 방향을 인코딩한다.
    3. 대상 셀의 누적 비용(또는 대상 셀과 인접 셀의 평균 비용)을 이웃의 누적 비용에 더하여 대상 셀의 누적 비용을 생성한다.이웃이 대각선인 경우 국부비용에 multiplied2를 곱한다.
    4. 알고리즘은 또한 간접 경로가 더 낮은 비용을 가질 수 있다는 점을 고려해야 하며, 종종 재고할 수 있는 확장된 계산의 가장자리를 따라 임시 비용 값을 추적하기 위해 해시 테이블을 사용한다.
    5. 모든 셀이 할당될 때까지 절차를 반복하십시오.
  3. 배수: 지형 유추에 따라 지정된 목적지에서 소스로 되돌아오는 최적의 경로를 추적하십시오. 마치 어떤 위치에서 흘러나오는 스트림처럼.가장 기본적으로는 목적지 셀에서 시작하여 백링크 그리드에 표시된 방향으로 이동한 후 다음 셀에 대해 반복하여 소스에 도달할 때까지 수행된다.최근의 소프트웨어는 8개의 이웃 방향 이외의 각도에서 직선을 인식하기 위해 3개 이상의 셀을 가로질러 보는 것과 같은 몇 가지 개선점을 추가했다.예를 들어 GRASS의 r.walk 기능은 "나이트의 이동"(한 셀은 직선으로, 한 셀은 대각선으로)을 인식하고 중간 셀을 우회하여 직선을 그릴 수 있다.

코리더 분석

저비용 및 중간비용 코리더가 음영 처리된 GIS의 비용 코리더 분석 절차 흐름도

모호한 버전으로 간주될 수 있는 최소 비용 경로 문제의 약간 다른 버전은 둘 이상의 셀 폭을 찾아 결과를 적용하는데 어느 정도 유연성을 제공하는 것이다.복도는 일반적으로 교통 계획과 야생동물 관리에 사용된다.

이 문제의 해결책은 연구 공간의 모든 셀에 대해 해당 셀을 통과하는 특정 소스와 목적지 사이의 최적 경로에 대한 총 누적 비용을 계산하는 것이다.따라서 위에서 도출한 최적 경로의 모든 셀은 동일한 최소값을 가질 것이다.이 경로 근처의 셀은 최적 경로에서 약간만 벗어난 경로에 의해 도달될 수 있으므로, 상대적으로 낮은 비용 값을 가지며, 더 먼 거리의 셀이 비용 값을 증가시키므로 가장자리가 퍼지도록 회랑을 형성할 것이다.

이 코리더 필드를 도출하는 알고리즘은 위에서 설명한 선원을 사용하는 두 가지 비용 축적 그리드를 생성하여 생성된다.그런 다음 알고리즘이 반복되지만 대상을 소스로 사용한다.그리고 지도 대수학을 사용하여 이 두 그리드를 추가한다.이는 각 셀에 대해 해당 셀을 통과하는 최적의 소스-대상 경로가 해당 셀에서 소스로의 최적 경로로, 해당 셀에서 목적지까지의 최적 경로에 추가되기 때문이다.ArcGIS가 프로세스를 자동화하는 코리더 도구를 제공하지만 지도 대수 도구와 함께 위의 비용 축적 도구를 사용하여 이를 달성할 수 있다.

비용 기반 할당

비용 축적 알고리즘의 또 다른 용도는 각 셀이 최저 비용으로 도달할 수 있는 소스에 할당되어 각 소스가 "가장 필요한" 일련의 지역을 만드는 다중 소스 사이의 공간을 분할하는 것이다.지형 유추에서 이러한 용어는 분수령(따라서 이를 "비용 손실"이라고 부를 수 있지만, 이 용어는 일반적인 용어가 아니다)에 해당된다.그것들은 본질적으로 일정한 비용이 드는 공간에 대한 할당인 보로노이 도표와 직접 관련이 있다.그것들은 또한 네트워크 분석을 위한 위치 할당 도구와 개념적으로 유사하다(계산적으로가 아닐 경우).

비용 기반 할당은 두 가지 방법을 사용하여 만들 수 있다.첫 번째는 백링크 그리드를 할당 그리드에 대체하는 비용 축적 알고리즘의 수정된 버전을 사용하는 것인데, 이 알고리즘은 각 셀에 가장 저렴한 이웃의 동일한 소스 식별자가 할당되어 각 소스의 도메인이 서로 만날 때까지 점진적으로 성장하게 한다.이것은 ArcGIS Pro에서 취한 접근법이다.[14]두 번째 해결책은 우선 기본 축적 알고리즘을 실행한 다음, 백링크 그리드를 사용하여 각 셀이 "흐름"하는 소스를 결정하는 것이다. GRASS GIS는 이 접근법을 사용한다. 사실, 지형의 분수령을 계산하는 데도 동일한 도구를 사용한다.[15]

구현

비용 거리 도구는 대부분의 래스터 GIS 소프트웨어에서 이용할 수 있다.

  • GRASS GIS(종종 QGIS에 번들로 제공됨), 별도 누적(R.cost) 및 배수(r. walk) 기능 포함
  • ArcGIS Desktop 및 ArcGIS Pro, 코리더 생성뿐만 아니라 별도의 축적(비용 거리) 및 배수(비용 경로) 지프로세싱 도구 포함.최근에는 ArcGIS Pro 버전 2.5를 시작으로 보다 유연한 옵션과 함께 보다 고급 알고리즘을 사용하는 새로운 비용 거리 툴 세트가 도입되었다.[16]
  • TerrSet(구 Idrisi)는 여러 가지 도구를 가지고 있어 비등방성(방향) 비용 등 다양한 종류의 비용 거리 문제를 해결하기 위한 다양한 알고리즘을 구현하고 있다.[17]

참조

  1. ^ a b de Smith, Michael, Paul Longley, Michael Goodchild (2018) Cost Distance, Geospatial Analysis, 6판
  2. ^ Warntz, William (1957). "Transportation, Social Physics, and the Law of Refraction". The Professional Geographer. 9 (4): 2–7. doi:10.1111/j.0033-0124.1957.094_2.x.
  3. ^ Bunge, William (1966). Theoretical Geography. Lund, Sweden: Berlingsta Botryckeriet. p. 128.
  4. ^ 워츠, 윌리엄 (1965) "표면, 경로 및 지리적 문제에 대한 적용에 관한 노트, IMAGE 토론서 #6, 앤아버:미시간 대학간 수학 지리학자 협회
  5. ^ a b Lindgren, Ernesto S. (1967). "Proposed solution for the minimum path problem". Harvard Papers in Theoretical Geography, Geography and the Properties of Surface Series. 4.
  6. ^ Lindgren, Ernesto S. (1967). "A minimum path problem reconsidered". Harvard Papers in Theoretical Geography, Geography and the Properties of Surface Series. 28.
  7. ^ Huff, David L.; Jenks, George F. (1968). "Graphic interpretation of the friction of distance in gravity models". Annals of the Association of American Geographers. 58 (4): 814. doi:10.1111/j.1467-8306.1968.tb01670.x.
  8. ^ a b c 래스터 그리드의 거리 계산을 위한 Eastman J R (1989) 푸시브룸 알고리즘.절차, AutoCarto 9 페이지 288-97
  9. ^ a b c Douglas, David H. (1994). "Least-cost Path in GIS Using an Accumulated Cost Surface and Slopelines". Cartographica. 31 (3): 37–51. doi:10.3138/D327-0323-2JUT-016M.
  10. ^ a b Bolstad, Paul (2008). GIS Fundamentals: A First Text on Geographic Information Systems (3rd ed.). Eider Press. pp. 404–408. ISBN 978-0-9717647-2-9.
  11. ^ G.H.피리(2009) 디스턴스, 롭 키친, 나이젤 레프렛 (eds)국제 인문 지리 백과사전, 엘스비어, 페이지 242-251. 도이:10.1016/B978-008044910-4.00265-0
  12. ^ Collischonn, Walter; Pilar, Jorge Victor (2000). "A direction dependent least-cost-path algorithm for roads and canals". International Journal of Geographical Information Science. 14 (4): 397–407. doi:10.1080/13658810050024304. S2CID 37823291.
  13. ^ "How cost distance tools work". ArcGIS Pro Documentation. Esri. Retrieved 29 December 2020.
  14. ^ "Cost Allocation (Spatial Analyst)". ArcGIS Pro Documentation. Esri. Retrieved 30 December 2020.
  15. ^ "r.watershed". GRASS GIS Documentation. Retrieved 30 December 2020.
  16. ^ "An overview of the Distance toolset". ArcGIS Pro Documentation. Esri. Retrieved 29 December 2020.
  17. ^ 이스트만, J. 로날드, 테르셋 설명서, 페이지 115, 227, 356

외부 링크