(Ramer-)Douglas-Peuckerのアルゴリズムというものがあることが分かった。折れ線の始点と終点を結ぶ線分と各点の距離を求める。すべての点との距離が許容誤差ε以内に入っていれば始点と終点だけを返して終了。なければ距離が最大の点Pを1つ選択。始点から点Pまでの折れ線と、点Pから終点までの折れ線のそれぞれについてまた1から処理する。再帰的なものはMathematicaの得意分野なので、MathematicaでRamer-Douglas-Peuckerのアルゴリズムを実装してみた。線分と点の距離さて、まずは線分と点の距離を求める関数を作成する。ネットで検索すると直線と点の距離を求めるものが多いが、線分と点の距離のほうが形状をよく保存できるのではないだろうか、と個人的に考えている。H(B、Hは点Aから見た点B、点Hの位置ベクトル)の条件から、Hの座標と実数tの値が求まる。by)^2)}となる。A)tとなるので、3次元以上の場合はこれから計算すればよい。実数tが0から1までの間にあるとき、垂線の足、点Hは線分AB上にある。よって線分ABと点Pの距離は0<=t<=1ならばHPt<0ならばAP1<tならばBPとなる。本当は点Aと点Bが一致してしまう場合を回避しなければならない。折れ線を間引くこれで本題に入れる。距離の最大値と最大値を与える点の番号を別々に求めているところがちょっと冗長だが仕方ない。例MathematicaのCountryDataから取り出せる日本の形状データを使ってこのアルゴリズムをテストしてみた例。ε=0.1間引いた後の点の数を指定できるようにするにはさて、Douglas-Peuckerのアルゴリズムは許容誤差εを与えて間引くので、間引いた後の点の数がいくらになるのかは指定できない。GPSログデータの編集・加工ツールとして有名な轍(Wadachi)では、間引いた後の点の数を指定できる。これを実現するには、以下のようなアルゴリズムになる。始点と終点を結ぶ線分と各点の距離を求める。距離が最大の点Pとその距離の情報をリスト(優先度付きキュー)に加えるリストからもっとも距離の大きい要素を取り出し、点Pを残す点として登録し、残す点の個数をカウントする点Pを新たな終点として、最大距離を与える点とその距離をリストに加える点Pを新たな始点として、最大距離を与える点とその距離をリストに加えるリストが空になるか、点の個数が指定した数になるまで3以降を繰り返す。残す点として登録したものだけを取り出すというアルゴリズムになる。GPXデータを簡略化ではこれを実装した。簡単のため優先度付きキューではなく配列を毎回Sortしている。50]}]元は4672点、赤線が50点に削減したもの。