polyline encoding

[1. 개요]

polyline 을 표현하는 방법 중 하나로, lossy compression algorithm 이다.

• 데이터 손실이 있지만, 일련의 좌표를 단일 문자열로 저장할 수 있다.
• geojson 형태로 저장하는 것보다 효율적으로 저장 할 수 있다.

본문에서는 WGS84 좌표를 예시로 정리하도록 한다.

---

[2. encoding flow]

WGS84 좌표 하나에 대해서 아래와 같이 진행한다.

ex) wgs84 좌표(lon, lat) 가 (127.1234567, 32.1234567) 이면,

      127.1234567 하나에 대해서

 

1. 부동소수점 좌표에 (1e+5) 를 곱하여 정수형으로 변환한다.
   => 소수점 5번째자리 까지만 encoding 한다.
   => 여기서 데이터 손실이 발생한다.
   => 더 큰 값을 곱해서 소수점 유실을 줄일 수 있지만, 32bit overflow 가 나지 않도록 주의해야 한다.
2. 1번 단계에서 구한 값을 1bit Left shift 한다.
3. 원래 값이 음수라면, 2번 단계에서 구한 값을 반전시킨다.
   => 이 단계에서, 최상위 bit 는 반드시 0 이 된다.
4. 하위 5bit 값에 대해서 아래 작업을 수행한다.
   4.1: 다음 bit chunk 가 0이 아니면, 4번 단계에서 구한 값에 0x20 을 OR 한다.
   => 5bit chunk 이므로, 6번째 bit 는 0 이다.
   => 하위 6번째 bit 값을 1로 설정한다.
   4.2: 4.1 에서 구한 값에 63 을 더한다.
   4.3: ASCII 문자로 변환한다.
5. 그 다음 하위 bit 에 대해서 4번 작업을 반복한다.
6. 다음 bit chunk 가 0 이면 종료한다.

polyline 은 wgs84 좌표 집합이므로,

lon, lat 을 encoding 한 후, 결과 문자열을 전부 결합하는 방식으로 구한다.

---

[3. code]

Compile 및 실행

1. javac polyline.java -encoding utf-8
2. java polyine

출력

• e}tcWqbacE

---

[4. 참고자료]

• https://developers.google.com/maps/documentation/utilities/polylinealgorithm?hl=ko
• https://stackoverflow.com/questions/9287010/how-to-convert-to-google-encoded-polyline-algorithm-format
•