こちらの記事などで、 OpenStreetMap のデータを OverpassAPI で取得する話を書きました。
で、これを一生懸命やっているのは、 OpenStreetMap の地図データをもとに、歩行者向けのルート検索をやってみたいなと思ったためです。
というのも、リリース中のアプリ 避難所検索＠伊勢 でルート検索ができるようしているのですが、ここで使っている GraphHopper というライブラリが、スマホ上でのオフラインルート検索機能の開発を停止したためです。
もちろん、現行のものは継続して使えるんですが、先々サポートされないので、困ったな、というのが動機です。
このアプリでカバーする範囲は（一般的なアプリに比べれば）狭い地域だし、歩行者向けであれば交通規制とかの考慮も後回しでいいかなと思うので、自分で組んでみると面白そうです。
もし、うまくルート検索ができるようになれば、このアプリ自体は現在 Android 版だけなので、 Flutter を用いて Android / iOS 両対応にもできるかなと思います。
ということで、手を出してみました。
とりあえず、ルート検索全体の形が見えるまで、あれこれと試行錯誤するだろうから、お手軽に使えるとういことで、まずは Python で試してみることにしました。
今回取り組んだこと
アプリに載せるところまで考えるとなかなか先が長いので、まずは、下記の部分を実装してみました。
- OpenStreetmap のデータから、道路のデータを取り出す
- 道路のデータから、グラフを作る
- グラフ上の２点間の最短経路を見つける
OpenStreetMap の道路は way とそれを構成する node になっているので、それをグラフの形にして持たせてやればなんとかなりそうです。グラフ上の２点間の最短経路を求める方法も、とりあえずは簡単なものを使って試します。
作成したプログラムは GitHub 上のリポジトリにアップしてますので、興味のある方は見てみてください。
OpenStreetmap のデータから、道路のデータを取り出す
OverpassAPI で取得します。取得するデータは、下記クエリで指定するものとします。
[out:json]
[bbox: 34.48756, 136.71216, 34.48906, 136.71424];
way["highway"];
out geom;
地図上でbboxで緯度経度を使って範囲を限定しているのは、扱うデータが大きいとテストにいろいろと余計な手間がかかるためです。
Overpass turbo で表すとこんな感じになります。近鉄宇治山田駅周辺の道路ですね。
問題なく実装ができれば、最終的には下記のように伊勢市全体に範囲を広げてやるつもりです。
[out:json];
area["name" = "伊勢市"];
way(area)["highway"];
out geom;
なお、道路を表すタグとしては、
を参考にして、 highway タグが存在している way としました。
道路のデータから、グラフを作る
取得したデータをもとに、グラフを作ります。クラスの構成としては node クラスを作り、OpenStreetMap の node に対応させます。で、この node クラスに、道路でつながっている他の node を記録させていきます（C とかでグラフを実装するときに使う隣接リストに似たイメージですかね）。
具体的には、つながってる他の node ID とそこまでの距離をペアにしたものを『辺』として、リストにします。ある node に注目したときに、隣接する node の数はそんなに多くないだろうと見込んで、単純なリストにしてみました。
way 単位でこの処理を繰り返しますが、新しい way を追加する場合、同じ node ID が出現したら、既存の node に対してもグラフの辺を追加してやる必要があるので、その処理を行います。
これで、グラフができるはずです（詳細は実装を見てください）。
２点間の距離の算出
なお、グラフを構成する際に、２点間の距離も求めておきます。緯度経度から距離を求めるには、下記の記事を参考にして GeoPy を利用します。
緯度経度から距離を算出するPythonのライブラリ ― GeoPy | H-MEMO
こういうのが簡単に使えるのが Python のありがたいところですね。
グラフ上の２点間の最短経路を見つける
とりあえず、経路検索はダイクストラでやってみます。訪問先の node のうち、最も近い node を取り出すのはヒープを使います。このあたりのことは、
こちらの『データ構造とアルゴリズム』を参考にしています。
動かしてみた結果
作成した Python プログラムを用いて、経路検索を行ってみます。
始点の node は 1301959953 終点の node は 5743469002 という点を選んでみました。
mor@DESKTOP-DE7IL4F:~/work/routing/osm$ python3 overpassapi.py
test
number of osm elements: 11
node id: 332553449, (lat, lon) =(34.4896078, 136.7123982)
adj id: 4594086915, (lat, lon) = (34.4895336, 136.7124605), dist = 10.024779836730287
（中略）
number of node: 62
shortest path
node id: 1301959953, distance: 0 m
node id: 5743469008, distance: 32.745117994646556 m
node id: 1303115718, distance: 83.19043320656411 m
node id: 1251267334, distance: 100.06976611499306 m
node id: 4594086913, distance: 105.76866701812669 m
node id: 4594086921, distance: 112.61548106213671 m
node id: 945145693, distance: 121.24926125927396 m
node id: 945145699, distance: 131.42225299846484 m
node id: 1303115774, distance: 151.44713160863677 m
node id: 1303115756, distance: 203.6311246298111 m
node id: 4592585522, distance: 211.5478194591524 m
node id: 5743469002, distance: 221.89806496501768 m
mor@DESKTOP-DE7IL4F:~/work/routing/osm$
これだけだとよくわからないので、出てきたノードのリストを OverpassAPI で表示させると、
[out:json]
[bbox: 34.48756, 136.71216, 34.48906, 136.71424];
node(id:
1301959953,
5743469008,
1303115718,
1251267334,
4594086913,
4594086921,
945145693,
945145699,
1303115774,
1303115756,
4592585522,
5743469002
);
out;
それっぽい経路が出てますね。
次は
これで、ごくごく簡単ですが、グラフ上の node から 別の node までの経路検索を行うことができるようになりました。
次は、実際の地図アプリで、この経路検索を使うことを想定し、任意の地点から任意の地点までの経路検索をできるようにしたいと思います。
というのも、アプリでルート検索するときに、開始点とかをアプリの地図上でタップして指定したりすると思いますが、このときの地点って、必ずしも道路そのもや道路上にある node に一致しているとは限らないと思います。
なので、タップして指定した地点から、何らかの方法で、道路上にある一番近くの node をどうにか見つける必要があるかと思ってます。これって、考え出すと結構面倒そうです。世の中のルート検索ツールってすごいんですね、改めて実感します。
なかなか先は遠そうですね。
グラフの簡略化
ほかにも、こんなことも組み入れたいです。
今回の実装で作成したグラフですが、分岐（交差点）がないのに node だけがあるような場合があります。例えば、 OpenStreetMap だと一本道だけど曲がってるようなときは、折れ線のような形で表現されるため、折れ線の頂点にノードが存在します。
こういう node （node_t と呼ぶことにします）に隣り合う、前後の同じ way 上の node を node1 , node2 として
node1 - node_t - node2
という並びの関係があるときを考えてみます。
このとき、 node1 - node_t 間の距離を d1 、 nod2 - node_t 間の距離を d2 とすれば、node1 - node2 間の距離は d1 + d2 として求められます。なので、 node_t を削除して、 node1 の隣接ノードとして node2 が存在し、その間の距離は d1 + d2 であるとしてしまえば、最短経路を求めるためのグラフとしては同じものとして扱えるかと思います。ノード数が減れば、グラフがコンパクトになるので、計算時間などの面で有利かなと思われます。
参考までに、下記などに途中のノードを省略する考えとかが載ってました（中身を全部読んだわけではないです）。
https://www.gisa-japan.org/content/files/conferences/2016/papers/F55.pdf
参考
既存のサービス（BBBike）を使って、道路データを抽出する話などもありました。
Webサービスを使って道路ネットワークを取得してみる – FRONT
