6

我有一个记录 GPS 数据的设备。每 2-10 秒读取一次读数。对于需要 2 小时的活动，有很多 GPS 点。

有谁知道通过删除冗余数据点来压缩数据集的算法。即如果一系列数据点都在一条直线上，那么只需要起点和终点。

4

5 回答 5

7

查看用于简化多边形的Douglas Peucker 算法。我已经成功地使用它来减少传输给客户用于显示目的的 GPS 航路点的数量。

于 2009-12-29T15:42:50.923 回答
1

有一篇关于在移动设备上压缩 GPS 数据的研究论文。

此外，您可以查看有关编写 GPS 应用程序的 CodeProject 文章。我认为您将遇到的问题不是直点，而是弯曲的道路。这完全取决于您希望自己的路径有多精确。

于 2009-12-29T15:41:38.820 回答
1

您可能想用多项式近似来近似您的路径 x(t), y(t)。你在寻找这样的东西：http ://www.youtube.com/watch?v= YtcZXlKbDJY ???

于 2009-12-29T15:42:33.373 回答
1

您可以通过基于后续点之间的斜率计算执行非常基本的简化来删除冗余点。

这是一些但不完整的 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.

我希望它有所帮助。

于 2010-01-24T16:41:44.487 回答
0

上面给出的代码有几个问题可能使其不适合：

  • “相同坡度”公差衡量的是坡度而不是角度的差异，因此 NNE 到 NNW 的差异被认为比 NE 到 SE 的差异大得多（假设 y 轴从南北走向）。

    解决这个问题的一种方法是测量两个段的点积与它们的长度乘积如何比较的容差。（记住两个向量的点积是它们的长度和它们之间角度的余弦的乘积可能有助于理解。）但是，请参阅下一点。

  • 仅考虑斜率误差而不考虑位置误差，因此长 ENE 段后跟长 ESE 段与在 ENE 和 ESE 之间交替的一串短段一样可能被压缩为单个段。

The approach that I was thinking of would be to look at what vector graphics applications do to convert a list of cursor coordinates into a sequence of curves. E.g. see lib2geom's bezier-utils.cpp. Note that (i) it's almost entirely position-based rather than direction-based; and (ii) it gives cubic bézier curves as output rather than a polyline, though you could use the same approach to give polyline output if that's preferred (in which case the Newton-Raphson step becomes essentially just a simple dot product).

于 2013-05-20T12:28:34.977 回答