[OpenLayers3] 가장 가까운 포인트 추적

현재 지도 상에 표시된 원 모양의 포인트 피쳐에 대해 마우스 커서 위치에서 가장 가까운 원을 추적해 효과적으로 시각화 해주는 예제를 만들어 보겠습니다. 실행 결과는 아래와 같으니 한번 마우스를 올려 놓고 요래~요래~ 움직여 보세요~

위와 같은 예제를 만들어 보겠습니다. 먼저 필요한 외부 CSS와 JavaScript 라이브러리를 아래처럼 추가합니다.




UI를 만들어 것인데요. 보면 지도 하나 딸랑~ 있습니다. 이 지도는 div 요소에 표시되므로 아래와 같습니다. 이 div의 id를 map으로 지정해 이름을 붙여 추후 참조할 수 있도록 하였습니다.


    

자, 이제 코드를 작성해 이 UI에 영혼을 불어 넣어 보겠습니다. 수리수리마수리..

jQuery의 기능 중 페이지의 구성 요소가 모두 준비되었을때 호출되는 이벤트를 아래처럼 등록합니다.

<script>
    $(function () {
        ....
    });

앞으로 우리가 작성할 모든 코드는 위에서 …. 부분에 추가되는데요. 먼저 지도 화면에 표시할 원에 대한 피쳐(Feature)를 4000개 생성합니다. 이 피쳐의 지오메트리 타입은 포인트이므로 무작위 위치를 가지도록 ol.geom.Point로 지정하고 i와 size라는 속성값을 지정해 둡니다. size에는 i값에 따라 10 또는 20의 값이 지정되도록 하였습니다.

var count = 4000;
var features = new Array(count);
var e = 18000000;

for (var i = 0; i < count; ++i) {
    features[i] = new ol.Feature({
        'geometry': new ol.geom.Point([2 * e * Math.random() - e, 2 * e * Math.random() - e]),
        'i': i,
        'size': i % 2 ? 10 : 20
    });
}

그리고 이 4000개의 포인트에 대해 어떤 스타일로 표시할지를 지정해야 하는데요. 이때 사용하는 styles 객체를 생성해 둡니다.

var styles = {
    '10': new ol.style.Style({
        image: new ol.style.Circle({
            radius: 5,
            fill: new ol.style.Fill({ color: '#666666' }),
            stroke: new ol.style.Stroke({ color: '#bada55', width: 1 })
        })
    }),
    '20': new ol.style.Style({
        image: new ol.style.Circle({
            radius: 10,
            fill: new ol.style.Fill({ color: '#666666' }),
            stroke: new ol.style.Stroke({ color: '#bada55', width: 1 })
        })
    })
};

위의 코드를 보면 10과 20에 대한 원형 스타일 2개를 준비하고 있습니다. 이는 이후의 코드에서 살펴보겠지만, 피쳐의 size 속성에 따라 스타일을 결정하게 됩니다.

ol3에서는 지도 상에 표시되는 것은 레이어(layer)라는 개념이 필요합니다. 이 예제의 경우, 좀더 정확하게는 ol.layer.Vector 레이어 타입인데요. Vector는 도형에 대한 형상을 표현하기 위한 레이어입니다. 레이어는 자신이 표현해야할 데이터를 제공해 주는 데이터소스가 필요합니다. 이 데이터 소스에 대한 객체를 아래처럼 추가합니다.

var vectorSource = new ol.source.Vector({
    features: features,
    wrapX: false
});

위의 코드를 보면 4000개의 포인트 피쳐를 담고 있는 features를 통해 ol.source.Vector 타입의 데이터소스 객체를 생성하고 있습니다. 이제 ol.layer.Vector 레이어를 위한 모든 것이 준비되었으니 레이어를 생성합니다.

var vector = new ol.layer.Vector({
    source: vectorSource,
    style: function (feature) {
        return styles[feature.get('size')];
    }
});

앞서 만들어 두었던 데이터소스를 지정하고 있구요. style 속성에 함수를 지정해 표시해야할 피쳐에 대한 size 속성값에 따라 스타일을 결정하도록 하였습니다.

이제 이렇게 생성된 레이어를 지도 객체에 지정합니다.

var map = new ol.Map({
    layers: [
        new ol.layer.Tile({ source: new ol.source.OSM() }),
        vector
    ],
    target: document.getElementById('map'),
    view: new ol.View({
        center: [0, 0],
        zoom: 6
    })
});

위의 코드 중 2번 줄에 Open Street Map와 앞서 생성한 벡터 레이어를 구성 레이어들로 지정하고 있습니다. 6번은 지도를 표현할 div 요소를 지정하는 것이고, 7번은 지도의 초기 중심 좌표와 줌 레벨을 지정하고 있습니다.

지금까지의 지도 객체에 벡터 레이어를 지정하기 위해 생성한 객체들의 관계를 클래스 다이어그램으로 표현하면 아래와 같습니다.

자, 이제 마우스 커서의 위치에서 가장 가까운 원을 추적할 모든 준비가 끝났습니다. 가장 가까운 원을 추적할때 추적된 원과 커서 사이에 피드백을 시각화할 것인데요. 이를 위해 아래처럼 2개의 전역 변수와 1개의 함수가 필요합니다.

var point = null;
var line = null;

var displaySnap = function (coordinate) {
    var closestFeature = vectorSource.getClosestFeatureToCoordinate(coordinate);

    if (closestFeature === null) {
        point = null;
        line = null;
    } else {
        var geometry = closestFeature.getGeometry();
        var closestPoint = geometry.getClosestPoint(coordinate);

        if (point === null) {
            point = new ol.geom.Point(closestPoint);
        } else {
            point.setCoordinates(closestPoint);
        }

        if (line === null) {
            line = new ol.geom.LineString([coordinate, closestPoint]);
        } else {
            line.setCoordinates([coordinate, closestPoint]);
        }
    }

    map.render();
};

displaySnap이라는 함수를 설명하면, 함수의 인자로 마우스 커서 위치에 대한 지도 좌표를 받습니다. 5번 코드에서 앞서 생성해 두었던 벡터 레이어의 데이터소스의 getCloestFeatureToCoordinate라는 매우 설명에 충실한 함수를 통해서 데이터 소스의 피쳐들 중 현재 마우스 커서 위치에서 가장 가까운 피쳐를 검사해 존재한다면 반환합니다. 만약 7번의 if 문을 통해 가까운 피쳐가 존재하지 않는다면 point와 line 변수를 null로 지정하고, 가까운 피쳐가 존재한다면 point 변수는 가장 가까운 포인트 피쳐의 위치를 가지는 ol.geom.Point 객체를 생성해 지정하고 line에는 커서의 지도 좌표 및 가장 가까운 포인트 피쳐의 위치 좌표로 구성된 ol.geom.LineString 객체를 생성해 지정합니다. 이 point와 line을 지도 상에 그려주면 피드백 시각화가 완성되는 것입니다. 이러한 시각화를 위해 일단 28번 코드에서 map.render() 함수를 호출하는데요. 이 함수가 호출되면 map에서 postcompose 이벤트가 호출되므로 이 이벤트에 대한 코드를 살펴보면..

var stroke = new ol.style.Stroke({
    color: 'rgba(255,255,0,0.9)',
    width: 3
});

var style = new ol.style.Style({
    stroke: stroke,
    image: new ol.style.Circle({
        radius: 10,
        stroke: stroke
    })
});

map.on('postcompose', function (evt) {
    var vectorContext = evt.vectorContext; // ol.render.VectorContext 
    vectorContext.setStyle(style);

    if (point !== null) {
        vectorContext.drawGeometry(point);
    }

    if (line !== null) {
        vectorContext.drawGeometry(line);
    }
});

위의 코드를 살펴보면, 1번과 6번의 코드에서 앞서 point 객체와 line 객체를 그리기 위해 사용되는 스타일 객체를 생성해 둡니다. 그리고 14번에서 map에 대해 postcompose 이벤트를 등록하는데요. 보시면 앞서 생생해둔 point, line을 drawGeometry 함수를 이용해 그려주고 있습니다.

자, 이제 마지막으로 displaySnap 함수를 적정한 시점에서 호출해 주기만 하면 되는데요. 그 시점은 지도 상에 마우스 커스를 이동하거나 클릭할때 정도가 될것 같습니다. 이 마우스 이동과 클릭에 대한 이벤트 코드를 아래처럼 지정해 둡니다.

map.on('pointermove', function (evt) {
    if (evt.dragging) {
        return;
    }

    var coordinate = map.getEventCoordinate(evt.originalEvent);
    displaySnap(coordinate);
});

map.on('click', function (evt) {
    displaySnap(evt.coordinate);
});

이상으로 지금까지 작성된 코드는 아래의 링크를 통해 다운로드 받을 수 있습니다.

최단 경로 탐색 – Dijkstra 알고리즘

다익스트라 알고리즘은 시작 노드만을 지정하면, 이 시작 노드에서 다른 모든 노드에 대한 최단 경로들을 분석해 줍니다. 참고로 최단 경로 탐색 알고리즘의 다른 형태로  A*(에이스타) 알고리즘이 있는데요. A* 알고리즘은 시작 노드에서 목적지 노드를 지정해주면 이 2개의 노드 간의 최단 경로 하나만을 분석해 줍니다.

이 글은 다익스트라 알고리즘에 대한 이런 저런 장황한 설명을 배제하고 실제 예를 들어, 그 예에 대한 최단 경로 탐색을 위한 다익스트라 알고리즘에 대해 설명합니다.

먼저 다음과 같은 예를 들어 보겠습니다.

위의 그림을 간단히 설명하면, 0부터 6번까지의 노드(Node)가 존재하고 각 노드를 연결하는 선인 링크(Link)가 있습니다.  각 링크에는 숫자가 표시되어 있는데요. 이 숫자는 해당 링크를 지나갈때에 소요되는 비용(Cost, 경비)로 생각할 수 있습니다. 예를 들어, 2번 노드와 6번 노드 사이에 비용 8인 링크가 있는데요. 이는 2번 노드에서 6번 노드를 지나간다고 할때 8의 비용이 필요하다는 의미입니다. 비용이 적을 수록 상대적으로 더 좋은 경로이겠지요.

이제 위의 예, 즉 0번 노드를 시작점으로 해서 나머지  1, 2, 3, 4, 5, 6 번 노드를 목적지로 하는 최단 경로 6개를 구할 수 있는 방법이 바로 다익스트라 알고리즘입니다.

이상의 문제 해결을 위해 가장 먼저 시작되는 연산은 다음 그림과 같습니다.

위의 그림에서 S 은 이미 처리가 완결된 노드의 집합인데요. 가장 먼저 시작 노드인 0번을 집어 놓음으로써 0번 노드에 대한 처리를 시작합니다. D 저장소는 0번~6번까지의 노드에 대해, 시작노드로부터 소요되는 비용을 저장하고 있습니다. D 저장소의 상단 행은 노드의 번호이고 하단 행은 시작노드로부터 소요되는 비용입니다. 위 그림에서 D 저장소를 보면 0번 노드는 시작노드이므로 소요되는 비용이 0이고, 0번 노드와 링크로 연결된 1번과 3번 노드는 각각 5와 1의 비용이 소요되는 것으로 기록되어 있습니다. T 저장소는 해당 노드로 가는데 연결된 노드의 번호를 담고 있는데요. T 저장소이 상단 행은 노드의 번호이고 하단 노드는 연결된 노드 번호입니다. 위의 그림을 보면 1번 노드와 3번 노드는 0번 노드와 연결되어 있으므로 0으로 기록되어져 있습니다. 이게 주어진 문제에 대한 다익스트라 알고리즘의 첫번째 처리입니다.

이제 다음 처리에 대한 그림을 살펴 보겠습니다.

S집합에 3번 노드를 추가했습니다. 이유는 D 저장소에 3번 노드에 대한 비용값이 가장 최소이기 때문입니다. S집합에 3번 노드를 추가함으로써 3번 노드와 링크로 연결된 2번과 5번 노드에 대한 비용값을 계산해 D 저장소에 기록해야 하는데요. 시작 노드인 0번 노드에서 2번 노드까지 가기 위해서 소요되는 비용은 총 3입니다. 이유는 0번-3번-2번 노드로 가야하므로 비용값은 0번-3번 노드로 가는 비용 1과 3번과 2번 노드로 가는 비용 2를 합한 값입니다. 이러한 계산은 D 저장소를 활용하면 쉽게 계산할 수 있는데요. 이미 시작노드에서 각 노드로 가는 비용이 계산되어 있기 때문에 마지막 노드로 가는 비용만을 더해주면 되기 때문입니다. 5번 노드에 대한 비용은 동일한 방식으로 1+1인 2가 됩니다. 그리고 T 저장소도 각 노드에 대해 이전에 연결된 노드값을 기록해 둡니다. T 저장소의 2번과 5번 노드는 3번 노드를 통해 연결되어 있으므로 3을 기록합니다. 다음 처리에 대한 그림을 살펴봅시다.

S 집합에 5를 추가했습니다. 이는 이미 처리가 완료된 노드 이외의 노드 중 5번 노드의 비용이 2로 가장 최소이기 때문입니다.  이미 처리가 완료된 노드인지 S 집합에 존재하는지를 보면 알 수 있습니다. 5번 노드에 대해 연결된 노드는 2, 3, 6번 노드인데요. 이미 3번은 처리가 완료되었으므로 2번 노드와 3번 노드에 대해 D 저장소의 값을 갱신해야 합니다. 5번 노드를 거쳐 2번 노드를 갈 경우 소요되는 비용은 2+2로 4입니다. 이 값은 이미 전 단계에서 계산된 비용값(3)보다 크므로 무시합니다. 6번 노드에 대한 비용값은 5번 노드까지 오는데 소요된 비용값(2)와 5번에서 6번 노드로 가는데 추가적으로 필요한 비용 3을 합한 값 5이므로, 이 값을 D 저장소에 기록하고 T 저장소의 6번 노드 값에 5번 노드를 기록합니다. 다음 단계로 넘어 갑니다. 

처리가 완결되지 않은 노드 중 비용이 최소인 노드는 2번인데요. 2번 노드와 연결된 노드는 1, 3, 5, 6번 노드입니다. 처리가 완결된 노드를 저장하고 있는 S 집합을 통해 3번 노드와 5번 노드는 더 이상 고려할 필요가 없다는 것을 알 수 있으니, 1, 6번만 고려하면 됩니다. 먼저 1번의 경우 소요되는 비용은 3+1로 4인데요. 이 값은 이전 단계에서 계산된 비용값(5)보다 작으로 D 저장소의 값을 변경 합니다. D 저장소가 변경되면  T 저장소의 값도 2번 노드로 변경합니다. 중요한 부분이므로 위의 그림에서 빨간색으로 표시했습니다. 이제 남은 6번 노드에 대한 비용값을 계산해 보면 3+8로 11인데요. 이 값은 이전 단계에서 계산된 비용인 5보다 크므로 무시합니다. 다음 단계로 진행합니다.

처리가 완료된 노드가 아닌 것 중 1번 노드의 비용이 현재 가장 최소이므로 집합 S에 1번 노드를 추가하고 1번 노드와 연결된 0, 2, 4번 노드 중 완결되지 않은 4번 노드에 대한 비용값을 계산합니다. 4번 노드의 비용값은 4+3으로 7이므로 이 값을 D 저장소에 기록하고 T 저장소에 1번 노드를 기록합니다.

이미 처리가 완료된 노드가 아닌 것 중 최소인 노드는 6번 노드인데요. 이 6번 노드를 집합 S에 추가하고 6번 노드와 링크로 연결된  1, 2, 4, 5 중 처리가 완결되지 않은 노드는 4번인데요. 6번 노드를 경유해 4번 노드로 가기 위한 비용은 5 + 1인 6으로 계산되며, 이 값은 이전 단계에서 계산된 값(7)보다 작으므로 D 저장소가 변경되고, 이와 함께 T 저장소에 대해서도 4번 노드에 대해 6번 노드로 변경합니다.  다음 단계로 진행합니다.

처리되지 않은 노드 중, 이제 유일하게 4번 노드만 남았는데요. 4번 노드와 연결된 1, 6번 노드에 대해 처리를 해야 하는데 이미 1, 6번 노드는 처리가 완결되었으므로 더 이상 진행하지 않고 종료됩니다.

이상의 결과에서 T 저장소를 통해 출발 노드인 0번 노드에서 각 노드에 대한 최단 경로를 파악할 수 있습니다. 0번 노드에서 1번 노드에 대한 최단 경로는 (1번 노드)←(2번 노드)←(3번 노드)←(0번 노드)가 됩니다. 이는 T 저장소를 보면, 먼저 1번 노드에 연결되는 노드는 2번 노드라는 것을 알 수 있고, 다시 2번 노드는 3번 노드와 연결되며 3번 노드는 시작 노드인 0번 노드라고 기록되어 있기 때문입니다. 시작 노드 0번에서 각 노드에 대한 최단 경로를 정리하면 다음과 같습니다.

  • 0번 노드에서 1번 노드 : (1번 노드)←(2번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 2번 노드 : (2번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 3번 노드 : (3번 노드)←(0번 노드)
  • 0번 노드에서 4번 노드 : (4번 노드)←(6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 5번 노드 : (5번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 6번 노드 : (6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)