GIS Developer

2016-01-23

0.7661204512466478

2016-01-212017-02-01

이제 앞서서 도로중심선을 이용해 구축한 Network DB를 기반으로 최단 거리를 찾는 툴을 소개합니다. 이 툴은 필자가 인터넷에서 소개된 A* 알고리즘 내용을 학습하고 직접 개발한 툴입니다. A* 알고리즘은 별도의 글(A* Algorithm)을 통해 설명을 드리겠지만, 한줄로 요약한다면, 최선의 길을 찾으려는 지속적인 노력과 시행 착오를 통한 개선을 통해 결국 최단경로를 찾는 알고리즘이라고 할 수 있습니다. 이 알고리즘을 이해하게 되면 이 한줄의 정의에 대해 고개를 끄덕이게 될거라 생각됩니다. 이 알고리즘에 대해 더 자세한 내용은 다른 많은 글을 통해 설명되어 있으니 당장 궁금한 분들은 검색을 통해 찾아 보시기 바랍니다. 이 툴은 다음과 같은 네트워크 DB를 사용합니다.

위의 파일들이 포함된 폴더를 선택하고 시작 노드와 도착 노드를 클릭해서 선택하게 되면 다음과 같이 최단 경로가 표시됩니다.

아래는 또 다른 최단 경로에 대한 검색 결과(소요소간 약 1.8초)입니다.

지금까지 도로중심선을 이용해 노트워크 DB를 생성하고 최단경로 알고리즘인 A*를 직접 구현한 툴을 소개해 보았습니다.

2016-01-212017-01-26

도로중심선만으로 네트워크 데이터 구축하기 ㅡ 2/3

단순 선형 데이터인 도로중심선을 이용해 노드와 링크 DB를 생성하기 위한 툴을 DuraMap-Xr을 이용해 개발하였습니다. 아래는 해당 툴의 화면입니다.

이 툴을 이용해서, 입력된 도로중심선에 대해 생성된 Node와 link 데이터를 표현해 보면 아래와 같습니다. 먼저 입력된 도로중심선입니다.

위의 도로중심선이 아래처럼 노드와 링크 데이터로 분리되어 생성됩니다.

생성된 노드 DB에 대한 속성 데이터는 아래와 같습니다. 노드에 표시된 숫자는 각 노드에 연결돈 링크의 개수입니다.

그리고 링크 DB에 대한 속성 데이터는 아래와 같습니다.

그러나 위의 노드와 링크에 대한 SHP 파일만을 가지고는 최단 경로 찾기에 대한 알고리즘(A*)을 효율적으로 적용하기 어렵습니다. 특히 Link에 대해서는 빠르고 효율적인 Node 참조가 가능 수 있도록 SQLite와 같은 DBMS에 저장해 둘 필요가 있으며 이러한 목적으로 아래와 같은 툴을 사용하여 Link에 대한 데이터를 SQLite 파일로 생성할 수 있습니다.

위의 SQLite 파일안에는 Link 테이블이 존재하며 Link에 대한 SHP 파일 중 도형 정보 이외의 속성정보를 그대로 가지고 있습니다. 또한 LinkID와 StartNode 그리고 EndNode에 대한 인덱싱 정보를 가지고 있어서 빠른 Query가 가능합니다. 이로써 최단 경로 알고리즘에서 사용하기 위한 기본적인 노드, 링크에 대한 데이터 파일이 준비되었습니다.

2016-01-202017-01-26

도로중심선만으로 네트워크 데이터 구축하기 ㅡ 1/3

도로중심선에 대한 SHP 파일을 통해 노드와 링크 데이터로 구성된 네트워크 데이터를 구축하고자 합니다. 이 목표를 이루기 위해서 3단계의 과정으로 나눠 정리를 하였습니다. 추후 이 3단계 과정을 실제 구현하여 실제로 네트워크 데이터를 구축할 것이고, C# 또는 Java언어를 통해 출발점과 종착점에 대한 최단 거리를 얻을 수 있는, 프로그램에 쉽게 적용할 수 있는 라이브러리를 만들 것이고, 이 라이브러리를 통해 기존의 GIS 엔진중 공간서버와 모바일 GIS 엔진에 최단거리에 대한 기능을 추가할 것입니다.

앞서 3단계의 과정을 언급하였는데요. 먼저 1단계입니다. 아래 그림을 통해 설명하면…

좌측 그림은 원래의 도로중심선입니다. 3개로 구성되어 있습니다. 이해를 돕고자, 폴리라인이 떨어져 보이도록 표시했는데, 붙어 있다고 생각하시기 바랍니다. 결국, 1단계를 거치게 되면 우측처럼 6개의 폴리라인으로 분리됩니다. 즉, 폴리라인의 모든 교차점은 잘려진다가 바로 1단계의 결과입니다. 다음은 2단계를 설명하기 위한 그림입니다.

위의 그림에서, 좌측은 원래의 도로중심선입니다. 2개의 폴리라인으로 구성되어져 있는데, 떨어져 보이도록 구성했으나 원래는 붙어 있다고 생각하시기 바랍니다. 결국, 2단계를 거치게 되면 우측처럼 1개의 폴리라인으로 합쳐집니다. 즉, 단 2개의 폴리라인만이 양 끝지점에서 교차할 경우 하나의 폴리라인으로 만든다가 2단계의 결과입니다. 다음은 마지막 3단계에 대한 설명을 위한 그림 3개 입니다.

위의 그림은 이 글의 가장 처음에 등장한 1단계에서의 그림에서 우측에 해당하는 그림으로 노드는 빨간색 원으로 표기했고, 링크는 노란색 원으로 표기한 것입니다. 총 7개의 노드와 6개의 링크로 구성되어져 있습니다. 어떻한 경우이든 1단계와 2단계를 거친 결과가 바로 아래의 그림이라는 점입니다. 이 그림을 통해 노드와 링크에 대한 테이블에 대한 정보는 아래와 같은데, 먼저 노드에 대한 테이블 정보입니다..