2023-01-21

歩行者向けのルート検索に挑戦（その１）

こちらの記事などで、 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 を取り出すのはヒープを使います。このあたりのことは、

データ構造とアルゴリズム

作者:杉原厚吉
共立出版

Amazon

こちらの『データ構造とアルゴリズム』を参考にしています。

動かしてみた結果

作成した 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

2023-01-20

YouTube をテレビで見れるようにする

ミラキャストテレビ android

最近、子どもが大きくなってきたのもあって、タブレットで YouTube を見れるようにしました。そうしたら、まあ、食いつきのすごいこと。こりゃ、テレビ離れも致し方ないな、という納得の勢いです。

一応、タブレット自体の使用時間を制限していますが、食いつくように見てるので、さすがに目に悪いんじゃないかと心配になってきました。考えてみると、 Nintendo Switch は自宅では必ずテレビにつないで大画面でやるようにしているので、 YouTube を見る時も同じようにすればいいんじゃないか？と思い立ちました。

ということで、以前スマホの画面をテレビにキャストするやつ（ミラキャスト、商品は Anycast でした）を買ってたのを思い出したので、それを使ってみることにしました。

問題ないかとおもいきや、接続時に、ちょっとしたトラブルがあったので、そのあたりをメモっておきます。

接続トラブル

まずは、以前の記事と同じ手順で接続してみます。

今回はスマホではなく、子供用に購入しているタブレットをつなぐ形になります。購入したときの顛末をブログに上げてなかったっぽいので、ここに書いときます。

ALLDOCUBE iPlay 40
Android 10
メモリ 8GB
ストレージ 128GB
10.4 インチ IPS 液晶 2000x1000

で、特に考えずに、以前と同じ手順でつないでみます。

ですが、『Connection in progress... 』が表示されるところで止まってしまい、先に進みません。

なんでだろうか？

一応、タブレットの仕様を確認すると

こんな感じに WiFi Display および WiFi Direct が共に Supported になってますので、つながりそうなもんなのですが・・・。

解決

当初、設定作業を子供と一緒にやっていたのですが、その際、 WiFi の接続状態（WiFI ルータのアクセスポイントとの接続）を見ているとしきりと接続・切断を繰り返していました。そのことに子どもが気づいて、『夜８時を過ぎるとWiFi がつながらないのが原因じゃないの？』と言い出しました。

WiFi にそんな制限欠けてたかな？と思いつつも、子どもがそろそろ寝る時間になってしまったので、子どもは寝かして、続きの接続テストは私がやることになりました。

一通り試してみても、やはりうまくいきません。手の打ちようがなくなってきたので、さきほどの子どもの意見を振り返って確認するべく WiFi ルータを調べてみると、なんと、接続時間の制限がかけてありました。

そんな制限かけたんだっけ？　＞　昔の俺

昔、この WiFi ルータに変更したときに書いた記事にも、接続時間制限かけた話は載せてませんでした。

で、WiFi に一時的に接続したうえで、 Anycast との接続を試すと、無事につながりました。子どもに一本取られましたね。すっかり忘れてました。

結局のところ原因は？

これはこれで解決したんですが、念のため、問題を再現しようと同じ事を試してみました。

WiFi 接続を切って（夜８時を過ぎるとつながらなくなります）、 AnyCast と接続させてみます・・・問題なくつながります。

あれ？これが原因じゃなかったのか？

一度、ペアリングができていると挙動が違うのかもしれません。

結局、真の原因はわからずじまいでした。まあ、こういう事例があったという参考程度にしてください。

後日談

問題なく YouTube をテレビで見れるようになったので、子供に使い方説明すると早速試して、ひとしきり楽しんでました。それが終わってから（それなりに時間がたっていたのに）気づくと、いくつかの WiFi 接続がつながらなくなってました。

こちらも原因不明です。しかも、いつの間にやら、再度接続ができるようになっていました。

どういうこと？

一番怪しそうなのが、この Anycast の使ってる周波数帯が 2.4GHz という点です。なので、同じ 2.4GHz 帯の WiFi 接続がおかしくなったんじゃないかな？と推測しています。

AnyCast M2 Plus TV dongle - AnyCast

そういえば、 YouTube を見てた子どものタブレットは 5GHz 側を使ってつないでましたね。

となると、 Miracast (WiFi Direct) と WiFi アクセスポイントへの接続って、周波数帯が異なると干渉しない、同じだと影響することがある？って感じでいいんですかね？

でも、今回トラブった一番最初の接続の時は、Miracast が 2.4GHz 、タブレットの WiFi が 5GHz なので、これだけでいうとつながりそうなんですけどね。WiFi アクセスポイントへの接続が確立していないと、 Miracast 側へも見に行くとかあるんだろうか？

はたして真相はどうなんだろうか？このあたりことは、知らないことばかりなので推測の域を出ないですね。なんにしても、無線関係はトラブると嫌ですねー。

まとめ

とりあえず、無事に YouTube をテレビで見ることができるようになりました。子供の印象は、しばらく見てたらラグるけど慣れた、でした。まあ、あんまり快適ではないかもしれませんが、しばらくは親のエゴに付き合ってもらうことにします。

にしても、『ラグる』って初めて聞きました。最近の小学生はそんな言葉を使うようです。

2022-12-21

OverpassAPI の QL でいろいろと試してみました (2/2)

OverpassAPI

Overpass API でいろいろ試した続きです（基本的な部分は前の記事をご参考にしてください）。

OpenStreeMap の要素としては node, way, relation の３つらしいんですが、 OverpassAPI では area という要素があります。個人的には、この area というものの実態がつかめず、苦労しました。

ということで、この記事では area について思ったことをまとめておきます。

area について

まず、 area というのは、 OpenStreetmap の要素では『ない』というのが大前提としてあります。じゃあ、areaってどうやって決めてるの？

となりますが、こちらの説明にあるように、一定の条件を満たす範囲をエリアとして定義しているとのことです。で、これは、 Overpass API サーバー上でバッチジョブのように動作して、 area を生成しているとのことです。

誤解をおそれずにまとめると、 area というのは、下記のような条件のどれかを満たす way または relation に対して作成される、というもののようです。

relation : タグ admin_level の指定ありかつタグ name の指定あり
relation : タグ type が multipolygon かつタグ name の指定あり
relation : タグ postal_code の指定あり
relation : タグ addr:postcode の指定あり
way : タグ area が yes かつタグ name の指定あり

それぞれのタグの意味を調べるとこんな感じかと思います。

admin_level というタグは自治体などの境界を表現する際に使われているようです。国や県、市町村などで異なるレベルを表現しているようです。
multipolygon はそのまま理解すると多角形なんですが、ここでは、内部に穴が開いているような領域を表現する際に使うもののようです。単なる多角形なら閉じた way （始点と終点が同じ node である way ）でも表現できますからね。
postal_code と addr:postcode は同じ郵便番号を持つ地域を意味しているんだろうと思います。
タグ area は何らかの領域を表しているようです。

area 要素を導入した目的は、ある一定の領域を簡便に取り扱うために導入されたんですよね、きっと。自治体の境界とか、複雑な領域を扱うには、こういうものがあるほうが便利ですよね、そりゃ。チュートリアルの area のページに詳しく書かれていますので一読するといいかと思います。

また、こちらの説明だと area 要素のタグは、元になった relation や way のタグをそのまま使っているとあります。

概要がわかったところで、 area をあれこれ触ってみます。

参考

area についてはなかなか理解できなくて、下記などの説明も参考にしました。

Overpass API の QL の言語リファレンスのエリアによるフィルターにある『警告: area(area); は現在サポートされていません。』の段落など
前の記事で紹介した Overpass API のチュートリアルにある area の説明
map_to_area クエリの説明

個人的には map_to_area の説明を読んだときに、 way または relation に対応して area 要素が作られている、というのをはっきりと認識できて、理解が進みました。

area クエリ

area がどんなものかつかめたら、早速 Overpass API で扱ってみます。まずは、 area を指定して、それを対象にデータを取得してみます。

エリア『伊勢市』に含まれる node を返します（データ量が多いので、実行時にはご注意ください）。

area["name" = "伊勢市"];
node(area);
out;

area クエリは area["name" = "伊勢市"] の部分になります。条件に該当する area を返してきます。

でも、実は、上記の結果は area クエリだけではなく、 area フィルタも通した両方の結果になっています。なので、 area フィルタについてもいろいろと試します。

area フィルタについて

上記の例で node(area) の部分が、 area フィルタで、 area クエリで取得した area を対象に、その area に含まれる node を返すというものになります。

node(area) だけだと、デフォルトの入力集合（デフォルトセット）に含まれる area が対象になるとのことです。 node(area.a) のような表記だと、 a という入力集合に含まれる area が対象になるようです。

他の例も見てみます。

エリア『伊勢市』に含まれる、 way を返します（データ量が多いので、実行時にはご注意ください）。なお、出力形式として out だけだと、 way を構成する node の緯度経度情報が出力されず描画できないので、 geom を付けています。

area["name" = "伊勢市"];
way(area);
out geom;

Wiki のエリアによるフィルターの説明では

ノードの場合は、エリアの内部または境界線上にあるものが検索されます。ウェイの場合は、少なくとも 1 点 (線分上の点も可) がエリアの内部 (境界線を含まない) にあるものが検索されます。エリア境界線上に終端があるだけで、エリアと交わらないようなウェイは、検索されません。リレーションの場合は、そのメンバーのいずれかがエリア内部 (境界線上を含まない) にあるものが検索されます。

とあります。上記の例を見ても、このとおりに area 内に node を持つ way を選択している様子（伊勢市外に道路が伸びている様子）が見てとれますね。

ついでに rel でも試してみます。

area["name" = "伊勢市"];
rel(area);
out geom;

伊勢市にメンバーがあるものが選択されているっぽいですね。

ちなみに、 area クエリが無い状態で、 area フィルタを使うと

node(area);
out;

下記のように、取得したデータがない応答がかえってきてました。

<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="Overpass API 0.7.59 e21c39fe">
<note>The data included in this document is from www.openstreetmap.org. The data is made available under ODbL.</note>
<meta osm_base="2022-12-14T10:04:24Z" areas="2022-12-14T07:49:33Z"/>


</osm>

pivot フィルタ

area クエリで取得した area の輪郭が欲しいときは pivot フィルタというのを使うといいみたいです。

area["name" = "伊勢市"];
rel(pivot);
out geom;

area の元になったリレーションの情報を得ることができるようです。

ちなみに、

area["name" = "伊勢市"];
node(pivot);
out geom;

でも同じ結果を得ることができました。

Wiki の説明だと pivot は way と rel に使うとあるんですが、 node に使ってもエラーにはならずにうまいことやってくれてるようです（が、予期せぬ結果になるかもしれないので避けたほうがいいんでしょうね）。

area クエリで何が返ってくるのか？

最初に示した例は、 area クエリで選択した結果が、デフォルトセットに含まれて、その area に対して、 area フィルタを適用して、 node を表示させたものでした。

じゃあ、 area クエリだけなら、何が返ってくるのかが気になります。

area["name" = "伊勢市"];
out;

とすると、Overpass turbo では表示されない（表示できない）ので、画面上部の選択ボタンで『データ』を選び、データとして表示させて、area クエリで返ってくるものを確認します。

上記の場合は、

<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="Overpass API 0.7.59 e21c39fe">
<note>The data included in this document is from www.openstreetmap.org. The data is made available under ODbL.</note>
<meta osm_base="2022-12-14T10:18:22Z" areas="2022-12-14T07:49:33Z"/>

  <area id="3604538518">
    <tag k="addr:country" v="JP"/>
    <tag k="admin_level" v="7"/>
    <tag k="boundary" v="administrative"/>
    <tag k="is_in:continent" v="Asia"/>
    <tag k="is_in:country" v="Japan"/>
    <tag k="is_in:country_code" v="JP"/>
    <tag k="is_in:iso_3166_2" v="JP-24"/>
    <tag k="is_in:prefecture" v="三重県"/>
    <tag k="is_in:province" v="Mie Prefecture"/>
    <tag k="name" v="伊勢市"/>
    <tag k="name:ar" v="إيسه"/>
    <tag k="name:en" v="Ise"/>
    <tag k="name:fa" v="ایسه، میه"/>
    <tag k="name:ja" v="伊勢市"/>
    <tag k="name:ja_kana" v="いせし"/>
    <tag k="name:ja_rm" v="Ise-Shi"/>
    <tag k="name:ko" v="이세시"/>
    <tag k="name:ru" v="Исе"/>
    <tag k="name:tg" v="Исе"/>
    <tag k="name:uk" v="Ісе"/>
    <tag k="name:zh" v="伊勢市"/>
    <tag k="name:zh-Hans" v="伊势市"/>
    <tag k="name:zh-Hant" v="伊勢市"/>
    <tag k="population" v="127071"/>
    <tag k="postal_code" v="516-0037"/>
    <tag k="source" v="KSJ2/N03"/>
    <tag k="source:population" v="http://www.pref.mie.lg.jp/DATABOX/23355003425.htm"/>
    <tag k="type" v="boundary"/>
    <tag k="website" v="https://www.city.ise.mie.jp/"/>
    <tag k="wikidata" v="Q328067"/>
    <tag k="wikipedia:ja" v="伊勢市"/>
  </area>

</osm>

のような、 area タグとそれに関する情報が返ってきました。これだけだと、緯度経度の情報を含んでいないので、表示できないのもその通りですね。

area の ID について

上記の area ID を確認すると 36xxxxxxxx と 36 で始まっています。こちらの説明によると、これは area の元になったリレーションのIDに対して、 3600000000 を付加したものとのことです。なので、

rel(id:0004538518);
out geom;

とすると、先ほどと同じ境界線を表示することができます。

area クエリ（つづき）

クエリは、完全一致だけでなく正規表現も使えます。そこで、 area クエリで正規表現を使ってみます。

area["name" ~ "伊勢市"];
out;

結果は

<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="Overpass API 0.7.59 e21c39fe">
<note>The data included in this document is from www.openstreetmap.org. The data is made available under ODbL.</note>
<meta osm_base="2022-12-14T10:30:39Z" areas="2022-12-14T07:49:33Z"/>

  <way id="182504191">
    <nd ref="1928645808"/>
    <nd ref="1928645781"/>
    <nd ref="1928645782"/>
    <nd ref="1928645778"/>
    <nd ref="1928645779"/>
    <nd ref="1928645809"/>
    <nd ref="1928645808"/>
    <tag k="building" v="train_station"/>
    <tag k="name" v="伊勢市駅"/>
（中略）
  </way>
  <area id="3604538518">
    <tag k="addr:country" v="JP"/>
    <tag k="admin_level" v="7"/>
（中略）
  </area>

</osm>

のようになってました。今度は、 area タグのほかに way も出力されています。

どうも、Wiki の説明などでは、 area クエリは area を返すとありますが、条件に一致した閉じた way も返しているようです。

is_in クエリ

指定された緯度経度を含むエリアおよび閉じた way を返すとのことです（リンク先の日本語ページには『閉じた way』の表記がありませんが、英語版のページを見ると書かれてます）。

引数として、伊勢市駅付近の緯度経度を指定してみます。

is_in(34.4909706, 136.7097211);
out meta geom;

駅近辺の way が表示されています。

でも、『データ表示』で確認すると、 area として

日本
本州
近畿地方
三重県
伊勢市
東海道
伊勢国

という名前を持つ area が返ってきているのがわかります。

is_in は入力集合を指定することもでき、その場合は入力集合のノードを含むエリアおよび閉じた way を返すようです。

まとめ

Overpass API の機能のうち、 area をいろいろと触ってみました。

最初は area がどんなものかつかめずに戸惑いましたが、 OpenStreetMap では、 way や relation を使って一定の領域（エリア）を工夫して表現しているものを、 area タグという表現を導入することで、便利に扱おうとしていることがよくわかりました。地域を絞り込んで検討したい時などには便利に使えそうです。

にしても、日本語の情報がもっと欲しいものです。

プログラマーのメモ書き

伊勢在住のプログラマーが気になることを気ままにメモったブログです