실시간 반응형 등시선도(Realtime Interactive Isochrone Map) 그리기

글 : 김승범 

몇 단계를 거쳐 <실시간 반응형 등시선도>를 그린 과정을 설명하려고 한다. 마우스를 지도 위에서 움직이면 해당 지점을 중심으로 다른 곳들이 시간적으로 얼마만큼 걸리는지를 보여주는 지도다.

등시선도(isochrone map)라는 용어는 많은 사람들에게 익숙하지 않을 수도 있는데, 한 지점으로부터 도달시간이 같은 지점들을 연속적인 선으로 이어서 표현한 지도다. 다른 예로 등고선, 즉 해발고도가 같은 지점들을 이은 지도를 쉽게 떠올릴 수 있다면 등시선도는 등고선의 높이 대신 시간을 바탕으로 그린 지도라고 생각하면 된다.

등시선도는 어디에 쓸까

이런 지도의 쓰임새 중 하나는 다음의 링크에서 잘 설명해준다.

https://blog.conveyal.com/shaping-conversations-about-transit-with-interactive-isochrone-mapping-1d6530d6a8a4

영문이라 빠르게 읽어내려가기 어려울 수도 있지만, 구글 크롬에 내장된 번역 기능만으로도 주요한 포인트들을 잡아내기에 충분하다.

단지 미리 준비된 한 장의 지도로도 어느 정도의 정보를 보여줄 수도 있겠지만, 실시간으로 사용자 조작에 의해 결과를 볼 수 있는 지도는, 보는 사람으로 하여금 시간 거리의 공간적 불균형을 좀 더 직관적으로 이해하게 해준다는 장점이 있다. 계산에 의해 도출된 결정적 수치도 중요한 쓰임새가 있겠지만, 그림으로 표현한다는건 많은 경우 누군가를 이해시키는데 목적이 있고, 그렇기 때문에 의사소통에 있어서 좀 더 중요한 의미를 지닌다. 이런 종류의 시각화들은 결국 사람이 스스로 판단할 수 있는 선택의 자율성을 갖추는데 도움이 되기 때문이다. 

예를 들어 아래 링크글의 중간 즈음에 있는 IGEOLISE 지도는 두 장소의 등시선도를 보여줌으로써 두 사람이 만나는 약속 장소를 잡는데 도움을 줄 수 있다. 정확히 시간이 똑같이 걸리는 지점을 계산하는건 약간 다른 종류의 일이겠지만, 아마도 보통의 사람들이라면 이 지도를 보고 적당히 마음에 드는 중간 지점을 찾으려 할 것 같다. 아, 물론 좀 더 보통의 사람들은 약속을 잡는데 굳이 이런 지도를 보는것조차 귀찮아 할 것 같지만.

[IGEOLISE에서 런던 두 지점으로부터의 30분 거리 등시선도를 그린 그림]

물론, 굳이 약속장소를 찾는 일이 아니라도 어떤 두 장소, 혹은 다수의 장소에서 도보로 10분 거리는 어떻게 다를지 비교해 볼 수도 있겠다. 공공의 입장이라면 불균형적으로 분포된 교통체계를 개선하는데 사용할 수도 있겠고, 주민들이라면 이런 자료를 근거로 상대적으로 취약한 자기 동네의 공공서비스 개선을 요구할 수도 있을 것 같다. 쓰임새는 무척 다양하다.

등시선도는 여러 지점들에서 측정된 시간값을 바탕으로 그릴 수 있다

[시간값 지도]

중고등학교 시절 수업 시간에 높이가 몇 개 지점에 표시된 지도에 등고선을 그려보는 연습을 했던 기억이 있다. 등시선도도 마찬가지 방식으로 그린다. 다만, 그 작업을 컴퓨터에게 시켜야 하기 때문에 좀 더 논리적인 절차를 생각해봐야 한다. 

물론, 이런 작업은 이미 여기저기서 많이 해왔기 때문에 누군가 이미 좋은 프로그램을 만들어 놓았을 것이라 생각하면 대부분 틀리지 않다. Qgis에서 시간값이 있는 point 파일이 있다면, contour 플러그인을 설치하여 쉽게 그릴 수 있다. 특정한 지점에 대해서 하나의 등시선도를 그리고 싶다면 이 방법이 가장 빠르고 쉽다. 클릭 몇 번만 하면 잠시 쉬려고 의자에 뒤로 기대기도 전에 화면 안에 라인이나 폴리곤의 콘타를 그려준다.

[QGIS에서 시간값 위에 그린 등시선도]

QGIS 플러그인은 1800장의 등시선도를 1분 안에 만들어낸다

그런데 문제에 부딪쳤다. 전국 지도에서 한 점을 중심으로 0분 부터 300분 거리까지의 등시선도를 30여초 동안 연속적으로 보여주는 영상을 만들려고 했는데, 1초에 60프레임을 보여주려면 30 x 60 = 1800 장의 등시선도가 필요했다. 

당시에는 QGIS에서 1800개의 linestring 으로 된 등시선도를 만든 후, 이를 읽어들여 한 프레임에 하나씩 보여주는 방법만을 알고 있었다. 약간 단순하고 무식해보여도, 1분 안에 1800개를 만들어주었기 때문에 사실은 그게 가장 빠르게 할 수 있는 방법이었다. 위에 있는 등시선도가 바로 1800개 선 중의 일부다.

그렇지만 출발 지점을 바꿀 때마다 일일이 수작업으로 그 일을 해야 한다는게 장기적으로는 시간낭비일 수 있기 때문에 좀 더 자동적으로 할 수 있는 방법을 찾아보기로 했다.

LINE TWEENING 방식으로 시도해보았다

처음에는 대여섯장의 등시선도를 그린 후 morphing(혹은 line tweening이라고도 함)의 방식으로 그 사이를 보간하여 보여주는 방법을 시도해보았다.

이미 자바스크립트로 구현해 놓은 좋은 사례들을 찾을 수 있었다. A에서 B 도형으로 변형하려고 할 때, 두 도형을 구성하는 정점의 수가 다르다면, 먼저 정점을 보간한다. 그 후, 변형이 자연스럽게 되도록,  A도형의 각 점에서 B도형 모든 점까지 거리제곱의 합이 최소가 되는 쌍을 찾아 상호간의 변형 상대 점들을 맺어주게 된다.

https://bl.ocks.org/veltman/4d1413aa5fd3bb5af1a806c146870031

그래서 구현한 것은 위와 같은 그림. 한 프레임 한 프레임은 매우 빠르게 계산되었지만 결과물이 자연스럽지 못했다.

처음부터 다시 시작하기

결국 모든 과정을 하나하나 백지에서부터 구현해보기로 했다.

등시선도를 그리기 위해 필요한 단계는 두 가지였고, 각 단계에서 핵심 알고리즘이 하나씩 필요했다.

첫번째로 도로 네트워크를 토대로 출발점을 입력하면 도로의 각 결절점까지 도달 시간을 구하는 일

두번째로는 그렇게 얻어진 각 점들의 값들을 토대로 등시선도를 그리는 일

최단거리 구하기 첫번째

일단 결절점까지의 도달시간은 GIS 소프트웨어나 라이브러리들의 네트워크 분석(혹은 graph tool)을 이용해서 뽑아낼 수 있다.  이미 기존에 routing 라이브러리들은 몇개 찾아보다가 API를 익히는 데에도 꽤 많은 시간이 걸리는데다가 정작 원하는 네트워크를 구성하려면 불편한 점들이 많다는 걸 깨달았었고, 그래서 시간을 내어 작성해놓았던 코드가 있었다.

다익스트라 알고리즘을 바탕으로 했고, 최적화시키지 못해서 한 점에서 전국의 40만개 노드까지의 최단 거리(SSSP : single source shortest path)를 구하는데 1500ms 정도나 걸렸는데 등시선 1800개를 그리는 목적을 달성하기 위해 이 작업은 전체 과정에서 한 번만 하면 되었기 때문에 크게 신경쓰지 않았다.

뒤에서 다시 설명하겠지만, 이 작업의 목적이 실시간 인터랙티브로 바뀌었을 때, 이 계산시간의 단축이 가장 중요한 이슈였고 50ms 정도까지 단축시킬 수 있게 된다.

등시선도 그리기 : Marching Square 알고리즘

등시선도를 그리는 방법 중에 찾아본 것은 두 가지였다.

첫번째는 marching square라고 하는 방식. 아래 링크에 구현방식을 잘 설명해놓은 글이 있다.

https://mrakow.wordpress.com/2015/11/30/isochrone-generation-with-the-google-maps-api-using-a-quadtree/

[marching square 방식의 등시선 그리기, 출처 : https://mrakow.wordpress.com/ ]

아래 글에서는 그 절차 하나하나와 주요한 개념들을 움직이는 그림들로 잘 설명해주고 있다.

http://jamie-wong.com/2014/08/19/metaballs-and-marching-squares/

선을 부드럽게 그려준다는 장점이 있는데, 시간 값이 있는 점들이 40만개쯤 있을 때, 빠르게 계산할 수 있을지 확신이 들지 않았다. 전체 공간을 잘게 나누어야 하는 과정이 필요했고, 한 화면에 볼 수 없는 매우 넓은 공간에서는 메모리 낭비를 막기 위해 쿼드트리를 이용해야 하는 등 몇 가지 절차가 더 필요했기 때문이다. 

d3.contour가 이 방식을 사용하고 있다.

https://observablehq.com/@d3/density-contours

https://github.com/d3/d3-contour

등시선도 그리기 준비 : 들로네 삼각화 알고리즘

두 번째는 들로네 삼각화(Delauney Triangulation) 후 그리는 방식. 

들로네 삼각화는 평면상의 점들을 토대로 평면을 삼각형으로 분할하는 알고리즘이다. 그래픽 작업에서 삼각형은 매우 중요한 기본 단위이기 때문에 들로네 삼각화 알고리즘은 여러 가지 목적에 광범위하게 쓰인다. 이 알고리즘은 임의의 세 점이 만들어내는 외접원에 다른 점이 포함되지 않도록 반복적인 검사를 통해 삼각형들을 생성해낸다. 물론 QGIS같은 프로그램에서도 이를 지원한다. 

[QGIS에서 생성한 들로네 삼각형]

들로네 삼각화로 그린 등시선도 결과물은 직선이지만, 측정된 정보들을 토대로 칼같이 그려주며 이미 웹 상에서 좋은 cpp 구현코드를 찾을 수 있었다는 장점이 있었다.

https://github.com/mapbox/delaunator

[출처 : Delaunator GITHUB ]

mapbox에서 만들어서 공개한 코드인데, 페이지 아래의 벤치마크를 보면 무척 빠르다. 고맙게도 그대로 cpp로 옮겨놓은 코드의 링크도 있다. 이 함수에서는 들로네 삼각화 후 등고선을 그리는데 필요한 모든 값들을 리턴해주고 있다.

40만개의 점을 계산하는데 400ms 정도가 소요되었는데, 출발점이 변경되더라도 들로네 삼각화는 전체 과정에서 딱 한번만 하면 되기 때문에 그 정도면 충분했다.

OpenGL Shader에서 등시선 그리기

이 작업은 모두 cpp 코드로 진행했고, 화면 출력은 OpenGL을 이용했다.

들로네 삼각화 후 OpenGL에서 등시선도를 그리는 일은, 삼각형 단위로 분할해서 독립적으로 계산할 수 있으며, 매우 간단한 비례식을 이용하면 된다.

예를 들어 30분 등시선도를 그리고자 한다면, 30이 포함되는 두 변을 찾고 그 안에서 비례식을 사용하여 좌표값을 결정해 준 후 두 선을 이으면 된다.

물론, 이와 같이 그냥 두 선을 이어서 화면상에 그리는 작업은 쉬운데, 계산한 선들을 연속적인 linestring으로 이어서 geojson 등으로 저장하는 작업, 그리고 polygon으로 저장하는 작업은 각각 별개의 복잡한 절차가 필요하다. 화면에 그리는 것으로 끝내는 방식은 삼각형 단위로 분할해서 독립적으로 계산하면 되었지만, 이 경우는 연속적으로 이어야 하기 때문에 인접 삼각형이 무엇인지 알아야 하고, 선들이 끝나는 맨 끝은 어떻게 처리할 것인지 고민해야 하기 때문이다. 다행히도 delaunator 함수는 이 작업에 필요한 모든 바탕 정보를 제공해주었다. 

delaunator는 한 선분을 따라갔을 때 다음 선분이 무엇이 되는지를 선분의 방향을 구분하여 쌍으로 제공한다. 글로 설명하기는 어렵지만 그림을 보면 대략적으로 이해할 수 있다. 가장자리에 있는 삼각형의 변들도 구분해낼 수 있다.

[half-edge로 정의된 개념이 어떻게 후속 작업에 이용될 수 있는지 설명해주고 있다]

[출처 : https://mapbox.github.io/delaunator/]

이번 경우에는 화면에 그리면 그만이었으므로, OpenGL의 geometry shader에서 매우 간단한 수식을 통해 선들을 그릴 수 있었다.

다음의 단순한 코드는 입력된 점들에 대해 매우 빠르게 각 삼각형 단위로 등시선들을 그려준다. 

 
 
        float tc = timeCriteria*i;
 
        float v0t = vertex[0].pos.z - tc;
        float v1t = vertex[1].pos.z - tc;
        float v2t = vertex[2].pos.z - tc;
 
        gs.color = vec4(color1,1.0);
 
        //모두 제한선 위거나 모두 아래면 다음으로 진행    
 
        if (v0t>0 ^^ v1t>0) {//사이에 끼어있으면,
            hasContour = true;                
            float v10 = vertex[1].pos.z - vertex[0].pos.z;
            float x = (vertex[0].pos.x*v1t - vertex[1].pos.x * v0t) / v10;
            float y = (vertex[0].pos.y*v1t - vertex[1].pos.y * v0t) / v10;
            gl_Position = Projection*View* vec4(x,y,tc*zscale*0, 1.0);        
            EmitVertex();
        }
 
        if (v1t>0 ^^ v2t>0) {//사이에 끼어있으면,
            hasContour = true;
            float v21 = vertex[2].pos.z - vertex[1].pos.z;
            float x = (vertex[1].pos.x*v2t - vertex[2].pos.x * v1t) / v21;
            float y = (vertex[1].pos.y*v2t - vertex[2].pos.y * v1t) / v21;
            gl_Position = Projection*View* vec4(x,y,tc*zscale*0, 1.0);        
            EmitVertex();
        }
 
        if (v2t>0 ^^ v0t>0) {//사이에 끼어있으면,
            hasContour = true;
            float v02 = vertex[0].pos.z - vertex[2].pos.z;
            float x = (vertex[2].pos.x*v0t - vertex[0].pos.x * v2t) / v02;
            float y = (vertex[2].pos.y*v0t - vertex[0].pos.y * v2t) / v02;
            gl_Position = Projection*View* vec4(x,y,tc*zscale*0, 1.0);        
            EmitVertex();
        }
        if (hasContour) EndPrimitive();
 
 
 

[geometry shader의 일부]

선이 아니라 색으로 칠하는 방법은 더 간단하다. OpenGL로 그릴 때는 모든 점들을 순차적으로 쉐이더라 불리는 코드에 통과 시키면서 화면 안의 픽셀들로 바꾸게 되는데, 마지막 단계인 Fragment Shader는 화면 픽셀 입장에서 계산된다. 버텍스 쉐이더에서 삼각형의 세 점에 다른 색상 값들을 보내면 프래그먼트 쉐이더에서는 그 내부에 해당하는 픽셀에 색을 칠하기 위해 하드웨어에 내장된 함수를 이용하여 중간 색상으로 보간해준다. '하드웨어 내장함수'라는건 매우 빨리 계산된다는 말이다. 

색상이 아니라 다른 수치의 경우도 마찬가지인데, 이 경우에는 그냥 삼각형 세 점의 값을 프래그먼트 쉐이더로 보내고 다음과 같은 간단한 식을 통해서 각 정점의 색상이 결정되도록 할 수 있다.

#version 430
 
uniform float timeCriteria;
 
in Vertex
{
    float v;
} colorin;
 
layout(location = 0) out vec4 FragColor;
 
 
void main() {        
    
    float v1 = colorin.v;
 
    //지정한 시간 기준의 6배수까지 콘타를 칠하고, 나머지는 그리지 않는다.
    if (v1<timeCriteria) {
        FragColor = vec4(0/255.0, 0/255.0, 4/255.0, 1);
    } else if (v1<timeCriteria*2) {
        FragColor = vec4(50/255.0, 15/255.0, 110/255.0, 1);
    } else if (v1<timeCriteria*3) {
        FragColor = vec4(137/255.0, 40/255.0, 129/255.0, 1);
    } else if (v1<timeCriteria*4) {
        FragColor = vec4(224/255.0, 76/255.0, 103/255.0, 1);
    } else if (v1<timeCriteria*5) {
        FragColor = vec4(254/255.0, 161/255.0, 110/255.0, 1);
    } else if (v1<timeCriteria*6) {
        FragColor = vec4(252/255.0, 253/255.0, 191/255.0, 1);    
    } else {
        discard;
    }
    
}
 

[fragment shader의 일부]

결국, 

각 지점의 최단 거리 도달 시간 계산 1회(직접 작성한 코드)

들로네 삼각화 1회 계산을 했고(기존 라이브러리 이용)

그 후에는 기준 시간들을 바꿔가면서 높지 않은 사양의 컴퓨터에서도 1초에 60프레임 이상으로 등시선을 뽑아내는 작업을 할 수 있게 되었다.

목표 수정 : 실시간 반응형으로 만들어보자

사실, 이때만 해도 계산 기준점을 옮겼을 때 최단거리를 다시 계산하려면 최소한 2초가 걸렸다. 1초에 2프레임도 아닌 2초에 1프레임이다. 실시간 인터랙티브는 생각조차 못했다. 그리고 딱히 해야 할 필요는 없었기 때문에 한참 동안 뒤로 밀려서 손을 놓고 있었다.

그러다가 어느 날 우연히 보게 된 페이퍼의 한 그래프에서 그게 가능할 수도 있겠다는 생각을 하게 되었다.

[두번째 행 SSSP 에서 RoadUSA를 Gunrock이 0.401초만에 계산을 한다고 기록되어 있다]

[출처 : http://www.ece.ubc.ca/~matei/papers/hpbd18.pdf  에서 TABLE IV]

이 페이퍼에서는 여러가지 SSSP 알고리즘을 비교해 놓았는데, gunrock이라는 gpu 병렬처리 알고리즘을 사용한 오픈소스 라이브러리를 사용하면 2백만개의 점과 5백만개의 선으로 이루어진 USA road 네트워크를 401ms초만에 계산한다는거다. 내가 작업했던 우리나라 전국의 네트워크는 그보다 1/5 수준이었으므로 처리 시간이 더 짧을 것이므로 그럭저럭 실시간 지도를 만들 수 있을 것 같다는 생각을 했다.

결론부터 말하자면 이 수치는 잘못된 것 같다. Gunrock 제작자들이 작성한 페이퍼에서 10초 정도 걸리는 실험 결과를 보여주기 때문이다. 

(그리고 테스트 환경이 똑같지 않다는것을 감안하더라도 두 페이퍼의 Gunrock vs NVGraph 가 서로 상반되어 약간 의아하다. 아래 페이퍼에서 NVGraph가 기록된 수치의 10배(30초)라면 이해가 된다)

[Gunrock는 10초를 약간 웃돌고, NVGraph는 3초 정도라고 기록되어 있다]

[출처 : https://arxiv.org/pdf/1701.01170.pdf Fig17에서 부분 발췌]

어찌되었든, 저 위의 페이퍼때문에 실시간 반응지도가 가능하다고 생각하게 되었고, 결국은 테스트해본 라이브러리를 모두 쓰지 않고 다익스트라 알고리즘으로 되돌아와서 목표에 닿게 되었지만 진행했던 작업을 간결하게나마 기록해보겠다.

기본 데이터 : CSR

테스트한 라이브러리는 세가지다. 

첫번째는 GPU 병렬처리 기반의 Gunrock

두번째는 GPU 병렬처리 기반의 NVgraph

세번째는 CPU 한 개의 코어에서 계산하는 방식인 Boost Library의 다익스트라 알고리즘 코드

세가지 라이브러리 모두 CSR 혹은 CSC라는 데이터 형식을 필요로 했다.

그래프(네트워크 형식의 데이터)들은 행렬로 표현할 수 있는데, 그래프를 옮긴 행렬은 빈 값이 꽤 많은 비중을 차지하고, 특히 트위터 같은 다중 연결이 아닌 도로 네트웍은 쓰여진 값이 거의 없다. 이런 행렬을 희소행렬(sparse matrix)이라고 부른다. 희소행렬은 저장공간의 최적화를 위해 몇 가지 방식으로 저장하는데, 그 중 CSR이라는 방식이 있다.

복잡한 것 같지만 아래 그림이 잘 설명해준다. 

5개의 노드와 14개의 링크가 있는 네트워크는 아래 그림의 왼쪽 행렬로 표현할 수 있다. 

그래프가 방향성이 있다고 할 때, 행이 출발 노드, 열이 도착노드다. 다섯개의 노드를 1,2,3,4,5 번 노드라고 할 때, 2번 노드에서 1번 노드로 갈 때의 저항값은 3이다. 4번 노드에서 5번 노드로 갈때의 저항값은 5다. 5번 노드에서 2번 노드로 갈 때의 저항값은 8이다.

CSR방식은 이 데이터들을 출발점 노드 순서로 정렬하여 저장했다고 생각하면 이해하기 쉽다. 그림의 오른쪽 부분이다.

반대로 CSC 방식은 도착점을 기준으로 정렬했다고 보면 된다.

그렇게 때문에 특정 노드에서 연결된 노드들을 배열상에서 순차적으로 빠르게 읽을 수 있다.

[CSR 방식 설명. 출처 : https://op2.github.io/PyOP2/linear_algebra.html]

Gunrock & Boost Dijkstra Library

Gunrock은 UC Davis 연구진들이 만들어서 공개한 오픈소스 라이브러리다. GPU 병렬 처리 방식이기 때문에 노드의 분기 수가 많을 때 최상의 성능을 발휘하는 것 같다. 제작자들도 다수의 페이퍼에서 도로망의 경우 노드의 분기 수가 적기 때문에 다익스트라 알고리즘처럼 순차처리 방식이 유리할 수도 있다고 설명하고 있다.

공개된 테스트 코드에서 Boost Library의 다익스트라 알고리즘과 결과를 비교하여 제공하는데, 내 컴퓨터에서 USA-roadnet의 경우 Gunrock 5.3초, 부스트 다익스트라 10초 정도가 나왔다. usa-roadnet은 정점 2천3백만개, 링크 5천 7백만개다. 

그렇지만 내가 구성한 국내 도로철도망 네트워크는 정점 46만개, 링크 100만개 정도였기 때문에 오히려 CPU 순차처리 방식(다익스트라)가 빨랐다. Gunrock 230ms, 부스트 다익스트라 110ms 정도

Nvgraph

NVgraph 는 엔비디아에서 API만 공개한 쿠다 기본 라이브러리다. 역시 GPU 병렬 처리 방식이다. Gunrock 페이퍼의 소개로 테스트해보게 되었는데, 아무리해도 30% 정도라는 결과가 나오지 않는다. Gunrock 제작자들의 입장에서 최대한 자신들의 코드가 빠르게 보이려는 동기가 있었을 것이므로 NVgraph를 과장하여 유리한 결과를 서술하지는 않았을 것 같다. 그렇지만 다른 사람들이 쓴 페이퍼들을 참고해보면 Gunrock 제작자들의 벤치마크가 잘못되었을 가능성이 있다.

내가 구성한 국내도로철도망은 240ms정도로 Gunrock과 비슷하게 나왔다. 그렇지만 USA roadnet을 돌려본 결과 20여초라는 무지막지한 결과가 나왔다.

우선 결론 : Boost Dijkstra Library

결국 노드 40만개 정도 크기의 국내 도로철도망에서는 GPU보다 CPU 다익스트라가 빨랐으므로, 부스트 라이브러리를 사용하기로 했다. 마우스를 움직이니 그럭저럭 볼만했다.

다시 시도 : 다익스트라 코드 직접 작성

여기서 한 가지 욕심이 생겼다. 어떤 지점을 중심으로 전국의 모든 곳들을 계산하면 110ms가 걸리지만 300분 정도까지 걸리는 전국을 모두 계산하지 않고 예를 들어 2시간 거리까지만 시각화 할 경우에는 훨씬 단축된 시간에 계산하여 시각화를 할 수 있을 것이라 생각했다.

그건 다익스트라 알고리즘에서 노드들을 훑어나가는 루프 안에서 한계 지점을 설정하는 코드 한줄을 추가하면 가능한 일이이었기 때문에, 부스트 라이브러리의 코드를 슬쩍 바꿔보려고 했다. 그렇지만 꽤 많은 라이브러리들이 그렇듯이 상당히 복잡해보이는 함수들이 서로 호출하면서 정신없이 진행되는 것처럼 보였다. 사실, 다익스트라는 몇 줄 안되는 매우 간결한 알고리즘이다. 그래서 부스트 라이브러리를 이해하고 바꿀 시간에, 일단 밑지는 셈치고 한번 기본 코드로 작성해보기로 했다.

struct NodeQ {
    int id;
    float time;
};
 
struct cmp {
    bool operator()(NodeQ& a, NodeQ& b) {
        return a.time > b.time;
    }
};
 
 
 
void solveSSSPFromNode(unsigned int startNode, float timeDistance, GraphCSR& graph, float* solution, int* predecessor)
{
 
    int i;
    float startTime,endTime;    
    int currentNode, nextNodeId;
    int scanBegin, scanEnd;
    using std::priority_queue;
 
    priority_queue<NodeQ, vector<NodeQ>, cmp> currentQueue;
    
 
    //시작점의 정보를 입력    
    solution[startNode] = 0;
    predecessor[startNode] = -1;
    NodeQ ndq = { startNode, 0 };
    currentQueue.push(ndq);
 
    while (currentQueue.size() > 0) {
 
        const NodeQ& currentNodeQ = currentQueue.top();
        currentNode = currentNodeQ.id;
        startTime = currentNodeQ.time;
 
        scanBegin = graph.rowOffset[currentNode];
        scanEnd = graph.rowOffset[currentNode + 1];
 
        for (i = scanBegin; i < scanEnd; i++) {
 
            endTime = startTime + graph.value[i];
            nextNodeId = graph.colIndex[i];
 
            if (endTime < timeDistance) { //여기에서 시간한계선을 벗어나면 건너뜀
 
                if (solution[nextNodeId] > endTime) {                    
                    solution[nextNodeId] = endTime;
                    predecessor[nextNodeId] = currentNode;                    
                    ndq = { nextNodeId, endTime };
                    currentQueue.push(ndq);
                }
            }
        }
        currentQueue.pop();         
    } /
     
}

결과는 놀랍게도 53ms. 

더도말고 덜도 말고 인터넷상에 떠도는 기본 코드들을 살짝 정리해서 거의 그대로 옮겨놓았는데 말이다.

무언가 부가적인 기능들을 추가하면서 부스트 라이브러리는 무거워 진 것 같다. 아니면 40억이 넘는 노드들을 처리하기 위해 64비트 크기의 변수들로 구현했을 수도 있다. 어찌되었거나 더 이상 부스트 라이브러리를 뜯어볼 필요도 없게 되었다. 

병렬 알고리즘 두 개를 검토한 후 돌아돌아 내가 짰던 최초 구현 코드에서 쓸데 없는 무거운 부분을 벗겨내는 것으로 마무리된 셈이다.

좀 많이 헤매긴 했지만, 정리해보니 OpenGL 문법을 알고 있다는 가정하에 그렇게 어려운 난이도의 작업은 아니다.

간단한 다익스트라 알고리즘을 사용했고, 

이미 작성되어 있는 Delauney Triangulation 라이브러리를 사용했으며, 

나머지는 더하고 빼는 자잘한 처리 작업들이다.

어떤 과정을 거쳐야 해야 등시선(등고선,등치선)을 그릴 수 있는지 알지 못하기 때문에 어렵다고 느끼지만, 막상 방법을 알고 나면 그렇게 어려운 일은 아니다.

혹시라도 등시선도나 등고선을 직접 그려보려는 사람이 있다면 이 글이 도움이 될 수 있을 것이라 생각한다. '등고선을 그리려면' 정도의 검색어로는 원하는 결과를 찾기 어렵기 때문이다.

더 해 볼 수 있다면

그림으로만 보는 것이 아쉽다면 각 권역들의 면적이 어느 정도인지 숫자로 계산하는 것도 가능하다. 화면상에 보이는 디테일만큼에서 근사치를 계산한다면 실시간으로 가능할 것 같다.

WebGL을 이용하여 웹상에서 구현하는 것도 가능할 것 같다. WebGL이 OpenGL 코드와 거의 유사하고, OpenGL보다 낮은 버젼들의 기능들만 구현되었지만, 위에서 작업한 방식을 생각해보면 충분할 것 같다.  단, WebGL 문법을 내가 알지 못하고 자바스크립트 안 한지 1년이 넘었다. 도로철도망 네트워크가 22MB정도라 웹 전송이 약간 부담스럽긴 하겠지만. 

어찌되었거나 웹에서 작동한다는건 훨씬 많은 사람들이 경험할 수 있다는걸 의미하기 때문에 충분히 가치있는 일이라 생각된다.

그렇지만 흔히 'personal project', 혹은 'non-profit project'라고 부르는 작업들은 적절한 선에서 끊을 수 있어야 한다. 그래야 건강하게 오래오래 산다.

아래는 실시간 구현 영상.

근간이 되는 네트워크는 도로철도망인데, 기차와 승용차(혹은 택시)의 조합이라고 생각하면 된다. 보행은 넣지 않았다.

국가교통 DB에서 도로망과 철도망을 받았고, 도로망의 경우는 구간별 소요시간을 전체적으로 조정하여 넣었다. 강릉 가는 고속도로가 없었지만 도로망을 그리는 일은 철도에 비해 매우 까다로왔기 때문에 추가하지 못했다.

철도망의 경우는 KTX 노선이 전체 소요시간 계산에 매우 중요한 비중을 차지했기 때문에 구간별로 다시 끊어 그린 후  소요시간을 정확히 입력해주었다. KTX경강선을 추가했다. 

다른 철도나 대도시의 지하철은 몇 개 역 사이를 샘플링하여 일괄적으로 넣었다.

마지막으로, 철도의 각 역들에서 가장 가까운 도로망에 선을 덧붙여서 네트웍을 통합시켰다.

아래처럼 여러 지점의 등시선도를 비교해 볼 수도 있다.

끝.