Leaflet에서 D3를 이용한 TSP(Traveling Salesman Problem) 활용

서비스바로가기

 

Leaflet에서 D3 라이브러리를 이용하여 TSP를 구현 후, 지도상에 사용자가 지정한 위치를 단 한번만 방문하고 시작점으로 돌아오는 TSP를 구현하였다. 

1.TSP(traveling salesman problem)란?

 

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을때, 모든 도시들을 단 한번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 이는 조합 최적화 문제의 일종으로 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

참조한 소스가 성능적으로 우수하지는 않습니다. 지도 조회 도구(Leaflet)과 시각화 라이브러리(D3)를 함께 사용하는 예시로 참조하십시오. 인터넷에는 TSP를 해결하는 다양한 응용 사례가 존재합니다.

(참조 : 위키백과 https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C)

 

2. 구현

2.1 leaflet

leaflet을 이용한 웹페이지 지도 발행은 [꿀팁-OpenLayers, Leaflet] > [OpenLayers와 Leaflet에서 Vworld 배경지도 이용하기]을 참고하세요.

D3 라이브러리를 이용하기 위해 leaflet의 지도에 svg 추가가 필요합니다. 프로그웍스 Openlayers 및 Leaflet에서 제공하는 데이터 및 배경지도는  국가공간정보포털 오픈마켓 데이터 및 VWorld를 이용하고 있습니다. <script></script>부분은 아래와 같습니다.

    • 3행 : leaflet 지도 불러오기
    • 4행 : 배경지도 Vworld 활용
    • 12행 : leaflet Map에 svg 추가(D3.js 라이브러리를 사용하기 위해 반드시 추가 필요)
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<script type="text/javascript">
$(document).ready(function(){
    var    letMap = L.map('letMap').setView([37.52470308242787126.9234],12);
        L.tileLayer('http://xdworld.vworld.kr:8080/2d/Base/201802/{z}/{x}/{y}.png').addTo(letMap);
        letMap.options.minZoom = 12;
        letMap.options.maxZoom = 12;
        letMap.dragging.disable();
        letMap.touchZoom.disable();
        letMap.doubleClickZoom.disable();
        letMap.scrollWheelZoom.disable();
        
        L.svg().addTo(letMap);
            
});
</script>
cs

 

2.2 D3(Data Drivened Document).js + TSP

D3(Data Drivened Document’).js는 웹에서 데이터를 표현하기에 적합한 도구로 특히, 인터랙티브 데이터 시각화에 많이 사용되고 있는 자바스크립트 기반 라이브러리입니다. D3.js는 HTML, SVG(Scalable Vector Graphics), CSS를 사용해 데이터를 시각적 결과물로 나타낸다. 위 leaflet <script></script> 12행에 leaflet Map에 svg를 추가한 이유가 D3.js 라이브러리를 이용하기 위함이었습니다.

다른방법을 알고 계신다면 알고계신 방법을 사용하셔도 무방하지만 저는 svg를 사용하겠습니다. 아래 <script></script>부분은 d3.js를 이용하여 TSP를 구현한 부분입니다. 소스가 상당히 길지만 정리된 내용을 보시면 금방 이해를 하실 수 있으실 겁니다.

D3.js 및 TSP분석을 위해 underscore.min.js 및 d3.v3.min.js파일을 추가합니다. leaflet map을 이용하기 위해서는 leaflet.js 및 .css파일로 추가하셔야합니다. (참고하기 : 

[꿀팁-OpenLayers, Leaflet] > [OpenLayers와 Leaflet에서 Vworld 배경지도 이용하기])

1
2
3
4
5
<link type="text/css" rel="stylesheet" href="<c:url value='/css/leaflet/leaflet.css'/>" />
 
<script src="<c:url value='/js/D3/d3.v3.min.js'/>"></script>
<script src="<c:url value='/js/leaflet/leaflet.js'/>"></script>
<script src="<c:url value='/js/TSP/underscore.min.js'/>"></script>
cs

D3.js 및 TSP 구현부분을 확인하기 전 알아야 할 부분이 있다.

TSP는 NP-hard 문제에 속하는 것으로 완전 탐색 연결을 위해서는 0(N!)이라는 시간 복잡도가 나온다(Factorial). 이는 10개만 탐색해도 3,628,800개 라는 값이 나오며, 웹페이지에서 구현 시, 페이지가 멈추는 현상이 생긴다.... 그렇기 때문에 포인트 개수에 제한을 두고 개발하였다.(최대 9개 지점 선택 가능)

- 참조 : Factorial( https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9 )

- NP-Hard란?

비 결정론적 튜링머신으로 다항시간 내에 풀 수 있는 문제로 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다.

지금부터 <script></script>부분을 살펴보겠습니다.

    • 2행~12행 : d3.js에서 tsp를 구현하기 위해 사용한 변수 선언
    • 14행 : d3.js를 이용한 TSP 구현 부분
    • 23행 : leaflet map하위의 svg부분을 변수 svg에 선언
    • 23행~42행 : marker와 path 부분 선언
    • 44행 : d3 click 이벤트 선언
    • 60행 : 지도 클릭에 따른 위치정보 추출 및 지도 위 포인트 표시 function 실행
    • 65행 : TSP 실행(RUN)
    • 81행 : TSP 초기화(RESET)
    • 90행 : 지도 클릭에 따른 포인트 표시(시작점은 빨강/그외 지점은 검은색)
    • 119행 : TSP 분석을 통한 path 그리기
    • 137행~151행 : 선택된 위치를 이용한 TSP 비용 계산(Cost)
    • 151행 : 배열에 담은 선택한 포인트를 랜덤으로 순서 생성 및 Cost 계산 function 실행
    • 163행 : TSP 분석에 필요한 최소 비용 및 경로 추출 반복 횟수 만큼(팩토리얼:factorial) 새로운 방문 순서 및 비용 계산(RandomPath 및 Cost부분 function 실행)
    • 176행 : TSP 옵션 정보를 이용한 path, cost 값 정의 및 TSP 완전 탐색이 진행되는 부분
    • 214행~230행 : TSP 반복 횟수 지정 부분(완전탐색 횟수 지정 부분)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
<script type="text/javascript">
    var tspCount,
        infoText,
        echoText,
        clickCoords,
        featureElement;
    var resultCost = [];    
    var checkRun = false;
    
    var dotscale = 12,
        nodes = []
        cities = [];
        
    (function (d3, _) {
        "use strict"
        
        drawFeatures();  
        
        function drawFeatures() {
            
            var path = d3.geo.path();
            var svg = d3.select("#letMap").select("svg");
            svg.append("svg:defs")
                .append("svg:marker")
                  .attr("id""arrow")
                  .attr("viewBox""0 0 10 10")
                  .attr("refX"15)
                  .attr("refY"5)
                  .attr("markerWidth"6)
                  .attr("markerHeight"6)
                  .attr("orient""auto")
                .append("svg:path")
                  .attr("d""M0,0L10,5L0,10");
    
              svg.append("rect")
                  .attr("class""background")
                .attr("height","686")
                .attr("width","100%")
                  .on('click', clickMap);
              
              var g = svg.append("g")
                .attr("id""baseSVG");
              
              function clickMap () {
                  if(checkRun == true){
                      cities = [];
                    tspCount = null;
                    $('#countInfo').html('0');
                    svg.selectAll('circle').remove();
                    svg.selectAll('path.connection').remove();
                    document.getElementById("echoText").value = "";
                    checkRun = false;
                  }
                  
                  if(cities.length >= 9){
                      alert("위치선택은 9개까지 가능합니다.");
                      return;
                  }
                  
                  cities.push(d3.mouse(this));
                clickCoords = d3.mouse(this);
                drawCities();
            }
              
              function run() {
                if(cities.length<2){
                    alert("2점 이상의 위치를 지도에 표시하세요.");
                    return;
                }
                
                  tspCount = null;
                $('#countInfo').html("TSP 0 번 분석");
                optsNum();
                svg.selectAll('path.connection').remove();
                var answer = sanTsp(cities, {});
                drawPaths(answer.initial.path);
                setTimeout(function () { drawPaths(answer.final.path); }, 1000);
                checkRun = true;
            }
              
            function reset () {
                cities = [];
                tspCount = null;
                $('#countInfo').html('0');
                svg.selectAll('circle').remove();
                svg.selectAll('path.connection').remove();
                document.getElementById("echoText").value = "";
            }
            
            function drawCities() {
                if($(".city").attr("cx"== null && $(".city").attr("cx"== null){
                    svg.selectAll('circle').data(cities).enter()
                    .append('circle')
                        .attr('cx'function (d) { return d[0]; })
                        .attr('cy'function (d) { return d[1]; })
                        .attr('r', dotscale)
                        .attr('fill','red')
                        .attr('stroke','black')
                        .attr('opacity','0.7')                        
                        .attr('class''city');
                }else{
                    
                    svg.selectAll('circle').data(cities).enter()
                        .append('circle')
                            .attr('cx'function (d) { return d[0]; })
                            .attr('cy'function (d) { return d[1]; })
                            .attr('r', dotscale)
                            .attr('fill','black')
                            .attr('stroke','black')
                            .attr('opacity','0.7')
                            .attr('class''city');
                }
                
                echoText = document.getElementById("echoText");
                
                echoText.value += cities.length+"번째 위치를 선택하였습니다. (위치정보"+clickCoords+") \n";
            }
            
            function drawPaths(ipath) {
                var paths = _.map(_.zip(ipath.slice(0,ipath.length-1), ipath.slice(1)), function (pair) {
                    return [cities[pair[0]], cities[pair[1]]]
                }).slice();
    
                svg.selectAll('path.connection').remove();
                svg.selectAll('path.connection').data(paths).enter()
                    .append('path')
                        .attr('d'function(d) {
                        var dx = d[1][0- d[0][0],
                            dy = d[1][1- d[0][1],
                            dr = Math.sqrt(dx * dx + dy * dy);
                        return "M" + d[0][0+ "," + d[0][1+ "A" + dr + "," + dr + " 0 0,1 " + d[1][0+ "," + d[1][1];
                      })
                        .attr('class''connection')
                        .attr("marker-end""url(#arrow)");
            }
 
            function ccCost(c1, c2) {
                return Math.sqrt(Math.pow(c1[0- c2[0], 2+ Math.pow(c1[1- c2[1], 2));
            }
            function sum(arr) {
                return _.reduce(arr, function (x,y){ return x+y; }, 0);
            }
            function pathCost(path) {
                var zipped = _.zip(path.slice(0,path.length-1), path.slice(1));
                
                return sum(_.map(zipped, function (pair) {
                    return ccCost(cities[pair[0]], cities[pair[1]]);
                }));
            }
            
            function randomPath() {
                var n = cities.length
                    ,    path = [0// wlog, begin with 0
                    , rest = _.range(1, n);
 
                while (rest.length > 0) {
                    var i = Math.floor(Math.random() * rest.length);
                    path.push(rest[i]);
                    rest.splice(i, 1);
                }
                return path.concat([0]);
            }
            function doRound(cur) {
                var newpath = randomPath(),
                    newcost = pathCost(newpath);
                if ((newcost < cur.cost)) {
                    return {
                        path: newpath,
                        cost: newcost
                    };
                } else {
                    return cur;
                }
            }
            
            function san(opts) {
                var path = randomPath(),
                    cost = pathCost(path),
                    cur = {
                        path: path,
                        cost: pathCost(path)
                    },
                    answer = {
                        initial: cur
                    },
                    i;
                
                console.log('Starting SAN-TPS', cur);
                var firstCur = cur
                
                if(cities.length == 9){
                    opts.N = opts.N*0.75;
                }
                for (i = 1; i <= opts.N; i++) {
                    
                    cur = doRound(cur);
                    if(cur.cost < firstCur.cost){
                        cur = cur;
                    }else{
                        cur = firstCur;
                    }
                    if(opts.N >= 40320){
                        opts.N = opts.N-100;
                    }
                    
                    document.getElementById("countInfo").innerHTML = "TSP " + i + "번 분석 ";
                }
                
                console.log('Finished SAN-TPS', cur);
                answer.final = cur;
                return answer;
            }
            
            function optsNum(){
                for (var i = cities.length; i >= 1; i--) {
                    if(tspCount == null){
                        tspCount = i;
                    }else{
                        tspCount = tspCount * i;
                    }
                }
            }
            
            function sanTsp(cities, opts) {
                opts = opts || {};
                opts.N = tspCount;
                return san(opts);
            }
    
            d3.select('#run').on('click', run);
            d3.select('#reset').on('click', reset);
    
            console.log('Loaded!');
            
        }
        
    })(d3, _);
</script>
cs

 

2.3 Leaflet + D3(Data Drivened Document).js + TSP <Body></Body>부분

    • 2행 : L.map에서 선언한 Id와 div태그에 사용한 아이디는 동일하여야 한다.
1
2
3
4
5
6
7
8
<body>
    <div id="letMap"></div>
    <h1>Location Info</h1>
    <div id ="countInfo">TSP 0 번 분석</div>
    <textarea id="echoText" rows="10" cols="310"></textarea>
    <button id="run">Run</button>
    <button id="reset">Reset</button>            
</body>
cs

 

3. 테스트 및 결과

테스트 시나리오는 사용자가 임의의 지점은 선택하고 그에 따른 TSP 결과 도출로 진행

구현된 TSP는 별도의 가중치가 없으며, 오직 거리를 이용하여 TSP를 구현하였으며, 직선으로 거리를 표시하고 계산하였다.

3.1 테스트 

1. 임의지점 선택에 따른 위치정보 표시 및 선택 개수 제한 유무

(임의 지점 : 부천시청,.가톨릭대학교성심교정, 매봉산, 서울역, 동덕여자대학교, 한양대학교 서울캠퍼스, 대공원입구, 영등포역, 광명시청 총 9개 지점)  

2. TSP 실행 및 화면 표출

3. TSP 분석 횟수 표시

4. 초기화

 

3.2 결과화면

 

 

SVG(Scalable Vector Graphics) 정의

> 바로가기 : W3C SVG Specfication (https://www.w3.org/TR/SVG2/)
> 바로가기 : W3School SVG Tutorial (https://www.w3schools.com/graphics/svg_intro.asp)
> 바로가기 : SVG 애니메이션 레벨2 (https://svgwg.org/specs/animations/)

동적 웹페이지를 위하여 플래쉬가 널리 사용되던 적이 있습니다. 현재도 사용되긴 하지만 웹 호환성 문제가 나타나며 점진적으로 사용이 감소하고 있는 추세입니다. 플래쉬를 충분히 대체할 수 있는 웹 표준 기술이 존재하기 때문에 플래쉬는 결국 사장될 것입니다. 이를 대체하는 대표적인 표준 기술이 SVG 입니다.

SVG(Scalable Vector Graphics)는 XML 문서 형식으로 2차원 벡터 그래픽 객체를 정의하는 웹 표준으로 1999년 W3C(World Wide Web Consortium)의 주도로 개발되었습니다. 당시 인터넷 이용 환경은 차별없는 웹 구현에 제약이 있었습니다. 웹 브라우저에서 그래픽 객체를 표현하기 위해 Flash, Applet, ActiveX 등 벤더 종속적인 Binary Plug-in 을 사용했으나 상호운영성 및 호환성에 부족한 부분이 있었습니다.

현재 신규 제작되는 웹사이트의 경우 대부분 HTML5 사양이 적용되고 있습니다. HTML5가 이전 HTML 사양과 구별되는 기술직인 특징은 멀티미디어(video, audio) 사용성 강화, 그래픽 표현 강화(svg, canvas), Socket 적용 등을 들 수 있습니다. HTML5가 정의하는 2차원 벡터 그래픽 표현 방법은 SVG를 사용합니다. 이를 통해 HTML5는 SVG가 가지는 장점을 수용합니다. SVG가 가지는 장점은 여러가지가 있지만 대표적으로 다음과 같습니다.

  • 문서로 작성되는 그래픽이기 때문에 텍스트 편집기를 통해 제작될 수 있다. 기계판독(Machine-Readable)이 되는 형식이다
    (플래쉬는 이진 바이너리 코드의 실행으로 기계판독이 되지 않는 데이터 입니다)
  • 벡터 그래픽이기 때문에 표현되는 장비 해상도에 영향을 받지 않는다
    (확대, 축소하더라도 원본의 품질을 유지한다)
  • DOM (Document Object Model)을 가지기 때문에 그래픽 요소에 대한 검색, 색인이 가능하다
  • Video, Audio, Raster Image 등 멀티미디어 요소와 통합이 쉽다
  • Animation 지원으로 동적인 그래픽 표현이 가능하다
    (SVG 애니메이션은 SMIL(Synchronized Multimedia Intergration Language)을 정의하는 W3C Synchronized Multimedia(SYMM) 워킹그룹과 협력하여 개발되었습니다.)
  • 웹 표준 기술이기 때문에 별도의 이진 플러그인 없이 웹브라우저에서 바로 동작한다.

[출처] http://svgtutorial.com/svg-browser-support/   

SVG 적용 사례

> 바로가기 : Pinterest (https://www.pinterest.co.kr/)
> 바로가기 : ArcGIS (https://developers.arcgis.com/javascript/3/jssamples/graphics_svg_path.html)
> 바로가기 : Earth NullSchool (https://earth.nullschool.net/)
> 바로가기 : D3-Data Driven Documents (https://d3js.org/)

 

SVG를 이용한 공간정보 시각화

공간정보 분야에서 SVG 적용으로 얻을 수 있는 가장 큰 이점은 SVG Animation 요소 적용으로 실시간으로 변하는 상황의 표현이 쉽다는 것입니다. 아래의 예시는 간단한 SVG 애니메이션 소스 입니다. 

첫번째는 그래픽요소가 가지는 속성을 변경하는 것으로, 실제 공간정보분야에 적용된다면 비즈니스 레이어에 존재하는 객체가 가지는 Business Value에 연동하여 그래픽 표현을 적용하는데 적용될 수 있습니다.
두번째는 객체의 위치를 변경하는 것으로써 이동체(Moving Object)의 실시간 위치를 관제하는 경우 적용될 수 있습니다.
세번째는 지정된 길을 따라가는 예시로 항공기의 궤적, 물류 분야 관제 등 경로 표현에 적용될 수 있습니다.
SVG에서 객체의 형상(Rectagle, Circle, General Path, Group,..)을 정의하는 모든 요소는 애니메이션의 대상이 됨으로 동적인 표현이 가능합니다.

지리좌표계의 적용을 위해 SVG 의 Root Element(<svg>)에 'viewBox' 속성을 지정합니다. 이를 통해 실세계 좌표계(World Coordintate Reference System)를 사용할 수 있습니다. 일반적으로 경위도로 표현되는 좌표를 그대로 이용하기 때문에 GIS App 개발을 위한 별도의 변환 작업이 요구되지 않습니다.

> 다운로드 : svg_gis.html ( 

svg_gis.zip
다운로드

가장 일반적인 방법으로써 공간정보의 시각화를 위하여 Openlayers, leaflet등의 공개 SW가 널리 사용됩니다. 이 들 라이브러리는 D3와 함께 사용되면 동적인 정보 표현을 가능하게 합니다. D3는 HTML, SVG, CSS를 쉽게 사용하도록 도와주는 Wrapper 또는 Helper 라이브러리 입니다. 사용자는 SVG가 정의하는 그래픽 요소에 대한 지식이 없더라도 D3를 통해 쉽게 SVG를 이용할 수 있습니다.

기회가 된다면 본 블로그를 통해 다양한 GIS Data Viewer(OpenLayers, Leaflet, CesiumJS)에서 SVG를 활용하는 사례를 직접 제작하여 게시하겠습니다. 

> 바로가기 : SVG 애니메이션 사례 - 영국 바람 차트 (

https://charts.animateddata.co.uk/ukwind/)

> 바로가기 : leatlet + SVG - TOURISVIS.COM 스키장 안내 지도 (

https://winter.intermaps.com/oetztal?lang=en)

 

 

+ Recent posts