正常化手指触摸数据的算法（减少点数）

Question

我正在研究一个应用程序，让用户通过手指在地图上选择区域。点然后转换为经度/纬度并上传到服务器。

触摸屏提供的方式太多，需要通过3G上传。即使是小的地区也可以积累高达500点。

我想平滑此触摸数据（近似它在一定的容差范围内）。只要区域的一般区域相同，绘图的准确性并不重要。

是否有任何众所周知的算法来做到这一点？这是否适用于卡尔曼滤波器？

Answer 1

还有Ramer–Douglas–Peucker algorithm（维基百科）。

该算法的目的是，给定一个 线段组成的曲线，以找到 具有较少 点的类似的曲线。该算法基于原始曲线 与简化曲线之间的最大距离来定义 “不相似”。简化曲线由定义原始曲线的点的子集 组成。

Answer 2

您可能不需要任何异乎寻常的东西来大幅削减您的数据。 请考虑一些如此简单的事情：

构造某种错误度量。一个简单的方法就是从被忽略的点到近似它们的线的距离的归一化总和。决定使用此指标的可容忍错误是什么。

然后从第一个点开始构造落在可容忍误差范围内的最长线段。重复此过程直到您将整个路径转换为多段线。

这不会给你全局最优的近似值，但它可能会足够好。

如果您希望近似值更“曲线”，您可以考虑使用样条曲线或贝塞尔曲线而不是直线段。

Answer 3

我打算做一些这在应用程序，但打算在生成从即时点的路径。我打算使用在Point Sequence Interpolation线程中提到的技术

Answer 4

您希望将曲面细分为具有四叉树或空间填充曲线的网格。 sfc将2D复杂性降低到1d复杂度。你想寻找尼克的希尔伯特曲线四叉树空间索引博客。