これまで、OSM Relation の扱いは osm2pgsql を参考にしてきた。例えば、行政境界の場合、 多くのwayをつなぎ合わせて、一つ以上の大きなポリゴンまたはマルチポリゴンレコードとした。 元のwayは少なくとも二つ、時には5つ以上といった多数のポリゴン/マルチポリゴンで重複して使用される。 これによりバイナリレコードファイルのサイズは大きくなる。
OSMのxmlファイルは日本地図領域では、uid、timestampなどを含めた場合、2024年10月現在 55GBになるが、 バイナリコード化すると、5.57GBに縮小する(タグはレンダリングに使用するものに限定)。
relation定義自体は 37MB と極めて小さい。relation をラインレコードやポリゴン/マルチポリゴンレコード に展開するのをやめて、レンダリング時にラインやポリゴン/マルチポリゴンを組み立てることにすれば、 バイナリレコードファイルは小さくてすむ。
これまで、バイナリレコードは順次検索でよかったが、レンダリング時に組み立てるには、 特定のレコードの抽出が必要になる。バイナリ検索でよいが、管理データが必要となる。
relationのメンバー配列はポリゴン/マルチポリゴンの場合には、予め、並び替えておく。 繋ぎ合わせるとき、反転がいるケースがある。レンダリング時に判断することもできるが、 事前処理で反転がいるときは、way id を負値にしておくとレンダリング時の処理が楽になる。
後述の Encoder では、type:2、ref:8、role:2 でメンバー当たり12バイトであるが、 node、way、relation の3ブロックに分ければ、type:2 はなくなり、node に対しては ref:8 であるが、 way、relation では現状では ref:4 でもよい。また、role:1 でもよい。
relation管理データとして、relation毎に境界ボックスが追加される。 nodeレコードやwayレコードと同様にブロック分割できるが、ファイルサイズが小さければ、日本全体の relationデータをメモリに常駐させる方がプログラムが楽である。
Encoderの出力フォーマット: 文字コードは UTF-16。 length, osm_id, uid, time, lon, lat, {key, val}* ----- Node length, osm_id, uid, time, bbox, num_nds, {lon, lat}*, {key, val}* ----- Way length, osm_id, uid, time, num_members, {type, ref, role}*, {key, val}* ----- Relation bbox: minlon, minlat, maxlon, maxlat
lengthは自分を含むレコード長(単位:バイト)。
uid、userはペアでコード化する。現在(2024年10月)、japan.osm で、4万弱のため、2バイトでもよいが、 4バイトを割り当てる。
データ更新時刻 time は分単位として、4バイトを割り当てる。精度はもっと下げてもよいので、2バイト化も可能である。 しかし、レコードサイズの縮小に拘らない方がよい。
role は enum で定義し、レコード上は2バイトで表す。inner、outer などいくつかについては、 レンダリングに関係するが、レンダリングでは無視するものが殆どである。 【ソースデータ例】
<node id='31253515' timestamp='2022-01-09T09:59:40Z' uid='7707735' user='zyxzyx' visible='true' version='5' changeset='115935292' lat='35.6536052' lon='139.7601994' />
japan のファイルサイズは node 136MB、way 3.99GB、relation 37.0MB、計4.13GBとなった。
北海道、本州、四国、九州などは除外する。ファイルサイズの縮小は僅かである(37.0 -> 36.7MB)。
length, head, osm_id, uid, time, lon, lat, {key, val}* ----- Node length, head, osm_id, uid, time, bbox, num_nds, {lon, lat}*, {key, val}* ----- Way length, head, osm_id, uid, time, bbox, num_members, {type, ref, role}*, {key, val}* ----- Relation bbox: minlon, minlat, maxlon, maxlat
最終的に Android機に読込むバイナリレコードファイルを作成する。
現在、ハイズームは zoom 13 と zoom 10 で分割している。
建物や住宅内道路など境界バックスが小さいレコードが無数にあるため、zoom 12か13での分割が必須である。
一方、航路は単純な wayレコードであるが、境界ボックスが非常に大きい。 このような大きな境界ボックスをもつレコードのために、zoom 7~10 での分割も必要となる。
OSMのマルチポリゴンには2つ以上の outer polygon をもつ relation がある。 この場合、outer polygon に続いて、その outer polygon に含まれる inner polygon を続ける。 その後に、次の outer polygon を続ける。
個々の outer polygon、inner polygon は順につなげれば、閉ループになるように並び替えておく。 このとき、反転が必要となった場合には、way id(ref)を負に変えておく。
バス路線などラインレコ―ドではエラーがあってもレンダリングする。メンバーを並び替える必要もない。
ポリゴン、マルチポリゴンの場合、閉ループが作れない場合、エラーとなる。全体をエラーとするか、 一部だけをエラーとするかは選択できるようにしておく。
relationのエラーはログファイルに出力しておく。
レンダリング処理では osm_id によるメンバー探索がいる。
Encoderと同じ形式で分割しても osm_id でバイナリサーチできるが、プログラムが少し必要で、検索時間がかかる。 osm_idとオフセットだけをファイル先頭におき、レコードから osm_id と length を除いた方がバイナリサーチは やりやすい。ファイルサイズは変わらず、バイナリサーチはやりやすい。しかし、ブロックのレコード数は分割前には 分からない。一時的に管理ファイルとレコード本体ファイルを別々に作成して、後で一体化するとか、 最初は、Encoderと同じ形式で作り、後で作り変えるなどが考えられる。
順次検索でもさほど処理時間がかからないならば、プログラムは一番簡単である。
レンダリング時にポリゴン/マルチポリゴンを組み立てるには、一つまたは複数のブロックから、wayレコードを とりださなければならない。総合的なレンダリング時間が数倍になることも覚悟の上で、 プログラムの簡単化を模索している。 まずは、順次検索として、もしも、探索時間が問題になるようならバイナリサーチに変更したい。
relationについてはかなりの処理がいるが、 node と way については、単純にブロック分割するだけである。 しかし、polygon についてはいずれ中心位置の算出が必要になる。
まずは node と way を zoom 12 と zoom 7 で分割してみる。
分割ファイルは先頭に head(2または4バイト) を持つ。length や osm_id の上位バイトは使われていないので、 ここにフラグを置くことも可能であるが、ファイルサイズをけちるのはやめたい。
フラグとしては、node/way判別、relationメンバー判別など。
relationメンバーは数%程度と思われるので、別ファイルにする方が検索が速いが、 同じファイルでフラグチェックで済ます方がシンプルで探索時間はさほど増えないだろう。
nodeとwayを別ファイルにする案もあるが、一本化の方がシンプルであろう。
空間検索では全レコードについて境界ボックスをチェックしている。 メンバーの osm_id(ref)を小さい順に並び替えておけば、全レコードを一度スキャンするだけで、 メンバーの offset を求めることができる。
境界ボックスが大きい マルチポリゴン の場合、メンバーが含まれるブロックファイルが複数になるが、 読込むブロックファイルはこれまでと変わらない。
総合レンダリング時間は増える可能性が高いが、ブロックファイルのサイズは小さくなるため、時間短縮の効果もある。 現在、空間検索時間がレンダリング時間に占める割合は数10%程度である。
ハイズームでのレンダリング時間の増加は精々数10%であろう。 中、低ズームは場合によっては1本化する。タイル画像ファイルは一度生成したものを表示するので、 中ズームは数倍、低ズームは10倍、レンダリングに時間がかかってもよい。プログラムをシンプルにしたい。
innerポリゴンは単独でポリゴンレコードとなっていることがある。relationのメンバーとなっていた場合、 重複が起きてもいいので、全メンバーを一つの代表ブロックに置く。 他のブロックでは、代表ブロックだけを知らせるデータを置く。
パソコンでは relation の全wayメンバーをメモリに載せることは容易である。スマホ/タブレットでは、 実際には、ブロックの入れ替えが起きるが、インタフェース上は osm_id を引数として、wayレコードを取りだせる。 ブロックファイルの入れ替えはこれまでよりも増えるため、relation関連のレンダリング時間は増える。 逆に、単独wayレコードのレンダリング時間は若干速くなる。relation関連のレコードは僅かなため、タイル当たりのレンダリング時間は極端に大きくなることはないであろう。
wayレコード自体には境界ボックスが巨大なものは少ないため、これまでハイズームは zoom 12(13)、zoom 7(8)の二つのzoom で分けていたが、これを zoom 12(11~13)のみへの分割とする。
分割前が 4.1GBで、zoom 12分割では最大が 23.5MB、全体で4.81GBとなった。2割の増加は、ブロックをまたがる way は複数の ブロックに置くことによる。
zoom 11分割では重複が減り、全体が 4.52GB(重複1割)となるが、最大が 74MB と大きくなる。最大は 40MB程度に抑えたいので、zoom 12分割がよいだろう。
レンダリング時には近隣ブロックはメモリに読込まれているため、重複をやめて、近隣ブロックから wayレコードを 取り出すことも可能である。relationに採用する方法を node、way にも適用することになるが、量が多いため、レンダリング対象 となるレコードの抽出に時間がかかる。パフォーマンス上は2割の重複の方が優利であろう。
実時間でポリゴン/マルチポリゴンを組み立てる場合もそれをキャッシングしたり、ファイルにセーブすることになる。
事前にosm_id別にポリゴン/マルチポリゴンを作って置き、ブロックファイルにはosm_id、境界ボックスやタグなどのみ 登録しておく案もある。重複によるファイルサイズの増加は小さくなる。ブロックやタイルと同じように、 relationレコードのキャッシュは必要になる。
実時間組み立てプログラムが簡単であれば、それがベストなので、もう少し時間をかけて考える。