压缩GPS点

退房 Douglas Peucker Algorithm 用于简化多边形。我成功地使用了它来减少将GPS航路点传输给客户进行显示时的数量。

有一篇关于 Compressing GPS Data on Mobile Devices .

此外,您可以查看下面的代码项目文章 Writing GPS Applications . 我认为你会遇到的问题不是直的点,而是弯曲的道路。这完全取决于你想要你的路径有多精确。

你可能想用它的多项式近似来近似你的路径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到NNW被认为比NE到SE的差异大得多(假设Y轴向北向南)。

  解决这一问题的一种方法是公差测量两段的点积与长度的乘积的比较。(记住两个向量的点积是它们的长度和它们之间夹角的余弦的乘积可能有助于理解。)但是,请参见下一点。

• 只考虑坡度误差而不考虑位置误差,因此长的ene段和长的ese段很可能被压缩为单个段,就像在ene和ese之间交替出现的一系列短段一样。

我想到的方法是看看矢量图形应用程序如何将光标坐标列表转换为一系列曲线。例如,请参见lib2geom的bezier-utils.cpp。请注意,(i)它几乎完全基于位置而不是基于方向;和(i i)它给出了三次b_)zier曲线作为输出,而不是折线,尽管您可以使用相同的方法给出折线输出,如果这是首选的(在这种情况下,牛顿-拉斐逊步骤基本上只是一个简单的点积)。