正常化手指觸摸數據的算法（減少點數）

Question

我正在研究一個應用程序，讓用戶通過手指在地圖上選擇區域。點然後轉換爲經度/緯度並上傳到服務器。

觸摸屏提供的方式太多，需要通過3G上傳。即使是小的地區也可以積累高達500點。

我想平滑此觸摸數據（近似它在一定的容差範圍內）。只要區域的一般區域相同，繪圖的準確性並不重要。

是否有任何衆所周知的算法來做到這一點？這是否適用於卡爾曼濾波器？

Answer 1

還有Ramer–Douglas–Peucker algorithm（維基百科）。

該算法的目的是，給定一個 線段組成的曲線，以找到 具有較少 點的類似的曲線。該算法基於原始曲線 與簡化曲線之間的最大距離來定義 「不相似」。簡化曲線由定義原始曲線的點的子集 組成。

Answer 2

您可能不需要任何異乎尋常的東西來大幅削減您的數據。 請考慮一些如此簡單的事情：

構造某種錯誤度量。一個簡單的方法就是從被忽略的點到近似它們的線的距離的歸一化總和。決定使用此指標的可容忍錯誤是什麼。

然後從第一個點開始構造落在可容忍誤差範圍內的最長線段。重複此過程直到您將整個路徑轉換爲多段線。

這不會給你全局最優的近似值，但它可能會足夠好。

如果您希望近似值更「曲線」，您可以考慮使用樣條曲線或貝塞爾曲線而不是直線段。

Answer 3

我打算做一些這在應用程序，但打算在生成從即時點的路徑。我打算使用在Point Sequence Interpolation線程中提到的技術

Answer 4

您希望將曲面細分爲具有四叉樹或空間填充曲線的網格。 sfc將2D複雜性降低到1d複雜度。你想尋找尼克的希爾伯特曲線四叉樹空間索引博客。