空間検索の第一段は、OSMバイナリレコードファイルをメッシュ分割することにより実施されている。 メッシュ(ブロック)のzoom値はレンダリングするタイルのzoom値より小さいため、 大量のレコードから、レンダリングに使うレコードを抽出する必要がある。
インデックスなどは使わず、順次検索で抽出する。
バイナリレコードファイルはそのままバイト配列データとして読み込む。
空間検索に必要な境界ボックス(minlon, minlat, maxlon, maxlat)は 地図アプリMap3 までは、予め バイナリレコードファイルに含めていた。 含めた場合、その分ファイルサイズは大きくなるため、読み込み時間が大きくなる。
境界ボックスの算出は簡単であるため、今回はファイルは小さくして、 ファイルを読み込んだ時境界ボックスを算出することにした。
class Block {
static final Block[] blocks = new Block[40]; // キャッシュ
int ix; // Block番号
Tile.Source src; // japan、kanto
Tile.Range range; // 低、中、高ズーム
int zoom, x, y; // ブロック座標
String path; // ファイルパス
int ref_count; // 参照スレッド数
long time; // 最終参照時間
byte[] vals; // OSMバイナリレコード(ファイル全体をbyte配列として読込んだもの)
int[] idxs; // 管理データ(head,offset,minlon,minlat,maxlon,maxlat)
}
// バイナリレコードファイルフォーマット
head(4), [num_nds(4),] {lon,lat}*, {key,val}* ... point/line/polygon
head(4), {num_nds(4)}*, {lon,lat}*, {key,val}* ... multipolygon
head:
第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
第2bit(0x04) 0: 差分座標、1: 絶対座標
下位３バイト レコード長
まだ、Relationによるデータは含んでいないが、 分割前のデータ japan.dat、kanto.dat は 1.58GB、342MBであるが、zoom12/7分割により 6.42GB＋66.1MB、 1.34GB＋7.6MB となった。
Map3 に比べて、異常に総ファイルサイズが大きい。同じレコードを同じファイルに何度も書き込んでいる可能性がある。
修正により 1.64GB＋17.4MB、350MB＋2.01MB になった。
マージンは極座標(アプリMap4)とXY平面座標(アプリMap3)では異なってくる。一旦、リセットした。実際の描画を確認しながら改めて設定する。
空間検索結果は OSMのインスタンスの配列とする。
ガーベージコレクションの発生を抑えるために、OSMのインスタンスは再利用する。
配列 int[] pnts、int[] poly_nodes、Tag[] tags の有効データ数は num_nodes*2、num_polys、num_tags である。 通常は、平均値の数倍のサイズを確保した状態を保っているので、メモリ再獲得は起きない。
少数であるが、非常に大きいエリアを使用した場合には、その状態を残さず、一旦、メモリを開放して、 次回に、必要サイズを確保する。このときだけ、ガーベージコレクションの対象が生まれる。
public class OSM {
Block block; // OSMバイナリレコード
int ix; // blocs.idxs[]の先頭位置
short type;
int[] pnts; // lon, lat または x, y の順
int num_nodes; // pnts配列の有効ノード数
int[] poly_nodes; // multipolygonノード数配列
int num_polys; // multipolygonのポリゴン数
Tag[] tags;
int num_tags;
Key skey; // 主キーが一つの時の主キー
Val sval; // 主キーが一つの時の主キーの値
short layer, zorder;
float way_area;
float getWay_area() { return way_area; } // sortで使う
int getZorder() { return zorder; } // sortで使う
// その他[省略]
}
空間検索で抽出されるレンダリングの対象となるレコードは平均的には数百～数千レコードであるが、 レイヤ別レンダリングにより、これらのレコードのタグが数10回チェックされる。
レコードの平均タグ数は１～２の範囲にあるため、Tag[] tags からあるタグを探す時間は僅かであるが、 探索回数が多いため、総時間はかなり大きくなる。 このため、探索回数を減らすために、主キーが一つのときに限り、skey、sval にその値をセットしておく。
所要タグは殆どのレコードでひとつである。高ズームでは、過半数が建物である。中低ズームでは道路である。
建物のレンダリングでは主キーが二つ以上でその一つが建物のケースもあるため、skey が建物の場合だけでなく、 主キーが二つ以上のときはタグの検索も必要となる。
建物以外のレンダリングでは、skey が建物であれば、以下の処理をスキップできる。 建物、道路のレコード数が大半を占めることから、タグ配列 tags の中身のサーチ回数は激減できる。
地図アプリMap3では、各主要タグに１ビットを割り当て、１命令でタグの存在をチェックできるようにしているが、 これをやめる。skeyによるフィルタリングがその代役を果たす。
amenity、building、 highway、 leisure、shop、tourism などが主タグであり、 bridge, tunnel、information、name、playground などは副タグである。
何が主タグかはレンダリングに依存する。
通常は tourism=information、information=board、name=*** であるが、 tourism=information がなく、information=board、name=*** であったとき、 それをエラーとせず、レンダリングするならば、information を skey とすべきである。
skey、sval でレンダリングが決まるわけではないので、この場合、skey なしとしても レンダリングは可能である。
レンダリング対象となるレコードには主要タグが一つはあるというのが筋ではあるが、 設定処理を複雑にしてはいけないので、上記の例の場合、skey なしとする。
建物のレンダリングはひとまず次のようにする。
point/lineレコードは除外する。
skeyが設定され、それが建物でない場合は除外する。
skeyが設定されていない場合のみ getVal()メソッドにより建物タグを取り出す。
建物タグがあった場合のみレンダリングする。 この部分は、いずれ、建物タグの値により、塗りつぶしの色などが変える。
レンダリングに至るまでに時間がかかるのは osm.getVal(Key.building) であるが、 この実行回数は少ない。建物の多い地域で計測したところ、全建物の 5～10％であった。 つまり、skey、sval の導入により、getVal()の実行回数が1/20～1/10に減少する。
public class RBuilding {
final static Paint paintBuildingYes = Renderer.getPaintFill(0xffe0d7d0);
void render(Canvas canvas, Renderer r, OSM[] osms, int fromIndex, int toIndex, int layer) {
for (int n = fromIndex; n < toIndex; n++) {
OSM osm = osms[n];
if (osm.type <= 1) continue;
if (osm.skey != Key.unknown && osm.skey != Key.building) continue;
Val building = osm.skey==Key.building ? osm.sval : osm.getVal(Key.building);
if (building != Val.unknown) {
osm.fillPolygon(canvas, r, paintBuildingYes);
}
}
}
}