Valhalla + Leafletで地図の経路検索を実装する

# これはなに

経路検索エンジンのValhallaと、地図描画ライブラリのLeafletを用いて、経路検索できるWebアプリを作る。

https://valhalla.github.io/valhalla/

https://leafletjs.com/index.html

# 環境構築

## 前提

- Dockerを使える環境がある
- Pythonを使える環境がある

## Valhallaのインストール

https://github.com/valhalla/valhalla/?tab=readme-ov-file#installation を参考に、Valhalla自身が提供するDocker imageを用いて環境を作る。
Docsの記載によると https://github.com/gis-ops/docker-valhalla を用いると手軽にインストールできるとのことで、今回はそちらを使う。

また、経路検索のためにOSM (OpenStreetMap) データが必要なため、geofabrikが提供しているOSMもダウンロードしてくる。

https://download.geofabrik.de/asia/japan/kanto.html

```sh
# 作業用ディレクトリを作る
$ mkdir sandbox-route-map

# dockerコンテナを手軽に立ち上げるためのツール群を持ってくる
$ git clone https://github.com/gis-ops/docker-valhalla.git .

# mapデータを配置するディレクトリを作成する
$ mkdir custom_files

# 関東地方のOSMデータを持ってくる
$ wget -O custom_files/kanto-latest.osm.pbf https://download.geofabrik.de/asia/japan/kanto-latest.osm.pbf

# コンテナを立ち上げる
# 初回はimageがGitHub上からdownloadされるはず
$ docker run -dt --name valhalla_gis-ops -p 8002:8002 -v $PWD/custom_files:/custom_files ghcr.io/gis-ops/docker-valhalla/valhalla:latest

# コンテナが起動していることを確認する
$ docker ps
CONTAINER ID   IMAGE                                             COMMAND                  CREATED          STATUS          PORTS                    NAMES
e3e33e043e02   ghcr.io/gis-ops/docker-valhalla/valhalla:latest   "/valhalla/scripts/r…"   39 seconds ago   Up 38 seconds   0.0.0.0:8002->8002/tcp   valhalla_gis-ops
```

なお、dockerコンテナ立ち上げ直後〜数分間、パソコンがものすごい唸りをあげていた。
OSMデータの読み込み処理が重かったのかなと勝手に予想しているが、真相は如何に……
M1チップのMacbook Pro (メモリ16GB)でこの状態なので、PCスペックによっては厳しいものがあるかもしれない。

後続の動作確認段階では大人しくなったので、本当にコンテナ立ち上げ時の負荷が高いのだろう。多分。

# 動作確認

## 経路検索する

経路検索API、turn-by-turn APIを叩いてみる。

https://valhalla.github.io/valhalla/api/turn-by-turn/overview/

東京駅から新宿駅までの道のりを取得する。

```sh
$ curl http://localhost:8002/route --data '
{
    "locations": [
        {"lat": 35.681236, "lon": 139.767125},  # 東京駅
        {"lat": 35.690921, "lon": 139.700258}  # 新宿駅
    ],
    "costing":"auto",
    "directions_options":{"units":"kilometers"},
    "language": "ja-JP"
}
'
```

結果は爆速で返された :thumbsup:

```json
{
    "trip":{
        "locations":[
            {"type":"break","lat":35.681236,"lon":139.767125,"side_of_street":"left","original_index":0},
            {"type":"break","lat":35.690921,"lon":139.700258,"side_of_street":"right","original_index":1}
        ],
        "legs":[
            {"maneuvers":[
                {"type":3,"instruction":"南方向です。","verbal_succinct_transition_instruction":"南方向です。。その先左方向です。","verbal_pre_transition_instruction":"南方向です。。その先左方向です。","verbal_post_transition_instruction":"60メートル直進です。","time":11.19,"length":0.062,"cost":13.708,"begin_shape_index":0,"end_shape_index":10,"verbal_multi_cue":true,"travel_mode":"drive","travel_type":"car"},
                {"type":15,"instruction":"左方向です。","verbal_transition_alert_instruction":"左方向です。","verbal_succinct_transition_instruction":"左方向です。。その先左方向です。その先丸の内室町線です。","verbal_pre_transition_instruction":"左方向です。。その先左方向です。その先丸の内室町線です。","verbal_post_transition_instruction":"40メートル直進です。","time":10.503,"length":0.043,"cost":41.202,"begin_shape_index":10,"end_shape_index":16,"verbal_multi_cue":true,"travel_mode":"drive","travel_type":"car"},
                {"type":15,"instruction":"左方向です。その先丸の内室町線/407です。","verbal_transition_alert_instruction":"左方向です。その先丸の内室町線です。","verbal_succinct_transition_instruction":"左方向です。","verbal_pre_transition_instruction":"左方向です。その先丸の内室町線, 407です。","verbal_post_transition_instruction":"300メートル直進です。","street_names":["丸の内室町線","407"],"time":27.432,"length":0.344,"cost":104.21,"begin_shape_index":16,"end_shape_index":34,"travel_mode":"drive","travel_type":"car"},
                {"type":10,"instruction":"右方向、鍛冶橋通り/406です。その先、406です。","verbal_transition_alert_instruction":"右方向です。その先鍛冶橋通りです。","verbal_succinct_transition_instruction":"右方向です。","verbal_pre_transition_instruction":"右方向です。その先鍛冶橋通り, 406です。","verbal_post_transition_instruction":"406を400メートル直進です。","street_names":["406"],"begin_street_names":["鍛冶橋通り","406"],"time":29.925,"length":0.379,"cost":130.109,"begin_shape_index":34,"end_shape_index":48,"travel_mode":"drive","travel_type":"car"},
                {"type":15,"instruction":"左方向です。その先1/20/日比谷通りです。","verbal_transition_alert_instruction":"左方向です。その先1です。","verbal_succinct_transition_instruction":"左方向です。","verbal_pre_transition_instruction":"左方向です。その先1, 20です。","verbal_post_transition_instruction":"400メートル直進です。","street_names":["1","20","日比谷通り"],"time":22.912,"length":0.418,"cost":61.812,"begin_shape_index":48,"end_shape_index":59,"travel_mode":"drive","travel_type":"car"},
                {"type":10,"instruction":"右方向、1/20/晴海通りです。その先、20です。","verbal_transition_alert_instruction":"右方向です。その先1です。","verbal_succinct_transition_instruction":"右方向です。","verbal_pre_transition_instruction":"右方向です。その先1, 20です。","verbal_post_transition_instruction":"20を1.5キロメートル直進です。","street_names":["20"],"begin_street_names":["1","20","晴海通り"],"time":78.855,"length":1.428,"cost":208.766,"begin_shape_index":59,"end_shape_index":112,"travel_mode":"drive","travel_type":"car"},
                {"type":23,"instruction":"右方向です。その先20/内堀通りです。","verbal_transition_alert_instruction":"右方向です。その先20です。","verbal_pre_transition_instruction":"右方向です。その先20, 内堀通りです。","verbal_post_transition_instruction":"500メートル直進です。","street_names":["20","内堀通り"],"time":24.724,"length":0.453,"cost":77.301,"begin_shape_index":112,"end_shape_index":132,"travel_mode":"drive","travel_type":"car"},
                {"type":21,"instruction":"四谷/新宿方面、20出口です。","verbal_transition_alert_instruction":"20出口です。","verbal_pre_transition_instruction":"四谷, 新宿方面、20出口です。","verbal_post_transition_instruction":"4キロメートル直進です。","street_names":["20"],"time":203.675,"length":3.864,"cost":345.516,"begin_shape_index":132,"end_shape_index":273,"sign":{"exit_branch_elements":[{"text":"20","consecutive_count":1}],"exit_toward_elements":[{"text":"四谷"},{"text":"新宿"}]},"travel_mode":"drive","travel_type":"car"},
                {"type":16,"instruction":"左方向です。","verbal_transition_alert_instruction":"左方向です。","verbal_succinct_transition_instruction":"左方向です。","verbal_pre_transition_instruction":"左方向です。","verbal_post_transition_instruction":"200メートル直進です。","time":15.843,"length":0.152,"cost":92.401,"begin_shape_index":273,"end_shape_index":281,"travel_mode":"drive","travel_type":"car"},
                {"type":10,"instruction":"右方向です。","verbal_transition_alert_instruction":"右方向です。","verbal_succinct_transition_instruction":"右方向です。。その先左方向です。その先新宿ランブリングロードです。","verbal_pre_transition_instruction":"右方向です。。その先左方向です。その先新宿ランブリングロードです。","verbal_post_transition_instruction":"30メートル直進です。","time":9.123,"length":0.032,"cost":30.407,"begin_shape_index":281,"end_shape_index":282,"verbal_multi_cue":true,"travel_mode":"drive","travel_type":"car"},
                {"type":16,"instruction":"左方向です。その先新宿ランブリングロードです。","verbal_transition_alert_instruction":"左方向です。その先新宿ランブリングロードです。","verbal_succinct_transition_instruction":"左方向です。","verbal_pre_transition_instruction":"左方向です。その先新宿ランブリングロードです。","verbal_post_transition_instruction":"100メートル直進です。","street_names":["新宿ランブリングロード"],"time":14.563,"length":0.14,"cost":80.39,"begin_shape_index":282,"end_shape_index":289,"travel_mode":"drive","travel_type":"car"},
                {"type":15,"instruction":"左方向です。","verbal_transition_alert_instruction":"左方向です。","verbal_succinct_transition_instruction":"左方向です。。その先目的地は右側です。","verbal_pre_transition_instruction":"左方向です。。その先目的地は右側です。","verbal_post_transition_instruction":"30メートル直進です。","time":5.704,"length":0.031,"cost":48.091,"begin_shape_index":289,"end_shape_index":294,"verbal_multi_cue":true,"travel_mode":"drive","travel_type":"car"},
                {"type":5,"instruction":"目的地は右側です。","verbal_transition_alert_instruction":"目的地は右側です。","verbal_pre_transition_instruction":"目的地は右側です。","time":0.0,"length":0.0,"cost":0.0,"begin_shape_index":294,"end_shape_index":294,"travel_mode":"drive","travel_type":"car"}
            ],
            "summary":{
                "has_time_restrictions":false,"has_toll":false,"has_highway":false,"has_ferry":false,"min_lat":35.674896,"min_lon":139.701169,"max_lat":35.69072,"max_lon":139.765784,"time":454.454,"length":7.35,"cost":1233.918
            },
            "shape":"xxx"  // 略
            "summary":{
                "has_time_restrictions":false,
                "has_toll":false,
                "has_highway":false,
                "has_ferry":false,
                "min_lat":35.674896,
                "min_lon":139.701169,
                "max_lat":35.69072,
                "max_lon":139.765784,
                "time":454.454,
                "length":7.35,
                "cost":1233.918
            },
            "status_message":"Found route between points",
            "status":0,
            "units":"kilometers",
            "language":"ja-JP"
        }
}
```

## 経路検索結果をdecodeする

上記結果内において `"shape":"xxx"  // 略` とした部分に、encodeされた経路情報が含まれる。
これをdecodeすることでlat, lon (緯度経度) のリストが取得できる。

```python
import polyline

shape_encoded = ""
shape_decoded = polyline.decode(shape_encoded)

for lat, lon in shape_decoded:
    print(f"Lat: {lat}, Lon: {lon}")
```

下記にも記載のある通り、小数点の位置がよくあるものと違うので、後続の地図描画の際には要注意！

https://valhalla.github.io/valhalla/decoding/

例: decode結果は `356.81004` であるが、Leafletで描画する際には `35.681004` に修正してあげる必要がある。

## 地図を描画する

lat, lonのリストをLeafletで描画すれば、地図上に経路を描画できる！ :raised_hands:



```html
<!DOCTYPE html>
<html>
<head>
    <title>Leaflet Route Example</title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <link rel="stylesheet" href="https://unpkg.com/leaflet@1.9.4/dist/leaflet.css" />
    <script src="https://unpkg.com/leaflet@1.9.4/dist/leaflet.js"></script>
</head>
<body>
    <div id="map" style="width: 100%; height: 600px;"></div>

    <script>
        // 地図の作成
        var map = L.map('map').setView([35.681236, 139.767125], 13);

        // 地図タイルレイヤーの追加
        L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
            attribution: '© OpenStreetMap contributors'
        }).addTo(map);

        // 経路データの取得
        var route = [
            [35.681004, 139.765556],
            [35.680907, 139.765516],
            [35.680826, 139.765481],
            // (中略)
            [35.690686, 139.701178],
            [35.690665, 139.701169],
            [35.690665, 139.701169],
        ];

        // 経路を地図上に描画
        L.polyline(route, {color: 'blue'}).addTo(map);

        // 出発地点と目的地にマーカーを追加
        L.marker([35.681004, 139.765556]).addTo(map)
            .bindPopup('東京駅').openPopup();
        L.marker([35.690665, 139.701169]).addTo(map)
            .bindPopup('新宿駅').openPopup();
    </script>
</body>
</html>
```

上記HTMLファイルをChromeなどで開けば下記のような経路が載った地図を得られる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363036/ed837c5f-c76f-89cd-0987-f279ac1d1150.png)

## 特定の経路を通らないようにする

`exclude_locations` パラメータを利用する。

https://valhalla.github.io/valhalla/api/turn-by-turn/api-reference/#other-request-options

四ツ谷駅周辺を通らないような経路検索をリクエストする

```sh
$ curl http://localhost:8002/route --data '
{
    "locations":[
        {"lat": 35.681236,"lon": 139.767125},
        {"lat": 35.690921, "lon": 139.700258}
    ],
    "costing":"auto",
    "directions_options":{"units":"kilometers"},
    "language": "ja-JP",
    "exclude_locations": [
        {"lat": 35.685399,"lon": 139.717754},
        {"lat": 35.687663,"lon": 139.717983},
        {"lat": 35.687649,"lon": 139.717822}
    ]
}'
```

結果↓

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363036/246963b1-cb6b-9433-9b57-d1c78f2726ce.png)

中心にある四ツ谷駅を避けるルートに変更されている :tada: 

## 特定のエリアを通らないようにする

`exclude_polygons` を使う
valhalla 3.4.0 時点では、 ~~経度→緯度の順番で配列に指定しないと期待通りにエリアを避けてくれない模様？~~ `"type": "break"` の指定が必要な模様？

```sh
curl http://localhost:8002/route --data '
{
    "locations":[
        {"lon": 139.767125, "lat": 35.681236, "type": "break"},
        {"lon": 139.700258, "lat": 35.690921, "type": "break"}
    ],
    "costing":"auto",
    "directions_options":{"units":"kilometers"},
    "language": "ja-JP",
    "exclude_polygons":[
        [
            [139.727350, 35.688417], // 開始と……
            [139.733589, 35.688046],
            [139.733818, 35.682792],
            [139.726359, 35.682532],
            [139.727350, 35.688417]  // 終了で同じ地点を指定する必要あり
        ]
    ]
}'
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363036/aa717668-dde9-64e3-1c98-d2fd29ff8391.png)

なお、ポリゴンの周囲長は10,000m以内とする必要あり。

```json
{
    "error_code":167,
    "error":"Exceeded maximum circumference for exclude_polygons: 10000 meters",
    "status_code":400,
    "status":"Bad Request"
}
```