Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

OptimindAdvent Calendar 2024

Day 8
@kashee337in株式会社オプティマインド

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

Last updated at Posted at 2024-12-08

この記事はOptimind Advent Calendar 2024 8日目の記事です。

前置き

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

スクリーンショット 2024-12-08 152734.png

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

Encoded Polylineの概要

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

Extended Polyline

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

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

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

この関数を用いて以下のように適当に生成したデータ列をエンコードしてみます。

サンプルデータ
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

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用の関数で再度データを復元し描画してみます。

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
無事復元できていそうです。
またこの時、生データとエンコードしたデータでは以下のようなサイズの違いがありました。元々が大したデータ量ではないですが、70%程度には圧縮できていそう。

raw :568byte
encoded :398byte

まとめ

本記事ではPolyline拡張に関する思い付きを実装しその備忘録を残しました。
普段の業務ではなかなか時間が取れないのでこういった機会を活用して無理やり何かやるの大事ですね。ただ、今回の結果を本当にアプリケーションに組み込んで利用するためには、そもそもデータのコンテキストを考慮した適切なデータ圧縮をかけた上でこの手法を適用するのが重要だと思われます。例えば、座標列であればLine Simplificationの手法であるDouglas-Peucker法4などを用いてそもそもの座標データ点自体を削減することで大きくデータを削減することが出来ると考えられます。しかし、これを単純にtimestampやvelocity付きのデータに適用すると間引かれるべきではないデータが間引かれることに繋がり辛い目に合うリスクがあるので、その点引き続き要件等部分だなと思います。

最後に

この後もOptimind Advent Calendar 2024は弊社の多彩なメンバーによる記事が続きますので、ぜひご覧いただければ嬉しいです。
また、オプティマインドの組織について興味を持っていただけた方は、弊社採用資料により詳しい内容が書かれていますのでぜひご覧ください。もっと詳しく知りたいと思っていただけた方はカジュアル面談も大歓迎ですので、気軽にお声がけください。

  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/ ↩

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?