マップの上にフィンガーペイントすることによってユーザーがリージョンを選択できるようにするアプリケーションに取り組んでいます。その後、ポイントは緯度/経度に変換され、サーバーにアップロードされます。フィンガータッチデータを正規化するアルゴリズム（ポイント数を減らす）
タッチスクリーンは、3G上でアップロードするにはあまりにも多くのポイントを配信しています。小領域でも最大500ポイントまで蓄積することができます。
私はこのタッチデータを滑らかにしたいと思います（許容範囲内で近似してください）。描画の精度は、領域の一般的な領域が同じであれば、それほど重要ではありません。
これを行うためのよく知られたアルゴリズムはありますか？これはカルマンフィルタのために機能しますか？
Ramer–Douglas–Peucker algorithm（ウィキペディア）があります。
アルゴリズムの目的は、少ない 点と同様の曲線を見つける に、 線分からなる曲線が与えられます。アルゴリズムでは、元の曲線 と簡略化された曲線との間の最大距離が に基づいて、「類似しません」という が定義されています。 簡略化された曲線は、 元の曲線を定義した点のサブセット で構成されています。
データを大幅に削減するには、エキゾチックなものは必要ありません。 次のような単純なものを考えてみましょう。
何らかのエラーメトリックを作成します。簡単なものは、省略された点から近似している線までの距離の正規化された和です。このメトリックを使用して許容可能なエラーが何であるかを決定します。
最初の点から、許容誤差範囲内に収まる最も長い線分を作成します。パス全体をポリラインに変換するまで、このプロセスを繰り返します。
これは、全体的に最適な近似を与えるわけではありませんが、それで十分でしょう。
近似をもっと「カーブ」にしたい場合は、直線セグメントではなくスプラインまたはベジエ曲線を使用することを検討してください。
私はこのアプローチに非常によく似た何かをしました。それはかなりうまくいった - 公差の数字で遊んでください。 – Jonny
私はアプリで、この何かをするつもりだったが、オンザフライポイントからのパスを生成する上で意図されました。このPoint Sequence Interpolationスレッドに記載されているテクニックを使用しようとしていました
4分木または空白曲線を使ってサーフェスをグリッドに細分する必要があります。 sfcは2dの複雑さを1dの複雑さに減らす。あなたは、ニックのヒルベルト曲線quadtree空間インデックスのブログを探しています。
似たようなアプローチを使っているペイントアプリを見たことがありますが、ポイントを減らしながら、実際に描いたラインからラインを移動することがあると感じています。 – Jonny