Polyline拡張に関する実験備忘録

この記事は[Optimind Advent Calendar 2024](https://qiita.com/advent-calendar/2024/optimind) 8日目の記事です。
# 前置き
株式会社オプティマインドでは世界のラストワンマイルを最適化するためのソリューションである[Loogia](https://loogia.jp/)というプロダクトを提供しています。このLoogiaのようにGISデータを用いるアプリケーションでは頻出であるPolylineデータというものがあり、これは連続する緯度経度の座標列を効率的に圧縮・符号化したものです。
なぜこのようなデータ形式が必要なのかというと、例えば地図アプリケーションに経路探索の結果である経路データを組み合わせて描画することを考えると、サーバーとクライアント間でやり取りされる経路データは、数百から数千の座標点を含むことがあります。これらを単純なJSON配列（例：[[lat1, lng1], [lat2, lng2], ...]）で渡すと、データ量が大きくなり、通信遅延やコスト増を招きます。
それに対してPolylineエンコード手法を用いて座標列をテキストベースの短い文字列に圧縮することで、データ転送量を削減することができます。
例えば、以下のような走行軌跡は`wisuEmaqbYaNt@aFPa@cOw@}XSwHOyEA_@i@BuAFuAFsGZA@`のような文字列としてエンコードされます。

![スクリーンショット 2024-12-08 152734.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2327853/3d71393d-1d66-3ad4-bcfb-6d84b3d34a67.png)

本記事は、このPolylineのエンコード方式に着目しその拡張に関する実験結果を備忘録として残すものです。

# Encoded Polylineの概要
PolylineエンコーディングのアルゴリズムとしてはGoogleのEncoded Polyline Algorithm[^1]を用ることが一般的なようです。このアルゴリズムではデータを整数化した上で、バイナリコードレベルでの前処理を行って5ビットのチャンクに分解した後、ASCIIコードの範囲に落とすことで連続した座標列を文字列へ圧縮・符号化を行っています。また、リスト内の各データは独立した要素として符号化するのではなく、前の要素の値との差分として表現することでより圧縮してエンコードすることができます。

https://developers.google.com/maps/documentation/utilities/polylinealgorithm?hl=ja

# Extended Polyline
前記のアルゴリズムの中身を考えると、当然座標データだけに限定されるような手法ではなく数値データ一般に適用することのできる手法であることが分かります。GISデータを扱うようなアプリケーションでは座標列だけではなく種々のデータを効率的に送受信したいような場合があります。例えば、動態の実績データを基に対象がいつどこにいてどの程度滞在したのかなどの分析を行う上では座標という「どこにいた」の情報だけではなくtimestampなどのような「いつ」という情報が重要になります。実際そのようなtimestampを含んだ拡張形式として、time_aware_polylineと呼ばれる実装なども公開されています。[^2][^3]
それ以外にも、速度情報、加速度情報、GPS精度の情報など、必要な情報を圧縮した形でエンコードしたいというニーズはアプリケーション次第では発生するでしょう。

そこでそのような付加情報を含んだデータのエンコード・デコードも通常のアルゴリズム実装にほんの少し改造を加えればできるのでは？と思ったので実装・実験を行いました。
今回は通常のエンコード対象である座標データに加えてtimestamp,velocityを付加することを考えます。これは通常のEncoded Polylineを拡張して以下のような形で実装できます。
```python
from dataclasses import dataclass
from typing import List

@dataclass
class Coordinate:
    latitude: float
    longitude: float
    timestamp: int
    velocity: float

def encode_extended_polyline(coords: List[Coordinate]) -> str:
    """timestampと速度含むpolylineをエンコードする"""
    result = []
    prev_lat = 0
    prev_lng = 0
    prev_time = 0
    prev_vel = 0

    for coord in coords:
        # データのスケーリング：必要な精度だけ残す形で整数化する
        lat_scaled = int(round(coord.latitude * 1e5)) 
        lng_scaled = int(round(coord.longitude * 1e5))        
        vel_scaled = int(round(coord.velocity * 1e1))

        dlat = lat_scaled - prev_lat
        dlng = lng_scaled - prev_lng
        dtime = coord.timestamp - prev_time
        dvel = vel_scaled - prev_vel

        # 差分をビット左シフトして符号を反転（Google polyline algorithm）
        for v in [dlat, dlng, dtime, dvel]:
            v = ~(v << 1) if v < 0 else (v << 1)
            # 5bit chunkへの分解と連続blcokの表現
            while v >= 0x20:
                result.append(chr((0x20 | (v & 0x1f)) + 63))
                v >>= 5
            result.append(chr(v + 63))
        
        # 次ループ用の値更新
        prev_lat = lat_scaled
        prev_lng = lng_scaled
        prev_time = coord.timestamp
        prev_vel = vel_scaled
    return ''.join(result)

def decode_extended_polyline(encoded: str) -> List[Coordinate]:
    """上記の拡張polylineをdecodeする"""
    index = 0
    current_lat = 0
    current_lng = 0
    current_time = 0
    current_vel = 0
    coordinates = []

    while index < len(encoded):
        current_lat += _decode_chunks(encoded, index)
        index += _chunk_length(encoded, index)
        current_lng += _decode_chunks(encoded, index)
        index += _chunk_length(encoded, index)
        current_time += _decode_chunks(encoded, index)
        index += _chunk_length(encoded, index)
        current_vel += _decode_chunks(encoded, index)
        index += _chunk_length(encoded, index)
        
        coordinates.append(Coordinate(
            latitude=current_lat / 1e5,
            longitude=current_lng / 1e5,
            timestamp=current_time,
            velocity=current_vel / 1e1
        ))

    return coordinates

def _decode_chunks(encoded: str, index: int) -> int:
    shift = 0
    result = 0
    while True:
        byte = ord(encoded[index]) - 63
        index += 1
        result |= (byte & 0x1f) << shift
        shift += 5
        if byte < 0x20:
            break
    return ~(result >> 1) if (result & 1) else (result >> 1)

def _chunk_length(encoded: str, index: int) -> int:
    length = 0
    while True:
        if ord(encoded[index]) - 63 < 0x20:
            break
        index += 1
        length += 1
    return length + 1

```
この関数を用いて以下のように適当に生成したデータ列をエンコードしてみます。
<details><summary>サンプルデータ</summary>

```csv:sample.csv
latitude,longitude,timestamp,velocity
35.16588,136.89895,1733640813,1.8
35.16613,136.89892,1733640833,1.4
35.16638,136.89889,1733640853,1.4
35.16663,136.89887,1733640873,1.7
35.16688,136.89884,1733640893,1.5
35.16713,136.89881,1733640913,1.8
35.16738,136.89878,1733640933,1.9
35.16763,136.89875,1733640953,1.4
35.16788,136.89873,1733640973,1.9
35.16813,136.89870,1733640993,1.5
35.16838,136.89867,1733641013,1.6
35.16863,136.89865,1733641033,1.8
35.16888,136.89863,1733641053,1.8
35.16913,136.89861,1733641073,1.7
35.16938,136.89859,1733641093,1.6
35.16944,136.89885,1733641113,1.6
35.16946,136.89915,1733641133,1.6
35.16948,136.89946,1733641153,1.7
35.16950,136.89977,1733641173,1.7
35.16952,136.90007,1733641193,1.7
35.16954,136.90038,1733641213,1.8
35.16956,136.90068,1733641233,1.8
35.16958,136.90099,1733641253,1.9
35.16960,136.90129,1733641273,1.4
35.16962,136.90160,1733641293,1.9
35.16964,136.90190,1733641313,1.5
35.16966,136.90221,1733641333,1.9
35.16968,136.90251,1733641353,1.5
35.16970,136.90282,1733641373,1.5
35.16972,136.90312,1733641393,1.5
35.16974,136.90343,1733641413,1.9
35.16976,136.90373,1733641433,1.8
35.16978,136.90404,1733641453,1.9
35.16980,136.90434,1733641473,1.8
35.16982,136.90465,1733641493,1.5
35.16985,136.90495,1733641513,1.8
35.16987,136.90526,1733641533,1.5
35.16989,136.90556,1733641553,1.6
35.16991,136.90587,1733641573,1.7
35.16992,136.90618,1733641593,1.5
35.16994,136.90648,1733641613,1.8
35.16996,136.90679,1733641633,1.6
35.16999,136.90709,1733641653,1.5
35.17001,136.90740,1733641673,1.4
35.17003,136.90771,1733641693,1.5
35.17005,136.90802,1733641713,1.6
35.17023,136.90811,1733641733,1.5
35.17048,136.90809,1733641753,1.5
35.17074,136.90807,1733641773,1.4
35.17099,136.90804,1733641793,1.7
35.17124,136.90802,1733641813,1.5
35.17149,136.90799,1733641833,1.5
35.17174,136.90797,1733641853,1.6
35.17200,136.90794,1733641873,1.5
35.17225,136.90792,1733641893,1.6
35.17250,136.90789,1733641913,1.8
```
</details>

```python
import pandas as pd

df = pd.read_csv("sample.csv")
coordinates = [
        Coordinate(row['latitude'], row['longitude'], int(row['timestamp']), row['velocity'])
        for index, row in df.iterrows()]
        
encoded_polyline = encode_coords_with_velocity(coordinates)
print("Encoded Polyline:", encoded_polyline)
```
結果は以下のような文字列が出力されます。
```
Encoded Polyline: wisuEmaqbYye`tifBc@q@Dg@Fq@Dg@?q@Bg@Eq@Dg@Bq@Dg@Eq@Dg@Aq@Dg@Hq@Bg@Iq@Dg@Fq@Dg@Aq@Bg@Cq@Bg@?q@Bg@@q@Bg@@Ks@g@?C{@g@?C}@g@AC}@g@?C{@g@?C}@g@AC{@g@?C}@g@AC{@g@HC}@g@IC{@g@FC}@g@GC{@g@FC}@g@?C{@g@?C}@g@GC{@g@@C}@g@AC{@g@@C}@g@DE{@g@EC}@g@DC{@g@AC}@g@AA}@g@BC{@g@EC}@g@BE{@g@@C}@g@@C}@g@AC}@g@Ac@Qg@@q@Bg@?s@Bg@@q@Dg@Eq@Bg@Bq@Dg@?q@Bg@As@Dg@@q@Bg@Aq@Dg@C
```
このpolylineを上記に書いたdecode用の関数で再度データを復元し描画してみます。
```python
from folium import Map, Marker, Icon, Circle

decoded_polyline = decode_polyline(encoded_polyline)

# 以下描画処理
m = Map()

# 始点終点
start_point = (decoded_polyline[0].latitude, decoded_polyline[0].longitude)
end_point = (decoded_polyline[-1].latitude, decoded_polyline[-1].longitude)
Marker(start_point, icon=Icon(color="red"), popup="Optimind").add_to(m)
Marker(end_point, icon=Icon(color="blue")).add_to(m)

# 経路点
for row in decoded_polyline:
    Circle(
        [row.latitude, row.longitude],
        radius=10,
        popup=f'latitude:{row.latitude}, lngitude:{row.longitude}, timestamp:{row.timestamp}, velocity:{row.velocity}'
    ).add_to(m)

m.fit_bounds(m.get_bounds())

display(m)
```
![スクリーンショット 2024-12-08 163152.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2327853/7c41af62-e31b-df8c-0db9-10abc5ccea92.png)
無事復元できていそうです。
またこの時、生データとエンコードしたデータでは以下のようなサイズの違いがありました。元々が大したデータ量ではないですが、70%程度には圧縮できていそう。
```bash
raw :568byte
encoded :398byte
```

# まとめ
本記事ではPolyline拡張に関する思い付きを実装しその備忘録を残しました。
普段の業務ではなかなか時間が取れないのでこういった機会を活用して無理やり何かやるの大事ですね。ただ、今回の結果を本当にアプリケーションに組み込んで利用するためには、そもそもデータのコンテキストを考慮した適切なデータ圧縮をかけた上でこの手法を適用するのが重要だと思われます。例えば、座標列であればLine Simplificationの手法であるDouglas-Peucker法[^4]などを用いてそもそもの座標データ点自体を削減することで大きくデータを削減することが出来ると考えられます。しかし、これを単純にtimestampやvelocity付きのデータに適用すると間引かれるべきではないデータが間引かれることに繋がり辛い目に合うリスクがあるので、その点引き続き要検討な部分だなと思います。
# 最後に
この後も[Optimind Advent Calendar 2024](https://qiita.com/advent-calendar/2024/optimind)は弊社の多彩なメンバーによる記事が続きますので、ぜひご覧いただければ嬉しいです。
また、オプティマインドの組織について興味を持っていただけた方は、弊社採用資料により詳しい内容が書かれていますのでぜひご覧ください。もっと詳しく知りたいと思っていただけた方はカジュアル面談も大歓迎ですので、気軽にお声がけください。

https://recruit.optimind.tech/

[^1]:https://developers.google.com/maps/documentation/utilities/polylinealgorithm?hl=ja
[^2]:https://github.com/Root-App/time_aware_polyline
[^3]:https://www.npmjs.com/package/time-aware-polyline
[^4]:https://www.trail-note.net/tech/thinout/