地図アプリ Map1 の基本方針

基本方針

これまでは、簡単化も図ったが、どちらかと言えば、パフォーマンスに拘り、プログラムは複雑になってきた。 Map4 では原点に立ち戻り、シンプル化を目指す。

OSMバイナリレコード形式についても抜本的に変更する。

OSMバイナリレコード形式

アプリの要になるのは、OSM地図のレンダリングに使うOSMバイナリレコードのフォーマットである。

できるだけ簡素にしたいが、平均サイズをなるべく小さくしたい。また、パフォーマンスも重要である。

• 殆どのレコードはごく短いが、まれに長いレコードがある。最小限の情報とレコード長を合わせて、 4バイトをレコードの先頭 head とする。
• pointレコードは座標値は一つであるから、ノード数 num_nds はなくてもよい。
• {key,val} は OSMタグを表すが、必要に応じて、 osm_id、wayarea（ポリゴンの面積）、{cx,cy}（ポリゴンの中心）などもここに含める。

  nameタグ、refタグなどの文字列は val とする。(Map3などでは文字列コードであり、文字列自体は辞書にある)

head,             num_nds, 　{lon,lat}*, {key,val}*, EOR  ... point/line/polygon 
head, num_polys, {num_nds}*, {lon,lat}*, {key,val}*, EOR  ... multipolygon
head:
  第0,1bit(0x03) 0: point、   1: line、    2: polygon、 3: multipolygon
  第2bit(0x04)   0: 差分座標、1: 絶対座標
EOR: end of record 0x0000

key は 2バイトで 0x0000 にはならない。よって、EORの検出で判断できる。

いくつかのステップを経て、上記の最終形式となる。途中で、レコードの長さが変化するため、 レコード長は敢えて持たない。

通常はレコードの先頭からパースする。もし、座標値列データを飛ばして、 タグ部 {key,val}* をパースしたい場合、head、num_nodes または head, num_polys, {num_nds}* から比較的簡単に タグ部の先頭が分かる。

OSMタグについて

レンダリングに使用する OSMタグの キーは enum Key で指定する。これに含まれない OSMタグは無視する。 OSMタグの値は enum Val で指定する。ここに含まれない場合、その OSMタグを無視するのではなく、値を Val.unknown とする。

shop、office、building などは無数の値が使われる。マッパーの好みによるものもあり、 事前に enum Val に漏らさず含めるのは得策ではない。shop アイコンは ● とか ■ とする。

文字列について

name:en も含んでいるため、文字コードは UTF-8 とする。ただし、レコード長が２バイトの倍数になるように、 必要に応じて、タグ部の末尾に 0x00 を追加する。これとは別に EOR も付加される。

地図アプリでのOSMバイナリレコードの管理

バイナリレコードは short配列としてそのままメモリに読込む。 全レコードをスキャンして、空間検索に使う境界ボックスなどを int配列に格納する。

可変長バイトコードの場合、復号に手間がかかるため、境界バックスの値をバイナリレコードの上部に置いていたが、 差分コードの場合、簡単に算出できるため、バイナリレコードファイルには境界ボックスは含まれていない。

class Block {
  short[] vals;     // OSMバイナリレコード(ファイル全体をbyte配列として読込んだもの)
  int[]  idxs;      // 境界ボックスなど
  // その他
}

メッシュ分割

データベースでは空間インデックスが使われるが、自作地図アプリではデータベースは一切使用していない。

OSMバイナリレコードは予めメッシュ分割しており、一つのバイナリレコードファイルでの検索は単純な順次検索である。

地図アプリMap3では、zoom 13以上のレンダリングは zoom 13で分割したものを使う。 しかし、広域森林のような巨大なポリゴンは、zoom 13では無数のメッシュ(タイルと同じ)にまたがるため、 重複が多くなる。これを避けるために、zoom 13分割では重複が多すぎるレコードは zoom 7 で分割している。

分割を２段階にするのではなく、境界ボックスが巨大となるレコードは分割せず、レコード毎のファイルにする案もある。 ファイル名は通し番号に境界ボックスの４値を並べたものとする。

zoom 7で分割しても重複はあるため、個別ファイルとした方が全体のファイルサイズは小さくなり、 ファイル読み込み時間は短くなる。

パフォーマンスの向上は期待できるが、分割プログラムやキャッシュ方法は異なるため、プログラムの負担はやや大きくなる。 シンプル化には反するので、大きな効果が期待できなければ見送る。

リファレンス