地図アプリでは陸地ポリゴンのレンダリングで陸地ポリゴンと現在のレンダリング対象であるタイルの 矩形領域との交差判定が必要になった。
交差判定なしに無条件に陸地ポリゴンをレンダリングすることができるが、その場合には、時間がかかる。 内陸部地図では通常はタイル矩形領域が陸地ポリゴン内に包含されるため、ポリゴンの描画は不要であり、 矩形領域を塗りつぶすだけでよい。ポリゴンの塗りつぶしよりも桁違いに高速である。
陸地ポリゴンと矩形の重なり部分をレンダリング毎に求める場合には、 ポリゴン描画と大差のない時間がかかる可能性があるが、海岸線を含むようなタイルは除外して、 内陸部のタイルについては、事前にパソコンで求めておくことにより、陸地描画の高速化が図れる。
タイル(矩形)が陸地ポリゴンの内部にあるかどうかを判定するには、 まず、タイルの頂点または中心がポリゴンの内部にあることを判定する。 次に、タイルの一辺が多角形の全線分と交差していないことを判定する。 これを４辺について行えば確かである。効率はよくないがプログラムは簡単である。
Java では Shape.contains(double x, double y, double w, double h)[2,3] が該当する。 ただし、矩形がポリゴンに含まれていても、false を返すケースがあるようだ。 マニュアル[2]をざっと見た限りでは、完全に包含しているわけではないのに true を返すことはないようだ。 であれば、陸地ポリゴンの描画の高速化に使える。
分割も間引きも行っていないOSMのオリジナルな陸地ポリゴンを準備する。 フォーマットは重要ではないが、ここでは、記事[4] のOSMParserのフォーマットとした。 ポリゴンの境界ボックス(ポリゴンの外接矩形)データも含まれている。
このデータでは、地図の左上が原点(0, 0)で、右下が(230, 230) である。
タイルは zoom、x、y で識別される。タイル(0, 0, 0)の座標は、左上が(0, 0)で、 右下が(230, 230) である。
タイル (zoom, x, y) の座標は左上が(x * 230-zoom, y * 230-zoom)で、 右下が((x+1) * 230-zoom, (y+1) * 230-zoom) である。
陸地ポリゴンの数は多いが、大きなものは少ない。いずれかのポリゴンにすっぽり含まれる タイルを求めるのが命題である。
最初に例えば zoom = 10 に対して求める。zoom 10 の一つのタイルが zoom 11 では４つのタイルになる。 zoom 10 で陸地タイルの場合、その４つの子タイルは当然陸地タイルである。 したがって、zoom 11 では zoom 10 で陸地タイルではなかったタイルについてのみ調べる。 ４つとも陸地たいるということはありえない。０～３タイルが陸地タイルとなる。
同じことを zoom 12、zoom 13、... と繰り返す。
要するに海岸線近くのタイルだけが新たに検出されることになる。
初めてのプログラムのため、実行時間の予測ができない。まず、シンプルなプログラムとして、 時間がかかりすぎるようならば考える。
最初のプログラムを下に示す。
import java.io.*;
import java.nio.*;
import java.util.*;
import java.time.*;
import java.awt.*;
public class LandTile {
int cntSrc = 0;
int get(int v, int zoom) {
return v / (1<<(30-zoom));
}
void extract(int x0, int y0, int x1, int y1, int[] xs, int[] ys) {
java.awt.Polygon poly = new java.awt.Polygon(xs, ys, xs.length);
for (int zoom = 8; zoom <= 16; zoom++) {
System.out.printf("zoom=%d\n", zoom);
int xBgn = get(x0, zoom);
int xEnd = get(x1, zoom);
int yBgn = get(y0, zoom);
int yEnd = get(y1, zoom);
for (int x = xBgn; x <= xEnd; x++) {
for (int y = yBgn; y <= yEnd; y++) {
Rectangle rect = new Rectangle(x*(1<<(30-zoom)),
y*(1<<(30-zoom)), 1<<(30-zoom), 1<<(30-zoom));
boolean f = poly.contains(rect);
System.out.printf("%d", f ? 1 : 0);
}
System.out.printf("\n");
}
}
}
void extract() {
String infile = "c:/osm/lands.dat";
File f = new File(infile);
long rest = f.length()/4; // int単位での残りサイズ
try (DataInputStream dis = new DataInputStream(
new BufferedInputStream(new FileInputStream(infile)))) {
while (rest > 0) {
cntSrc++;
int head = dis.readInt();
rest--;
int rec_length = dis.readInt()/4; // int単位に直す
rest--;
int[] buffer = new int[rec_length];
for (int n = 0; n < buffer.length; n++) {
buffer[n] = dis.readInt();
}
rest -= rec_length;
// レコード全体を読み込み終わった
IntBuffer db = IntBuffer.wrap(buffer);
int x0 = db.get(); // (1)
int y0 = db.get(); // (2)
int x1 = db.get(); // (3)
int y1 = db.get(); // (4)
int rid = db.get(); // (5) rid は使わない
int osm_id1 = db.get(); // (6) osm_id
int osm_id2 = db.get();
int iway_area = db.get(); // (7) way_area
float way_area = Float.intBitsToFloat(iway_area);
int key = db.get(); // (10)
int val = db.get(); // (11)
int num_nodes = db.get();
//if (way_area > 10000000000.0) System.out.printf("%d ", num_nodes);
int[] xs = new int[num_nodes];
int[] ys = new int[num_nodes];
for (int i = 0; i < num_nodes; i++) {
xs[i] = db.get();
ys[i] = db.get();
}
extract(x0, y0, x1, y1, xs, ys);
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static void main(String[] args) throws Exception {
long start = System.currentTimeMillis();
LandTile lt = new LandTile();
lt.extract();
System.out.printf("cntSrc=%d 実行時間＝%.2f分\n",
lt.cntSrc, (System.currentTimeMillis() - start)/60000.0 );
}
}
初めてさっと作った割には上出来である。下に出力の一部を抜粋したものを示す。 １は陸地タイルを表す。陸地タイルがうまく検出できているように見える。
処理時間の短縮は考えていない。zoom 毎に、該当タイルを全て求めている。 処理時間や結果データが膨大にならなければこれでよい。 結果は zoom別ファイルとしてみよう。タイルの x, y座標を出力する。
zoom=14 00000000000000000000000000000000000000000000 00000000111100001111000000000000000000000000 00000001111111111111100000000000000000000000 00000111111111111111111110000000000000000000 00011111111111111111111111100000000000000000 00111111111111111111111111111100000000000000 01111111111111111111111111111111000000000000 01111111111111111111111111111111111000000000 01111111111111111111111111111111111100000000 00011111111111111111111111111111111110000000 00000111111111111111111111111111111111000000 00000011111111111111111111111111111111100000 00000000011111111111111111111111111111110000 00000000000011111111111111111111111111110000 00000000000011111111111111111111111111111100 00000000000000111111111111111111111111111100 00000000000000011111111111111111111111111100 00000000000000001111111111111111111111111100 00000000000000000111111111111111111111111110 00000000000000000000000111111111111111111100 00000000000000000000000011111111111111111100 00000000000000000000000001111111111111111100 00000000000000000000000000111111111111111100 00000000000000000000000000011111111111111000 00000000000000000000000000001111111111111000 00000000000000000000000000000011111111110000 00000000000000000000000000000000111111100000 00000000000000000000000000000000001111000000 00000000000000000000000000000000000000000000
世界地図が対象では、時間がかかるだけでなく、 出力ファイルサイズが大きくなりすぎ、実用的ではない。
世界地図は低ズームだけでよいので、陸地タイル判定は日本地図に限定する。 陸地ポリゴンデータを日本地図限定で作ることもできるが、 あれこれファイルを増やさないために、ソースデータは世界地図用ポリゴンデータを使う。
日本地図の外接矩形領域に包含される陸地ポリゴンだけを対象とする。