 |
 |
| zoom 8 | zoom 16（皇居） |
Mapnikの場合、空間検索は PostGIS によっている。 また、osm2pgsql も適宜、PostGISを使っているようである。
しかし、Mapnik、osm2pgsql とも、高速化や高性能化に向けて、 独自実装にシフトしているように窺がえる面がある。
空間検索の分かりやすい実装が見つかれば、真似たいところであるが、 今のところ全く見つからない。
このため、自作地図システムでは、当初から、原始的な方法で空間検索機能を実装している。
OSMバイナリレコードを予め地域別ブロックに振り分けている。 それぞれのレコードの境界ボックス(外接矩形)によってブロックに振り分けるため、 複数のブロックにまたがるレコードは全く同じレコードを複数のブロックに保有している。 この重複分がファイルサイズにすれば３割前後になるであろう。
PostgreSQL/PostGISの場合も空間インデックスのメモリ使用量は大きく、 テーブルサイズの２、３割は占める。
高ズーム用データは zoom 13 と zoom 7 で分割している。 大きなポリゴン(境界ボックスが大きい)は、zoom 13分割では、多数のブロックにまたがり、 総ファイルサイズが大きくなりすぎる。 このため、境界ボックスが大きいレコードは zoom 7 分割としている。
例えば、zoom 18 のレンダリングでは zoom 7、13 分割ファイルを使う。 分割ファイル中のごく一部のレコードしか使わないので、 ここでも検索が必要になる。
Point レコードだけであれば、二分検索が使えるが、 Line や Polygon レコードについては空間検索となり、簡単ではない。
このため、これまでは、単純な順次検索を用いてきた。 レンダリング時間に比べれば、この順次検索時間は小さいが、 次期地図アプリではできればなんらかの改善を図りたい。
空間インデックスを使わない空間検索は簡単である。 レコードの境界ボックスを rectRecord、タイル矩形を rectTile とした場合、 この二つの矩形が交差するかどうかは Rect.intersects(rectRecord, rectTile) で判定できる。 true の場合、そのレコードはレンダリングの対象となり、false の場合はレンダリング対象ではない。
実際にはタイル矩形にはマージンが必要であり、そのマージンは、 レコードが Pointデータ、Lineデータ、Polygonデータかによって異なるため、レコードタイプにより、 rectTile は異なる。
この Rect.intersects(rectRecord, rectTile) を使う方がプログラムは分かりやすいが、 実行時間がかかることを改めて確認した。
このため、ここは地図アプリGISのプログラムを踏襲する。
下のプログラム(赤字部分)に示すように、空間検索は X座標判定とY座標判定を分ける。 両者とも上限と下限の二つの不等式の論理和でレンダリング対象外のレコードを見つけて除外する。
座標値は４バイト整数で表されるが、建物など境界ボックスが小さい場合は、境界ボックスの中心座標からの差分値は ２バイト整数でき、OSMバイナリレコードのサイズは小さくできる。 このため、X座標の判定は、二つに分かれている。
下のプログラムで空間検索自体は 30行程度である。
int next;
for (int ix = 0; ix < buff.length; ix = next) {
int position = ix; // recordの先頭
int head = buff[ix++];
int length = buff[ix++] / 4;
next = ix + length; // 2023.1.6
boolean slim = (head & 0x80) != 0;
int minzoom_wid_zorder = buff[ix+(slim?3:4)]; // 5
int minzoom = minzoom_wid_zorder >> 24; // 最上位バイト
if (zoom < minzoom) {
continue;
}
int type = head & 0x03;
//==================== 空間検索はここから ===================
int W, H, x0, x1;
int XC = buff[ix++]; // 1 bbox中心
int YC = buff[ix++]; // 2 bbox中心
if (slim) {
int WH = buff[ix++]; // 3, 4 w & h
W = WH >> 16;
x0 = XC - W;
x1 = XC + W;
if (x1 < bx0[type] || x0 > bx1[type]) {
continue; // X座標空間検索
}
H = (short)(WH & 0xffff);
} else {
W = buff[ix++]; // 3 w
x0 = XC - W;
x1 = XC + W;
if (x1 < bx0[type] || x0 > bx1[type]) {
continue; // X座標空間検索
}
H = buff[ix++]; // 4 h
}
int y0 = YC - H;
int y1 = YC + H;
if (by0[type] > y1 || y0 > by1[type]) { // Y座標空間検索
continue;
}
ix += 3; // 6 minzoom, osm_id
//=================== 空間検索はここまで =======================
OSM osm = osms[toIndex];
osm.reset();
if (type >= 2) {
osm.way_area = Float.intBitsToFloat(buff[ix++]); // 7
}
osm.blk = (short)block.ix;
osm.pos = position;
osm.head = (short)(head & 0xff);
osm.type = (short)type;
osm.slim = slim;
osm.x0 = XC;
osm.y0 = YC;
osm.buf = Block.blocks[osm.blk].vals;
if ((osm.head & 0x10) != 0) { // xc, yc ありか？
if (slim) {
int xy = buff[ix++];
osm.xc = XC + (short)(xy >> 16);
osm.yc = YC + (short)(xy & 0xffff);
} else {
osm.xc = buff[ix++]; // 8
osm.yc = buff[ix++]; // 9
}
} else if (type == 0) {
osm.xc = x0;
osm.yc = y0;
}
osm.bgnTag = ix; // ここからタグがはじまる
long tag_flags = 0;
while (true) {
int flag_key = buff[ix++];
int key = flag_key & 0x7fffffff;
if (key == Tag.Key.name.ordinal()) {
osm.iname = buff[ix++];
} else {
ix++; // val ここでは使わない
}
if (key > 0 && key < 64) {
tag_flags |= 1L << (key - 1);
}
if (flag_key >= 0) break;
}
osm.tag_flags = tag_flags;
int wid = (minzoom_wid_zorder >> 16) & 0xff; // 第二バイト
int zorder = (short)(minzoom_wid_zorder & 0xffff); // 下位２バイト
osm.wid = (short) wid;
osm.zorder = (short) zorder;
osm.layer = (byte) ((zorder + 500) / 100 - 5);
int nodes = 0;
if (type > 0) {
osm.bgnMulti = ix; // ここから int[] num_nodes
while (true) {
int num_nodes = buff[ix++];
nodes += (num_nodes & 0x7fffffff);
if (num_nodes >= 0) break;
}
}
osm.bgnData = ix; // ここから座標値列データが始まる
osm.endData = next;
osm.nodes = nodes;
toIndex++; // 確定
if (toIndex >= osms.length) break;
}
tile.ixRecord = toIndex;
上記のように、現在は何の工夫もない順次検索である。何らかの工夫により、判定回数を減らしたいものであるが、 簡単な方法をいまだ思いつかない。
空間検索メソッドはレンダリングプログラム(下記)から呼び出される。
陸地ポリゴンレコードと OSMレコードはファイルが分かれているため、空間検索もレンダリングも独立している。
OSMレコードによるレンダリングが下記のプログラムでは renderLandcover.renderLow(cv, ttr, osms, 0, ttr.ixRecord) だけであるが、最終的にはここに７、８レイヤのレンダリングが並ぶ。同じ空間検索結果のデータを使うため、 空間検索としては、これだけで終わりである。
void render(Tile tile) {
long start = System.currentTimeMillis();
tile.status = Tile.Status.busy;
Tile.Source src = tile.src;
int zoom = tile.zoom;
int x = tile.x;
int y = tile.y;
if (src==Tile.Source.japan || src==Tile.Source.kanto || src==Tile.Source.hot) { // レンダリング
Canvas cv = tile.canvas;
TileToRender ttr = tileToRender;
ttr.set(zoom, x, y);
if (false && isLandTile(zoom, x, y)) {
cv.drawRect(0, 0, PX, PX, paintLand);
} else {
cv.drawRect(0, 0, PX, PX, paintWater);
ttr.ixRecord = 0;
if (zoom <= 9) {
Block.getOSMs(1, DIR + "lands_low", ttr, osms);
} else {
Block.getOSMs(1, DIR + "lands_split", ttr, osms);
Block.getOSMs(5, DIR + "lands_split", ttr, osms);
}
for (int n = 0; n < ttr.ixRecord; n++) {
osms[n].fillLandPolygon(cv, ttr, paintLand);
}
}
ttr.ixRecord = 0;
if (zoom <= 7) {
Block.getOSMs(3, DIR + src + "_low", ttr, osms);
} else if (zoom <= 12) {
Block.getOSMs(7, DIR + src + "_mid", ttr, osms);
} else {
Block.getOSMs(6, DIR + src + "_norm", ttr, osms);
Block.getOSMs(12, DIR + src + "_norm", ttr, osms);
}
renderLandcover.renderLow(cv, ttr, osms, 0, ttr.ixRecord);
synchronized (Block.blocks) {
for (int ix = 0; ix < ttr.ixUsing; ix++) {
Block block = Block.blocks[ttr.usingBlocks[ix]];
block.ref_count--;
}
}
} else { // ダウンロード
Bitmap bmp = loadBitmap(tile);
if (bmp == null) bmp = download(tile);
if (bmp == null) {
bmp = tileToRender.bmpWork;
tileToRender.cvWork.drawRect(0, 0, PX, PX, paintNull);
}
putBitmapToTile(bmp, tile);
}
}
マルチポリゴンおよびパターン塗りつぶしは未実装である。 下の時間は空間検索だけでなく、陸地ポリゴンや森林、水域等のレンダリング時間を含んでいる。
レンダリングはマルチスレッドで実行しているため、空間検索の内訳時間を得るのは難しい。
ズーム 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 平均 郊 外 138 114 174 142 97 73 47 70 76 69 65 72 69 78 73 90ms 東 京 155 145 163 109 99 77 68 73 81 89 71 80 68 66 51 93ms
|
|
| zoom 8 | zoom 16（皇居） |
シングルスレッドで空間検索時間とレンダリング時間だけを計測する。 前節の数値は invalidate() を発行してから onDrawが起動されるまでの待ち時間や描画時間も含まれるが、 今回はその計測は行わない。上記の数値では zoom 6～9 の実行時間が大きいが、 空間検索、陸地ポリゴンのレンダリング、森林・水域等のレンダリングのどこに大きな時間がかかっているかを探るのが目的である。
皇居を中心として計測した。この後、レンダリングによって増えるのは最後行だけである。多分２，３倍の値になるであろう。
陸地ポリゴンの検索とレンダリング時間は沿岸では増えるが、日本全体ではこの程度であろう。 空間検索時間については全く問題がない。陸地ポリゴンのレンダリング時間は最終的には全体の10％前後となるであろう。 島国の日本としてはこの程度はやむ得ないであろう。
現在のプログラムでは zoom 13以上は同じブロックファイルからの順次検索のために、ほぼ同じ空間検索時間となる。 ブロックファイルを４段階に分ければ、zoom 15～20 の空間検索時間は縮小できる。 OSMレンダリング時間は最終的には３倍ほどになるとしても、空間検索時間が全体を占める比率は 30％前後になりそうである。
低ズームでは森林ポリゴンが入り組んだ形状のため、レンダリングに時間がかかる。 間引き無しデータが 4GB に対して、低ズーム用は 27,4MB、中ズーム用は 92.6MB に過ぎない。 空間検索やレンダリング時間の短縮の余地があるかも知れない。
低ズームでは抽出されるレコード数が大きいので、空間検索の後処理の時間が問題になる。
[ハイズームは zoom 12, zoom 6分割] zoom 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 平均 陸検索 2.1 3.1 2.6 1.4 2.2 2.4 1.2 0.9 0 0 0 0 0 0 0 1.1ms 陸描画 39.7 51.6 41.1 21.1 36.0 31.5 16.2 13.2 0 0 0 0 0 0 0 16.7ms OSM検索 30.0 56.0 25.7 36.4 48.5 32.5 50.0 92.2 94.1 119.3 118.5 89.0 109.3 88.1 87.1 71.8ms OSM描画 162.9 132.8 229.2 140.0 99.3 18.1 12.6 19.8 12.2 11.8 11.1 4.6 4.9 2.6 1.6 57.6ms
上記のデータはハイズームの分割が zoom 12とzoom 6のときである。やはり、地図アプリGIS のときの zoom 13、zoom 7分割の方が良さそうである。それに変えて測定しなおす。
結果を下に示す。OSMデータの空間検索時間が20％弱減少した。zoom 13以上では約30％の時間短縮となった。 他の数値の変動はたまたまであり、特に理由はない。
[ハイズームは zoom 13, zoom 7分割] zoom 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 平均 陸検索 2.7 3.2 1.8 1.4 2.5 2.7 1.0 1.0 0 0 0 0 0 0 0 1.1ms 陸描画 40.2 52.7 27.9 20.9 35.3 33.3 15.9 12.9 0 0 0 0 0 0 0 16.0ms OSM検索 32.4 56.3 32.3 37.5 52.2 32.5 47.8 70.1 70.1 109.0 79.6 74.2 73.5 69.0 67.5 60.3ms OSM描画 164.5 130.4 243.3 139.5 94.4 19.1 11.4 23.8 11.0 12.4 8.6 5.7 4.3 2.2 1.3 58.1ms
最終的にOSMレンダリング時間が３～５倍になったとしても、ハイズームでは大半の時間を空間検索が占めることになる。 zoom 12以上でも空間検索時間が占める比重が大きいことになる。
レコードの大半を占めるのは小さな建物である。zoom 13では点のように小さい。中心のX座標で並び替えておけば、 小さな建物の場合は狭い範囲に固まっている。
境界ボックスの幅の小さいものと大きいものに二分しておく。大きいものについては、これまで通り順次検索とする。 幅の狭いレコードは境界ボックス中心のX座標で分割しておく。 タイル範囲の検索では、検索範囲を広げて、上限・下限を二分検索で求めれば、順次検索の範囲を狭めて、高速化が可能である。
ただし、プログラムの見通しが付くまでは着手できない。
空間検索で小さな改善をした。少し効果があった。
zoom 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 平均 陸検索 2.2 3.0 2.3 1.3 2.3 2.9 0.9 0.9 0 0 0 0 0 0 0 1.1ms 陸描画 42.1 50.1 36.8 20.6 36.1 36.7 12.4 12.0 0 0 0 0 0 0 0 16.5ms OSM検索 30.8 47.2 24.0 35.3 46.3 31.8 27.7 66.6 64.2 60.7 61.4 60.9 61.9 65.5 65.9 50.0ms OSM描画 165.2 136.5 235.2 119.6 84.0 14.4 5.5 21.4 10.1 6.8 4.2 2.8 2.2 1.9 2.0 54.1ms
空間検索のわずか２行を短縮したが、効果は観測できなかった。
zoom 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 平均 陸検索 2.6 3.1 2.2 1.5 2.3 2.4 1.0 0.8 0 0 0 0 0 0 0 1.1ms 陸描画 40.8 51.1 36.4 20.3 36.5 34.5 16.0 12.5 0 0 0 0 0 0 0 16.5ms OSM検索 28.4 48.1 24.3 27.9 47.6 26.5 42.4 67.5 58.4 57.2 57.2 68.5 70.3 69.2 66.4 50.7ms OSM描画 163.6 131.1 229.6 117.8 87.1 13.6 8.6 21.9 11.2 6.5 4.1 3.2 2.4 2.4 2.1 53.7ms
実際はマルチスレッドで動かす。そのときの総合時間を下に示す。 このページの最初に掲載した結果よりも、短縮している。 ハイズーム用データの分割を zoom 13、7 にした効果が大きい。
現段階では低ズームの時間が大きいが、この先増えるのは、中高ズームの方が大きいので、 全般的には平準化する。
ズーム 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 平均 郊 外 138 117 166 122 73 71 60 65 54 42 56 65 62 55 55 80ms 東 京 142 127 161 103 94 65 51 71 47 58 59 44 51 60 43 78ms
例えば、zoom 18のタイルサイズで、ここに入るオブジェクトをひとまとめにする。 殆どの建物はここに入るため、zoom 13以上での空間検索の対象は半分以下になる。 単純に考えれば、空間検索時間は半減する。
ハイズームでは空間検索時間の比重は高いが、総合的には、この後、低中ズームよりは速くなるので、 空間検索時間に拘らない方が良いかもしれない。
少なくとも、即座に、グルーピングを行うことは見合わせる。
これまでハイズームでの空間検索は zoom 13分割の比重が高いものと思い込んでいた。 調べてみると、以下のように、zoom 7分割が３倍以上、全体の３/４以上を占めていることが分かった。
japan_norm13/7270/3229 37/38850 Recs japan_norm7/113/50 14/133486 Recs
総ファイルサイズは増大するが、zoom 7分割を zoom 8分割に変えてみる。 ファイルサイズは 716MB から 1.97GB へと大幅増となった。 境界ボックスが大きいデータが多いということである。 吟味すれば、レンダリングに使わないレコードは予め除去できよう。 取りあえずはこの数値を許容する。 この様子では、ブロック当たりのファイルサイズはさほど小さくなっていない可能性がある。
レンダリングに使わない巨大なレコードを除去する必要があるかも知れない。
japan_norm13/7270/3229 37/38850 Recs japan_norm8/227/100 14/98603 Recs
測定結果を下に示す。少しは効果がある。
ズーム 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 平均 郊 外 134 120 178 127 76 70 59 66 45 39 42 49 63 35 51 77ms 東 京 142 127 161 90 94 65 78 64 58 49 55 57 54 38 48 71ms