我有一个记录GPS数据的设备。每2-10秒进行一次读数。对于需要2小时的活动,有很多GPS点。压缩GPS点数
有谁知道通过删除冗余数据点来压缩数据集的算法。即如果一系列数据点全部在一条直线上,那么只需要起点和终点。
我有一个记录GPS数据的设备。每2-10秒进行一次读数。对于需要2小时的活动,有很多GPS点。压缩GPS点数
有谁知道通过删除冗余数据点来压缩数据集的算法。即如果一系列数据点全部在一条直线上,那么只需要起点和终点。
查看用于简化多边形的Douglas Peucker Algorithm。我已成功地使用此功能来减少传送给客户端进行显示时的GPS航点的数量。
需要注意的是,解决方案存在精度损失。看起来很好btw,如果每个点都需要重新创建,就不太合适。 – 2009-12-29 15:46:01
@psasik:一个卡尔曼过滤器应该解决这个问题。将会出现错误分布,但是随着时间的推移,更多的测量将会提高精度 – 2009-12-29 15:50:45
psasik - 感谢您的信息 - 请看http://www.codeproject.com/KB/cs/Douglas -Peucker_Algorithm.aspx – 2009-12-29 16:38:50
有一篇关于Compressing GPS Data on Mobile Devices的研究论文。
此外,你可以看看这个CodeProject文章Writing GPS Applications。我认为你的问题不是直线,而是弯曲的道路。这完全取决于你希望你的路径有多精确。
感谢Roboto - 这个信息很有趣,但它并不是我所寻找的。无论如何感谢您的信息。 – 2009-12-29 16:41:50
你可能想用它的多项式近似来近似你的路径x(t),y(t)。你在找这样的东西:http://www.youtube.com/watch?v=YtcZXlKbDJY ???
您可以通过基于后续点之间的斜率计算进行非常基本的简化来移除冗余点。
这里是有点,但不是完整的C++代码呈现可能的算法:
struct Point
{
double x;
double y;
};
double calculate_slope(Point const& p1, Point const& p2)
{
// dy y2 - y1
// m = ---- = ---------
// dx x2 - x1
return ((p2.y - p1.y)/(p2.x - p1.x));
}
// 1. Read first two points from GPS stream source
Point p0 = ... ;
Point p1 = ... ;
// 2. Accept p0 as it's first point
// 3. Calculate slope
double m0 = calculate_slope(p0, p1);
// 4. next point is now previous
p0 = p1;
// 5. Read another point
p1 = ... ;
double m1 = calculate_slope(p0, p1);
// 6. Eliminate Compare slopes
double const tolerance = 0.1; // choose your tolerance
double const diff = m0 - m1;
bool if (!((diff <= tolerance) && (diff >= -tolerance)))
{
// 7. Accept p0 and eliminate p1
m0 = m1;
}
// Repeat steps from 4 to 7 for the rest of points.
我希望它能帮助。
上面给出的代码有几个问题,可能使其不适合:
“相同的斜率”宽容措施梯度而非角度差,所以NNE向西北偏北被认为比一个更大的区别NE到SE(假设y轴运行南北)。
解决这个问题的一种方法是测量两个区段点积与其长度乘积的比较公差。 (这可能有助于理解记住两个向量的点积是它们长度和它们之间角度的余弦的乘积。)但是,请参阅下一点。
仅考虑斜率误差而非位置误差,所以长ENE段跟随长ESE段可能会被压缩为单个段,如ENE和ESE之间交替的一段短段。
我想到的方法是查看矢量图形应用程序如何将光标坐标列表转换为曲线序列。例如。请参阅lib2geom的bezier-utils.cpp。请注意:(i)它几乎完全是基于位置的,而不是基于方向的; (ii)它将三次贝塞尔曲线作为输出而不是多段线,尽管如果这是首选的(在这种情况下牛顿 - 拉夫逊步骤本质上只是一个简单的点积),您可以使用相同的方法给出折线输出。
单个位置记录是4个浮点数或16个字节。两个小时每两秒钟是115kb。这种重要的平台是哪种?即使是手机,也没有什么。 – 2009-12-29 15:44:52
@Pavel:取决于使用的卫星数量(最多12个)。NMEA $ GPGSA句子允许多达12颗卫星,加上所有其他辅助数据 – 2009-12-29 15:47:26
我的问题不是存储,而是显示。如果我想在网站上显示路线(通过谷歌地图),那么我不想显示1000个数据点。 – 2009-12-29 16:26:38