도로중심선에 대한 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단계를 거친 결과가 바로 아래의 그림이라는 점입니다. 이 그림을 통해 노드와 링크에 대한 테이블에 대한 정보는 아래와 같은데, 먼저 노드에 대한 테이블 정보입니다..
다음은 링크에 대한 테이블 정보입니다.
여기서 한가지 더, 선택적으로 고려해야할 부분이 있습니다. 즉, Undershot 문제인데요. 아래의 이미지를 먼저 살펴보시기 바랍니다.
Undershot이란 위의 이미지에서 왼쪽처럼, 두개의 폴리라인이 만나야 하지만 편집자의 실수로 약간 이격이 발생한 경우입니다. 이때 프로그램으로 이 이격을 제거해주는 작업이 필요합니다.
위 2개의 노드와 링크에 대한 테이블 정보를 통해 최단거리를 얻기 위한 알고리즘의 입력값이 준비된 셈입니다.