折れ線データを簡単化する方法としてはRamer-Douglas-Peuckerアルゴリズムが有名である[1]。 これは多数の頂点(node)からなる折れ線データに対して許容誤差範囲内にあるノードを間引くものであり、 再帰法によりプログラムは簡単である。
下のプログラムでは頂点の座標をX座標とY座標（または経度と緯度）をまとめて一つの long 値としている。
点i から 点j までを簡単化する場合、この間の点で、点i と 点j 間の直線との垂直距離が最も大きい 点maxIndexとその距離maxDistance を求めている。この距離が許容誤差に収まるならば、 点i と 点j 間の 頂点は全て間引き、処理終了である。
そうでないときは 点i と 点maxIndex 間 および 点maxIndex 間と点j 間について同じ処理(再帰)を する。
これで、間引きが行えるので実に簡単である。
折れ線の間引きはこれで問題ないが、ポリゴンではいささか問題がある。 元のポリゴンは自己交差のない単純なポリゴンであっても、間引きを行うと、 ねじれ(自己交差。線分と線分が交差する)が生まれることがある。
PostGIS の場合、自己交差が起きた場合、小さなねじれの部分を切り取るようである。 ねじれの部分が大きい場合は、間引きを減らして、切り取りが小さくてすむようにするものと思われる。
自分の場合、何年か前にはねじれを回避して間引きを行ったが、結構プログラムは複雑になる。
小さなねじれがあっても、ポリゴンの塗りつぶしには差し支えない場合もある。 それは塗りつぶしアルゴリズムするため、ねじれはない方が望ましい。
沿岸と小島や埋立地が道路でつながっているとき、ひとつのポリゴンとして表されていることが多い。
低ズームでは、道路の幅はなくなり、一本の線になる。 このような場合、塗りつぶしソフトは正しく動作するのであろうか？ 小島や埋立地が描画されないケースも起こりそうな気がする。
低ズームでは上記のようなアルゴリズムは使わなくてむ、 複数ノードの座標値がほぼ同じ値になってしまうケースが増え、 当然、これらは一つのノードとしてまとめてよい。 ねじれは起きなくても、道路は線になる。
たとえ、0.1画素であっても、幅がある方がいいのだろうか。
void SimplifySection(long[] pnts, int i, int j, double epsilon) {
if ((i + 1) == j) return;
double maxDistance = -1.0;
int maxIndex = i;
for (int k = i + 1; k < j; k++) {
double distance = PerpendicularDistance(pnts[k], pnts[i], pnts[j]);
if (distance > maxDistance) {
maxDistance = distance;
maxIndex = k;
}
}
if (maxDistance <= epsilon) {
for (int k = i + 1; k < j; k++) {
pnts[k] = Long.MIN_VALUE; // 間引く
}
} else {
SimplifySection(pnts, i, maxIndex, epsilon);
SimplifySection(pnts, maxIndex, j, epsilon);
}
}
// １度＝約100km ⇒ 1m＝約0.00001度
double PerpendicularDistance(long p, long p1, long p2) {
double E7 = 10000000.0;
double px = getX(p) / E7;
double py = getY(p) / E7;
double p1x = getX(p1) / E7;
double p1y = getY(p1) / E7;
double p2x = getX(p2) / E7;
double p2y = getY(p2) / E7;
double dx = p2x - p1x;
double dy = p2y - p1y;
double d = Math.sqrt(dx*dx + dy*dy);
return Math.abs(px*dy - py*dx + p2x*p1y - p2y*p1x)/d;
}