私は、ユーザーが地図の上に指で絵を描いて地域を選択できるようにするアプリに取り組んでいます。ポイントは緯度/経度に変換され、サーバーにアップロードされます。
タッチ スクリーンは、3G 経由でアップロードするにはあまりにも多くのポイントを提供しています。小さな領域でも最大 500 ポイントまで蓄積できます。
このタッチ データを滑らかにしたいと思います (ある程度の許容範囲内で概算します)。領域の一般的な面積が同じである限り、描画の精度はそれほど重要ではありません。
これを行うためのよく知られたアルゴリズムはありますか? これはカルマンフィルターで機能しますか?
Ramer–Douglas–Peucker アルゴリズム(ウィキペディア)があります。
このアルゴリズムの目的は、線分で構成される曲線が与えられた場合に、より少ない点で類似の曲線を見つけることです。アルゴリズムは、元の曲線と簡略化された曲線の間の最大距離に基づいて「非類似」を定義します。単純化された曲線は、元の曲線を定義したポイントのサブセットで構成されます。
データを劇的に削減するのに、あまりエキゾチックなものは必要ないでしょう。次のような単純なものを考えてみましょう:
ある種のエラー メトリックを構築します。簡単なものは、省略された点からそれらを近似していた線までの距離の正規化された合計です。このメトリックを使用して、許容誤差を決定します。
次に、最初の点から始めて、許容誤差範囲内に収まる最長の線分を作成します。パス全体をポリラインに変換するまで、このプロセスを繰り返します。
これはグローバルに最適な近似を与えるわけではありませんが、おそらく十分です。
近似をより「曲線的に」したい場合は、直線セグメントではなく、スプラインまたはベジェ曲線を使用することを検討してください。
四分木または空間充填曲線を使用してサーフェスをグリッドに分割します。sfc は、2 次元の複雑さを 1 次元の複雑さに減らします。Nick のヒルベルト曲線四分木空間インデックス ブログを探します。
アプリでこれを行うつもりでしたが、オンザフライでポイントからパスを生成するつもりでした。このPoint Sequence Interpolationスレッドで言及されている手法を使用するつもりでした