高低図を間引く

質問

プログラミングするためのアルゴリズムで悩んでいます。
今、xとしてスタート地点からの距離、yとしてその標高のデータがあります。(x1,y1),(x2,y2)・・・・(xn,yn)のようにｎ個データがありそれをグラフ化しようとしています。
ところが、ある制約からnが例えば20個くらいまでしか扱えません。
そこで、n個のデータを例えば20個に間引いてグラフイメージとして出したいのですが、本来のデータに一番近いイメージを表現するにはどうしたらいいでしょう？

回答No.3

noocyte

これも一案ですが…

> ∧∧∧∧∧∧＿＿＿＿＿＿／￣￣＼＿＿
> これですと、後ろの山は角度が浅いので間引かれてしまいませんか？
> ∧∧∧∧∧∧＿＿＿＿＿＿＿＿＿＿＿＿

もし，上図の左側のような短周期の起伏をならし，右側のような
ゆるい起伏はなるべくそのまま残したい，ということであれば，
地形を時系列信号とみなして，ローパスフィルタをかけると
いいかもしれません．

お礼

ローパスフィルターって昔、聞いたなぁ・・。
電気工学でやったのかな？

実際に数学に当てはめるにはどうするのでしょう？？？

回答No.2

akina_line

こんにちは。

　測点間隔がそれほど差が無いのであれば、前後の高低差が少ない点を省略したらよいのではないですか。
　たとえば、y(a-1)-y(a)、y(a)-y(a+1)の絶対値を調べて、両方とも値が小さければy(a)は省いてもグラフの見た目はあまり変わらないと思います。

では。

お礼

絶対値で比べると、
yが0,1,0,1で推移する凸凹より
yが0,10,20,30となった点を優先してしまいますよね。（この場合は
直線になっちゃいます。）
どんなもんでしょ？

回答No.1

motochan7185

あくまで案ですが・・・

１番目とｎ番目は始点と終点なので間引きから除外。
標高が最大と最小の点は間引きから除外。
残りの点について。
各点(x_i,y_i)に対して、以下の関数を定義します。
f(i) = |(y_i+1 - y_i)/(x_i+1 - x_i) - (y_i - y_i-1)/(x_i - x_i-1)|
i番目の点でどれだけ折れ曲がっているか、の目安です。

f(i)が大きなものから順に残していくように間引けば、
本来のグラフに近いものができるのではないでしょうか。

お礼

ご回答ありがとうございます。折れ曲がり度で間引くのですね。
この場合はどうなりますでしょう。
（最大・最小はとりあえず考慮せず）
∧∧∧∧∧∧＿＿＿＿＿＿／￣￣＼＿＿
これですと、後ろの山は角度が浅いので間引かれてしまいませんか？
∧∧∧∧∧∧＿＿＿＿＿＿＿＿＿＿＿＿

そういうものだと言われればそんな気もしますが・・