Google Map API 의 Encoded PolyLine Algorithm

하다보니 좌표를 전송해야할 필요가 생겼다. 하지만 나한테 주어진 데이터 크기의 제한이 있었다. 그래서 Google Map APi 에서 인코딩된 폴리라인에 관한 내용을 확인하고 적용하려고 했다.

구글에서 얘기하는 인코딩된 Polyline

해당 알고리즘은 손실이 있는 압축 알고리즘이다. 하지만 그 손실로 발생하는 오차를 최소화 하여 진행된다.
좌표값은 위도(Double), 경도(Double) 로 이루어져 있다. 게다가 Polyline 은 이 위도의 배열로 구성되어 있다. 단순한 핵심 Point 뿐만이 아닌 지도상에 도로의 형태에 맞게 각도를 주기 위해 포인트와 포인트 사이에도 많은 좌표가 들어간다.

이를 효율적으로(데이터의 오차는 적고, 압축율은 높게) 전달하기 위핸 알고리즘이다.

1. 10 진수 값에 1e5를 곱한 다음, 결과를 반올림하여 정수로 만든다.
   • 여기서 1e5를 곱하는 이유는 오차를 최소화 하며 자릿수를 맞추기 위해
   • 또한 Double 에서 Int 로 변환하여 데이터의 크기를 줄인다.
2. 변환된 정수를 2진수로 만든다. 이 때 음수일 경우 2의 보수(모든 비트를 반전하고, 마지막으로 1을 더한다)를 구하여 계산한다.
   • 비트를 활용한 연산을 하기 위함
   • 이 후 단계 계산에 용이하게 하기 위해
   • 비트 수준 조작으로 계산이 빠르고 메모리 사용을 줄인다.
3. 바이너리 값을 한 비트 왼쪽으로 시프트 한다.
   • 부호를 제거하기 위함
   • 양수와 음수를 구분하지 않고 비트를 압축하기 위한 작업
   • 추후 단계에서 부호 정보를 다른 방식으로 표현하여 부호 비트가 필요없어지고, 그로 인해 데이터 크기가 감소한다.
4. 원래 십진수 값이 음수이면 값을 반전시킨다.
5. 바이너리 값을 오른쪽에서 시작하여 5비트 정크로 나눈다.
   • 압축을 위해 데이터를 분리한다.
   • 데이터를 분리하여 더 작은 단위로 데이터를 처리할 수 있다.
   • 5비트 단위는 작은 값의 데이터를 더 효율적으로 표현하는데 유리하다.
     • Polyline은 좌표의 배열이다. 첫번째 값 이후에 값에 대해서는 이전 값과의 차이만을 사용하여 Encode 하는 방식을 채택했다.
     • 이로 인해 좌표 배열의 압축율을 높일 수 있다.
6. 5비트 정크를 역순으로 배치한다.
   • 디코딩의 효율을 높이기 위해 (길이가 가변적인 데이터도 효율적으로 인코딩, 디코딩이 가능하다.)
7. 다른 비트의 정크가 다음에 오는 경우 값을 0x20 으로 OR 연산을 한다.
   • 연결플래그라고 보면 된다. 하나의 데이터도 5비트의 정크로 나누었고, 해당 값들이 하나의 값을 의미하는 연속하는 데이터라는 것을 표기하기 위한 Flag,
8. 각 값에 63을 더하고 ASCII 값으로 변환한다.
   • 문자열로 표현하여 네트워크 전송 및 저장에 적합한 형태로 만든다.
   • 범용석 (다양한 시스템에서 처리 가능)

그렇다면 Swift 에서 해당 과정을 Encode, Decode 해보자.

Encode

import Foundation
import CoreLocation

func encodedPolyline(from coordinates: [CLLocationCoordinate2D]) -> String {
    var result = ""
    var previousLat = 0
    var previousLng = 0

    coordinates.forEach { coordinate in
        // 1
        let scaledLat = Int(round(coordinate.latitude * 1e5))
        let scaledLng = Int(round(coordinate.longitude * 1e5))

        // 배열에서 첫번째 값을 제외한 나머지 값들은 이전 값과의 차이로 계산하여 압축율을 높인다.
        let deltaLat = scaledLat - previousLat
        let deltaLng = scaledLng - previousLng

        // 1번 이후 인코딩 과정
        result += encodedNumber(deltaLat)
        result += encodedNumber(deltaLng)

        previousLat = scaledLat
        previousLat = scaledLng
    }

    return result
}

private func encodedNumber(_ number: Int) -> String {
    var num = number < 0 ? ~(number << 1) : (number << 1)
    var encoded = ""

    // while 문 기준 : 7번 과정에서 0x20 으로 OR 연산을 했기 때문
    while num >= 0x20 {
        let chunk = (0x20 | (num & 0x1F)) + 63 // 8, 9번 과정
        encoded.append(Character(UnicodeScalar(chunk)!)) // 10
        num >>= 5
    }

    let lastChunk = num + 63
    encoded.append(Character(UnicodeScalar(lastChunk)!))

    return encoded
}

Decode

func decodedPolyline(_ encoded: String) -> [CLLocationCoordinate2D] {
    var index = encoded.startIndex
    var result: [CLLocationCoordinate2D] = []
    var lat = 0
    var lng = 0

    while index < encoded.endIndex {
        let deltaLat = decodedNumber(from: &index, encoded: encoded)
        let deltaLng = decodedNumber(from: &index, encoded: encoded)

        lat += deltaLat
        lng += deltaLng

        let latitude = Double(lat) / 1e5
        let longitude = Double(lng) / 1e5

        result.append(.init(latitude: latitude, longitude: longitude))
    }
    return result
}

func decodedNumber(from index: inout String.Index, encoded: String) -> Int {
    var result = 0
    var shift = 0
    var byte: Int

    repeat {
        byte = Int(encoded[index].asciiValue!) - 63
        result |= (byte & 0x1F) << shift // 하위 5비트 추출 후 적재
        shift += 5
        index = encoded.index(after: index) // 다음 문자로 이동
    } while byte >= 0x20 // 최상위 비트가 1이면 반복한다.(5비트 청크로 나눌때 연결된 값에 플래그

    return (result & 1) != 0 ? ~(result >> 1) : (result >> 1)
}

느낀점

사실 비트 단위로 계산하는 코드를 만들어야겠다는 생각을 한적이 없다. 사실 데이터의 효율을 어떻게 가져올 수 있는지에 대한 고민을 해봤지만 최근에는 결 UI Render 효율에 더 집중했던 것 같다. 뒤늦게 개발이라는 공부를 하고 계속 하고 싶다는 생각을 했지만, 할 수록 공부하고 알아야할게 너무 만핟. 본론적인 자료 구조, 알고리즘에 대한 공부가 필요한 것 같다. 문제를 풀기 위한 공부말고....

 

출처: https://developers.google.com/maps/documentation/utilities/polylinealgorithm?hl=ko