XLOG

1. 배경회사에서 보행자 네비게이션 기능을 개발할 때 실시간 나의 위치가 경로상 어디에 위치하는지를 update 해줘야 했다. 보행자 경로 특성상 경로와 상관없이 지름길을 이용하기 쉽기에 순서와 상관없이 계산을 해야했다. 처음엔 LinearSearch 를 사용해 전체 coordinates 와의 거리를 계산하였다. 3km ~ 5km 의 경로를 테스트하며 UI 업데이트에 큰 무리는 없었으나, 연산량을 줄이면 배터리 및 성능의 이점을 가져올 수 있을거라 판단하여 확인하던 중 KD Tree 를 알게 되어 도입하게 되었다.2. KD Tree 란?KD Tree(K-Dimensional Tree)는 공간상의 점들을 빠르게 검색하기 위해 설계된 자료구조다. 내 경우는 경로가 2차원 (x, y) 좌표로 구성되어 있었고,..

하다보니 좌표를 전송해야할 필요가 생겼다. 하지만 나한테 주어진 데이터 크기의 제한이 있었다. 그래서 Google Map APi 에서 인코딩된 폴리라인에 관한 내용을 확인하고 적용하려고 했다.구글에서 얘기하는 인코딩된 Polyline해당 알고리즘은 손실이 있는 압축 알고리즘이다. 하지만 그 손실로 발생하는 오차를 최소화 하여 진행된다.좌표값은 위도(Double), 경도(Double) 로 이루어져 있다. 게다가 Polyline 은 이 위도의 배열로 구성되어 있다. 단순한 핵심 Point 뿐만이 아닌 지도상에 도로의 형태에 맞게 각도를 주기 위해 포인트와 포인트 사이에도 많은 좌표가 들어간다.이를 효율적으로(데이터의 오차는 적고, 압축율은 높게) 전달하기 위핸 알고리즘이다.10 진수 값에 1e5를 곱한 다음..