algorithm - (x,y) データのポイント数を減らす方法

Question

私は一連のデータポイントを持っています:

(x1, y1) (x2, y2) (x3, y3) ... (xn, yn)

サンプル ポイントの数は数千になる場合があります。最小限の (30 と仮定しましょう) ポイントのセットで、同じ曲線をできるだけ正確に表現したいと考えています。できるだけ多くの変曲点をキャプチャしたい。ただし、データを表すために許可されるポイントの数には厳しい制限があります。

同じことを達成するための最良のアルゴリズムは何ですか? 役立つフリーソフトウェアライブラリはありますか?

PS: 相対勾配差に基づく点の除去を実装しようとしましたが、これが常に可能な限り最良のデータ表現になるとは限りません。

Answer 1

補間アルゴリズムを探しています。ポイントのセットは数学的な意味での関数ですか（すべての x 値は互いに分離しています）、多項式補間を行うことができます。または、それらが 2 次元平面上に分布している場合は、ベジェ曲線を使用できます。

Answer 2

それは、曲線が各点と交差する必要があるか、または近似であるかによって異なります。試す：

1. ポイントを取る
2. 任意の補間 ( http://en.wikipedia.org/wiki/Polynomial_interpolation ) を適用して、曲線の方程式を取得します。
3. 次に、特定のステップでサンプル ポイントを取得します。