トップ地図アプリMap > OSMデータファイルのバイナリコード化

OSMデータファイルのバイナリコード化

はじめに

本来ならば、OSM地図レンダリング用ファイルもAndroidタブレットで行いたいが、現有機ではパワー不足で難しい。 日本地図領域のOSMファイル(xmlファイル)は約40GBという大きさである。

SAXParserを使って、前処理を行い、結果をバイナリコード化して、複数のファイルに分割したい。 大きくは Node、Way、Relation に分離する。

OSMデータ(xml形式)としては Nodeセクションは大きいが、殆どが wayを構成するノードを示すものである。 これらの座標値を wayレコードに持たせれば、残るNodeセクションのファイルサイズは小さく、 サイズが大きいのは Wayセクションのみとなる。これまでのところ、最大約1GBとして、4ファイルとなる。

これまで使用してきたプログラムは複雑なものであるが、改めて、一から再構築することにより、かなりの 簡単化が図れる見通しを得た。

現行のOSMバイナリレコード形式

現在の地図アプリがレンダリングに使用しているOSMバイナリレコード形式を以下に示す。

本ページにおけるバイナリコード化は一挙にこのようなレコード形式を目指すものではない。 難しいのは Relation によって表現されるポリゴンやルートである。 このRelation処理は次のステップで行い、ここでは、OSMデータ上のテキスト(xml形式)を単純にバイナリ化するのみである。

一般的なバイナリレコードでは先頭が length のものが多いと思われるが、length を可変長にする場合など、 レコードの様々な種別を表すデータ(head)を先頭に置く方がやりやすい。

head, length, x0, y0, x1, y1, [osm_id,] [way_area,] [xc, yc,] 
num_tags, {key, val,}+ [num_bus_routes,]{bus_route_id}* {num_nds,}* {x, y,}*  

head:
  第0,1bit(0x03) 0: point、1: line、2: polygon、3: multipolygon
  第4bit(0x10) xc, yc, 1:有り 0:無し
  第5bit(0x20) osm_id  1:有り 0:無し  
  第6bit(0x40) 1:bus_route_id有り 0:なし
  第7bit(0x80) 1: 差分座標、0: 絶対座標
  第11~20bit(11)  zorder(-500~599) 
  第21~26bit(6)   wid           LandPolygon, building=yes なども含む
  第27~31bit(5)   minzoom      

(x0, y0) は、境界ボックスの左上座標で、常に絶対座標である。

(x1, y1) および (xc, yc)、(x, y) の (x0, y0) からの差分座標が全て2バイトで表現できる場合にかぎり、 差分レコードとする。

赤字の部分は後から追加したものであるが、少々煩雑である。 バス路線は、特殊タグ扱いとしてタグに含めた方がシンプルになる。 zorder、wid、minzoom についても、レコードサイズに拘りすぎない方がいいだろう。 諸々のデータはタグを含めて一元管理した方がシンプルになる。

タグの値 val が、文字列の場合、コード化しており、辞書ファイルを別途作成している。 少なくとも第1ステップでは、文字列のコード化は行わず、val は utf-16形式の文字列とする。

第1ステップでのOSMバイナリレコード形式

今回、新たに導入する中間形式である。OSMのxmlは階層的であり、上位が node、way、relation である。これら共通の子供として、tag がある。 更に、way には nd、relation には member という子供がある。

node、way、relation、tag、nd、member をそのままレコードとする案と node、way、relation をレコードとして、 子供はそれぞれの親に含ませる案がある。前者の方がレコード形式は簡単であるが、次のステップのプログラムにとっては、 後者の方がやりやすい。

まずは、以下の形式をたたき台としたい。

osm_id, num_tags, {key, val}*, lon, lat                         ----- Node   
osm_id, num_tags, {key, val}*, num_nds, {lon, lat}*             ----- Way  
osm_id, num_tags, {key, val}*, num_members, {type, ref, role}*  ----- Relation      

最初のプログラム

上記の仕様に沿った最初のプログラムを以下に示す。

Encoder.java

Tag.java

実行結果を以下に示す。

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Encoder kanto
maxId=2822F0E7C, nodes=2A6D42B, ways=6B3661, rels=8715, 総サイズ=0.56GB 実行時間: 3.16分

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Encoder japan
maxId=28230265A, nodes=DF15625, ways=1E8A2CA, rels=1E074, 総サイズ=2.72GB 実行時間: 13.56分

Wayは単独で道路などのラインデータか家などのポリゴンデータであるか、またはRelationのメンバーである。

Relationは通常は、ラインかポリゴン/マルチポリゴンとなる。 ラインの場合、レンダリング上は予め、繋ぎ合わせて、一つの長いラインデータにする必要はないが、 ポリゴン/マルチポリゴンの場合、現在は、 繋ぎ合わせて、一つのポリゴン/マルチポリゴンデータとしている。

都道府県境界などは巨大なポリゴン/マルチポリゴンとなる。 空間検索の高速化のために、予め、メッシュ分割しているが、複数のメッシュにまたがる 巨大なポリゴン/マルチポリゴンは同じ巨大なレコードが複数メッシュに置かれるために、 全体のファイルサイズが大きくなる。

都道府県の塗りつぶしは行わず、境界線に沿って内側に都道府県名を描画するのみであるから、 レンダリング用データとしては必ずしもポリゴン/マルチポリゴンデータが要るわけではない。 例えば、東京と神奈川の境界線の場合、境界線ごとに、どちらに東京都、神奈川県を描くかわかればよい。

これを判断するためには、一旦は境界線をつなぎ合わせてポリゴンとする必要があるが、 このポリゴンをそのままレンダリング用データとするのではなく、 個々の境界線データ(Wayオブジェクト)に、ラインの進行方向に向かって、右が東京都Relation(正)、左が神奈川県Relation(負)といった Relation IDを境界線レコードに含ませればこと足りる。

一つの境界線が同時に二つの市の境界線でもあり、二つの県の境界線であることもある。 つまり、複数の境界線Relationの ID を符号付きで持たせるようにする。

プログラム上、上記のことが簡単かどうかはまだ分からない。

陸地ポリゴンの方がはるかに巨大であるが、レンダリング用データとしては予め小さなポリゴンに分割したものを使う。 広域森林については分割されてない地域も多いが、都道府県に比べれば小さい。

レンダリング用OSMバイナリレコード形式[2024.1.25]

先に述べた第1ステップでのOSMバイナリレコード形式はXML形式をコンパクトなバイナリ形式に変換するもの であり、レンダリングに適したものではない。

現行のOSMバイナリレコード形式は煩雑すぎる。もっと、分かりやすい形にしたい。

最初に下記の第一案を考えた。分かりやすいが、レコード長を表すデータがない。

第二案は、先頭にレコード長を持ち、ノード数データ num_nodes はない。

先頭の length で全体の長さが分かっており、 {key, val}* の読み込みが終われば、末尾まで {lon, lat}* であるから、num_nds はなくてもよい。

しかし、outer polygonに1以上の inner polygon が続くマルチポリゴンをどう表すかが問題である。

現地図アプリでは、num_nds は一つの polygon/line の長さであり、 単純な polygon/line では、num_nds は一つ、multipolygon では二つ以上になる。 単純な polygon/line では、なくすることも可能であるが、分かりやすさから、num_ndsを置いている。

量的には multipolygon はほんの少しである。再考の余地はある。

num_kvs, {key, val}*, num_nds, {lon, lat}*               ..... 第一案 
length, num_kvs, {key, val}*, {lon, lat}*                ..... 第二案
length, num_kvs, {key, val}*, {num_nds}*, {lon, lat}*    ..... 第三案

現在は length や num_nodes は4バイトである。 殆どのレコードで length、num_nds は2バイトで表せる。

全体のファイルサイズおよび地図アプリでのメモリ使用量を次のようにすべきであろう。

殆どのレコード長は 2バイトですむことから、2バイトと4バイトを許す。

num_nds はマルチポリゴンに対してのみ持たせる。 大抵は2バイトで表せるが、4バイトになるケースもある。 マルチポリゴンレコードの占める割合は小さいので、ここで、2バイトと4バイトを許しても、ファイルサイズやメモリ使用量に与える影響は小さい。4バイトに統一した方がプログラムが簡単である。

length(2/4), num_kvs(2), {key,val}*, {lon,lat}*                 ... point/line/polygon 
length(2/4), num_kvs(2), {key,val}*, {num_nds(4)}*, {lon,lat}*  ... multipolygon

Java はビッグエンディアンである。例えば、int型(4バイト)であれば、先頭が最上位バイトである。

レコード長(lengthデータ分は除く)が 15ビットで表せる(Short.MAX_VALUE以下)ときは 先頭の2バイトが長さ、それを超えるときは、先頭の4バイトに長さをセット、最上位ビットを 1 にする。

レコード読み込みでは、先頭の2バイトを読み込み、正の値であれば、それがレコード長となる。 負の値であれば、最上位ビットを取り除いたものが、上位2バイトとなる。 次の2バイトを読み込み、これを下位2バイトとして、4バイトにしたものがレコード長となる。

殆どのレコードが 15ビットで表せるため、組み立てのオーバヘッドは符号判定+αであり、ごく小さい。

来歴

2024.1.25 Way単独建物OSMバイナリレコード出力

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -run kanto
建物レコード数=4331819, Wayレコード=7026273, 建物レコードの平均タグ数=1.0707476, 建物レコードの平均Node数=6.527187

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -run japan
建物レコード数=19373553, Wayレコード=32023242, 建物レコードの平均タグ数=1.0443347, 建物レコードの平均Node数=6.330969

2024.1.24 name:jaタグなどの扱い

name:ja、bridge:name などは、そのままでは、enum にできない。name_jaでなく、 name__ja、name__en、bridge__name、tunnel__name とした。

            String skey = atts.getValue("k").replace(":", "__");
            if (Tag.setKeys.contains(skey)) {
                String val = atts.getValue("v");
                Key key = Key.valueOf(skey);
                short ikey = (short)key.ordinal();

これらにより、これらのタグも取り込めるようにできた。この結果、ファイルサイズが少し大きくなった。

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -enc kanto
maxId=2822F0E7C, nodes=2A6D42B, ways=6B3661, rels=8715, 総サイズ=0.56GB 実行時間: 3.39分

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -enc japan
maxId=28230265A, nodes=DF15625, ways=1E8A2CA, rels=1E074, 総サイズ=2.71GB 実行時間: 14.33分

2024.1.21 タグのキー、コードタグの値をshortに変更

いずれ、タグの使い方を広げるため、キーを short型に変更した。byte型に縮小することも可能ではあるが、 ファイルサイズはさほど変わらないため、short型にとどめる。

最終的には建物などレコード数の大半でレンダリング上 osm_id は不要なため、osm_id も特殊タグとする。

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -enc kanto
maxId=2822F0E7C, nodes=2A6D42B, ways=6B3661, rels=8715, 総サイズ=0.55GB 実行時間: 2.94分

c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -enc japan
maxId=28230265A, nodes=DF15625, ways=1E8A2CA, rels=1E074, 総サイズ=2.68GB 実行時間: 13.06分

リファレンス