トップ地図アプリMap1 > 地図アプリ Map1 の基本方針

地図アプリ Map1 の基本方針

前ページ

基本方針

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

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

OSMバイナリレコード形式

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

{key,val} は OSMタグを表すが、必要に応じて、osm_id、{cx,cy}(ポリゴンの中心)などもここに含める。

head,                                 {lon,lat},  tags_length, {key,val}*  ... point
head,                       num_nds,  {lon,lat}*, tags_length, {key,val}*  ... line
head, way_area,             num_nds,  {lon,lat}*, tags_length, {key,val}*  ... polygon
head, way_area, num_polys, {num_nds}*, {lon,lat}*, tags_length, {key,val}*  ... multipolygon
head:
  第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
  第7bit 0: num_nds は2バイト、1: num_nds は4バイト

point の {lon,lat}、line、polygon の先頭の {lon,lat}、multipolygon の polygon 毎の先頭の {lon,lat} は それぞれ 4バイトペアとする。line、polygon、multipolygon中の各polygon の2番目以降は前との差分を2バイトペア で表す。差分が2バイトで表せないほど大きい場合は、ノードを内挿(追加)して、必ず2バイトで表せるようする。

polygon、multipolygon では、 num_nds(polygon毎のノード数)が2バイトでは表せないほど大きくなることがあるかも知れない。 multipolygon の場合、先頭の outer polygon だけで、 後続の inner polygon のノード数が2バイトで表せないほど大きくなることはないはずであるが、 分かりやすさのため、全部が2バイトか4バイトのいずれかとする。

{lon,lat}* についても、内挿はやめて、一つでも差分が2バイトで表せない場合は、差分をやめる方法もある。 バイナリレコードを利用する側にとっては、全て差分の方がプログラムが分かりやすく、パフォーマンスがよい。

タグについてもパフォーマンス上は short型を追加した方が良いが、その効果は小さいため、これまで通り、 int、long、float、String とする。OSMタグではないが、osm_id もタグ部に置く。ノードの osm_id は long型となる。 厳密には 6バイトでもよいが、効果は小さいので、long 型の方が分かりやすい。

全体としては OSMバイナリレコードの数値は short型が中心となるため、 可変長バイトコードに比べて、それほどサイズ上のロスがなく、プログラムが分かりやすく、パフォーマンスが良い。

OSMタグについて

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

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

文字列について

name:en も含んでいるため、ASCIIコードの比重が高く、文字コードは UTF-8 とした方が、 ファイルサイズは少し小さくなる。しかし、2バイト境界になるよう文字列末尾に 0x00 を補充する措置がいる。

UTF-16とすれば、2バイト単位となり、全体のファイルサイズは少し大きくなるが、プログラムは分かりやすい。

name:en は現在は使っていないので、やめてもよい。

文字列型タグを増やす場合、ファイル単位の辞書式にした方がいいだろう。

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

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

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

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

メッシュ分割

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

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

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

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

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

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

リファレンス