'Designing Interactive Distance Cartograms to Support Urban Travelers', by Ray Hong 등 6명 2017 리뷰

▶ 기본 개념

우리가 통상 보는 지도는 등거리지도(Equidistant Map, 이하 EM)이다.

EM은 지리적인 정보를 찾을 때는 유용하지만 시간이라는 factor을 고려해야 할 때 불편함을 준다.  (이전 포스트를 참고)

이전 포스트에 추가로 Ray Hong은 새로운 개념 GAP(Geo-contextual Anchoring Projection)와 SRC(Scalable Road-network Construction)을 적용하여

더 나은 Distance Cartogram(이하 DC)를 만들었다. 여기서 DC는 사용자가 지정한 위치에서 다른 지점까지의 걸리는 시간을 바탕으로 만든 지도를 뜻한다.

이 때 시간은 실제 거리(physical distance)와 비례하지 않을 수 있다. (교통사정과 도로의 접근성 등등)

▶ GAP와 SRC 이란?

1) GAP이란?

앞서 서술했듯이 DC는 다른지점까지의 걸리는 시간을 바탕으로 만든 지도이다. 따라서 교통상황 같은 도달하는 시간에 영향을 주는 요인들에 의해 지도가 계속해서 변하고 왜곡이 생긴다. 사용자가 지정한 원점(이하 O)에서 10km 떨어진 지점 A, 20km 떨어진 지점 B가 있다고하자. 하지만 A 근처에는 핫플이 많기 때문에 A 근처만 가도 극심한 교통체증이 있어서 A까지 가는데 30분이 걸리지만 B는 15분이면 갈 수 가 있다고 하면 DC에서 A는 B보다 O에서 멀리 떨어져있다. 이렇듯 DC는 현실의 물리적거리와 대치되는 상황이 발생할 수 있고 이는 사용자에게 혼란을 준다. (아래 그림 참고)

(위는 실제 DC에서의 지도 왜곡을 보여준다)

이전 포스트에서도이러한 현실 왜곡울 DC의 한계점이라고 포스팅 했었다. GAP는 이런 '왜곡'현상을 해결하기위한 수단이다.

GAP의 기본 개념은 점들의 topology를 보존하면서 각 노드를 초기 위치에서 목표 위치로 반복적으로 이동시키는 알고리즘이다. Topology가 깨지지 않고서는 노드를 움직일 수 없는 경우에는 이동을 멈추고 anchor를 추가하여 멈춘 위치와 목표 위치 사이의 차이를 시각적으로 표시한다. 

Topology라고 하면 위상기하학이라는 뜻으로서 topology가 깨진다는 말은 쉽게말하면 지도의 점,선,면들이 뒤틀려 지도가 본래의 지도와 달라짐을 뜻한다.

아래부터는 GAP의 psudo code를 서술하겠다. 관심 없는 분들은 스킵하셔도 무방하다.

----------------------------------------------------------------------------------------------------------------------------------------------------

이런  node의 움직임은 다음과 같은 pseudo code에 의해 계산된다.

O_i와 n_j는 Key structure G의 원점이고 T_i는 getTargetPosition 으로 n_i를 Dijkstra algorithm으로 계산한 값이다. 

Dijkstra algorithm는 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.

본 글에는 서술하지 않고 추가 포스트에 서술하겠다.

detectViolation(t) 으로 topology의 깨짐(violation)을 확인하고 깨짐이 발견되면 anchor를 생성한다.

anchor가 생성되면 node를 움직이지 않고 시간을 표현할 수 있어서 좋다. 하지만 너무 많은 anchor가 생성이 되면 지도의 식별성이 떨어지기 때문에 

적절한 값을 주는것이 필요하다.

-------------------------------------------------------------------------------------------------------------------------------------------------

GAP는 쉽게 말해 EM을 DC로 바꿀 때 생기는 node의 이동이 크면 node를 이동시키지 않고 화살표와 anchor를 이용해 이동할 지점을 표시해주는 기술이라고 할 수 있겠다. GAP를 사용하면 DC를 사용할 때 생기는 지도왜곡이 적어져서 사용자가 실제 지형을 파악하는데 GAP를 사용하지 않을 때보다 도움을 준다. 하지만 너무 많은 anchor가 생성이 되면 지도의 식별성이 떨어지기 때문에 적절한 값을 주는것이 필요하다.

위 (d)에서 x가 anchor이다.

2) SRC란?

SRC는 Scalable Road-network Construction의 약어로 직역하면 축척 조절이 용이한 road-network 라는 뜻이다. (Scalability is the capability of a system, network, or process to handle a growing amount of work, or its potential to be enlarged to accommodate that growth. 출처: 위키백과) 사람들이 DC를 사용 할 떄 현재 나와있는 여타 다른 EM과 마찬가지로 실시간이고 빠른 지도를 원할 것이다. 하지만 DC는 계속해서 교통상황과 같은 실시간 데이터를 받아 걸리는 시간을 계산하고 node의 값이 계속 바꾼다. 또한 지도상의 node는 또 얼마나 많은가? 모든 node를 사용할 수 없어서 major feature만 사용한다고 해도 실시간 지도로 나타내기위해서는 간소화가 필요하다. 이 간소화의 정도는 사용자가 지도를 볼 때 raw road network를 파악 할 수 있을 정도를 유지해야 한다.

실제로 사용자는 지도를 hierarchically(계층적으로, 도로를 층층히 보면서)하게 보며 실제 도로 모양과 어느정도 비슷해야 사람들이 DC에서도 지도를 이해하기 편하다. SRC를 위해 아래와 같은 과정을 통해 key structure을 간소화한다. 

Stage 1: OSM(open street map)에서 raw road network를 추출한다. 이 node들은 위,경도 좌표를 포함하고 있으며 간선 도로, 고속도로, 자전거 도로 등 교통에 영향을 주는 도로를 추출한다. 고속도로를 H class, 간선도로를 R class, 그 둘을 이어주는 link를 L class로 두고 이 논문에서는 8,530 pathways와 66,205 nodes를 추출해냈다. 

Stage 2: 이 단계에서는 어느 노드에 degree( 연결되 있는 변의 갯수)가 3이 넘으면 도로를 나눈다. 정확히는  두 개의 끝 점사이의 중간 노드 하나가 다른 변에 이어져 있으면 한 경로를 두 개로 나눕니다. (T- splitting)

Stage 3: dead - end(막다른)길을 없앤다. 기준값은 100m 다

Stage 4: 같은 길(한 끝점이 같은 경우)끼리 합쳐준다.

Stage 5: Ramer-Douglas-Peucker (RDP) line simplification을 한다. 중간 node를 없애고 straight line을 만들어주면서 geographical accuracy를 유지하게 한다.

Stage 6: 이제 서로 근처의 2개의 노드가 같은 group이면 하나로 묶는다. 이렇게 되면 길은 a) highway ramp(고속도로 경사로) b) 다차선도로, c) 로터리 세가지 타입으로 묶는다. 이 stage는 두 노드의 사이의 거리가 기준 값을 넘을 때 까지 반복한다.

Stage 7: DC의 핵심 구조를 구성하기 위해  확대 / 축소 수준과 지도 초점구간을 기반으로 SRC에서 파생 된 여러 유형의 경로를 연결한다. 이로써 정확한 위상적 관계 구축이 가능해진다. 그리고 끊김없이 사용자와 상호 작용할 수 있다. 

▶ Turk 결과

Ray Hong은 2개의 설문조사를 시행하였다.

첫번 째 설문조사는 EM과 DC 둘 중 어떤게 유용한지에 대해 진행하였다. 사람들한테 3가지 시나리오를 주었는데 첫번째 시나리오는 택시기사가 근처 가장 짧은 시간안에 도달할 수 있는 승객(후보군 7명)을 찾는 미션을, 두번째 시나리오는 금요일에 도달시간(travel time)뿐만 아니라 평점도 같이 고려하는 (후보군 14개) 2 factor 가 있는 미션을, 마지막 세번째는 가격, size, 도달시간, 근처 시설 까지 4 factor(20개 후보군)을 고려하며 갈 곳을 결정하는 미션이다. 

67%가 DC가 정보를 얻기 쉽다고 답하였고 80%가 DC를 계속 쓰겠다고 답하였다.

계속 쓰고 싶다고 말한 사람 중 7명이 At-A-Glance 그룹, 5명이 Include-and exclude group으로 분류됐는데

전자는 DC가 simple 한 문제에 쓰기 좋다고 답한사람이었고 후자는 시각적으로 후보들을 grouping 할 수 있기 때문에 어려운 문제에 쓰기 좋다고 답하였다.

2번째 설문은 DC만 쓰는것이 좋은지 DC와 EM을 동시에 같이 사용하는 것이 좋은지에 대한 설문이다. 앞서 말했듯이 DC만 쓰는 지도는 실제 지형지물의 파악에 혼선을 줄 수 있다.(지도의 왜곡이 일어나기 때문에) 설문은 NASA TLX 설문을 따라 cognitive load를 측정하였다.

결과는 다음과 같다.

Stage 1과 Stage 2의 차이점은 stage 2 미션이 실제 지형지물을 활용해야하는 미션이었다는 것이다. Accuracy와 performance를 제외하고 DC가 EM보다 높게 나왔는데 이는 제한시간이 없었기 때문에 참가자들이 높은 정확도를 낼 때 까지 미션을 풀었기 때문이다. 

2번 째 설문 후 interview를 통해 몇가지 결과를 도출 할 수 있었다. 첫번쨰는 사람들이 EM+DC를 DC보다 더 선호한다는 것이다. 실제 지형을 확인 할 수 있다는 것에 EM+DC에 더 높은 신뢰를 보여주었다. 두번째는 당연한 결과지만 사람들이 EM+DC를 사용할 때 실제 지형 환경을 더 잘 이해했다는 것이다. 세번째는 EM+DC 지도가 생소한 DC에 비해 익숙한 EM을 같이 보여줌으로써 DC를 받아들이게 하는데 도움을 준다는 것이다. 

▶ EM + DC

EM+DC 지도의 개념은 EM에 DC를 덧씌운다는 것이 아니다. 여기서 EM+DC는 DC를 보다가 언제든지 EM을 보여준다는 것이다. 버튼을 눌리는식으로(toggle) EM모드 DC모드 지도를 선택한다는 것이다. 여타 다른 인터넷 지도와 마찬가지로 지도의 중요한 점은 랙 없이 빨리빨리 정보를 보여주는 것이다. 하지만 DC의 특성상 다익스트라 알고리즘을 풀어야 Node가 나오기 때문에 DC모드를 껏다 켯다하면 그 때마다 Node를 계산하면 시간도 많이 걸리고 서버 낭비일 것이다. 이 논문에서는 선형 보간(linear interpolation)으로 이 문제를 해결한다.

(a) EM의 키 구조에서 각 노드 N에 대해 N의 직교 좌표 N𝑠𝑡𝑎𝑟𝑡 (𝑥, 𝑦)는 원점 O에서 극 좌표 N𝑠𝑡𝑎𝑟𝑡 (𝑟, φ)로 변환된다. 다음으로 (b) N𝑠𝑡𝑎𝑟𝑡(𝑟, φ)의 목적지, N𝑒𝑛𝑑 (𝑟 ', φ), 거리 𝑟'는 O로부터의 이동 시간을 나타낸다. N𝑒𝑛𝑑의 𝑟 '는 𝑡𝑛 (O에서 n까지의 이동 시간)과 𝑐 (모든 N𝑠𝑡𝑎𝑟𝑡와 N𝑒𝑛𝑑 사이의 변위를 최소화하는 상수)의 곱으로 정의 할 수 있다. (c) N𝑒𝑛𝑑 (𝑟 ', φ)는 데카르트 좌표 N𝑒𝑛𝑑 (𝑥', 𝑦 ')로 변환된다. N𝑒𝑛𝑑 (𝑥 ', 𝑦')가 정의되면 시스템은 N의 위치를  N𝑠𝑡𝑎𝑟𝑡(𝑥,𝑦)에서 N𝑒𝑛𝑑 (𝑥', 𝑦')로 ​​선형적으로 보간한다.

 

결론

위 사진처럼 b) toggle 기능으로 DC와 EM을 교차적으로 보여줄 수 있다. 이것이 EM+DC를 교차적으로 보여줌으로서 사용자에게  DC를 더욱 잘 활용할 수 있게 해준다. SRC기법을 활용하였기 때문에 실시간으로 지도를 볼 수 있고 zoom 기능과 yelp에서 가져온 정보로 각종 위치 type을 볼 수 있고 평점또한 볼 수 있다. 자동차가 그려진 곳이 현재 사용자의 위치이며 동그란 원이 원점으로 부터 걸리는 시간을 표시한 것이다. GAP을 이용하여 심하게 왜곡된 지점을 anchor을 이용하여 표시하였다. 

위 사진의 a)는 EM, b)는 DC, c)는 설문조사시 사용됐던 DC 지도이다. a)와 b)를 보면 알 수 있듯이 DC는 지도의 왜곡이 생길 수 밖에 없고 실제 사용자가 geographic 환경을 햇갈릴 수 있다. 이를 EM+DC 지도로 해결하자는 것이 이 논문의 주제라고 할 수 있겠다.

Reference

모든 사진 및 table은 Designing Interactive Distance Cartograms to Support Urban Travelers, by Ray Hong 등 6명, 2017

혹은 직접 만들었습니다.