壓縮GPS點數

Question

我有一個記錄GPS數據的設備。每2-10秒進行一次讀數。對於需要2小時的活動，有很多GPS點。

有誰知道通過刪除冗餘數據點來壓縮數據集的算法。即如果一系列數據點全部在一條直線上，那麼只需要起點和終點。

Answer 1

查看用於簡化多邊形的Douglas Peucker Algorithm。我已成功地使用此功能來減少傳送給客戶端進行顯示時的GPS航點的數量。

Answer 2

有一篇關於Compressing GPS Data on Mobile Devices的研究論文。

此外，你可以看看這個CodeProject文章Writing GPS Applications。我認爲你的問題不是直線，而是彎曲的道路。這完全取決於你希望你的路徑有多精確。

Answer 3

你可能想用它的多項式近似來近似你的路徑x（t），y（t）。你在找這樣的東西：http://www.youtube.com/watch?v=YtcZXlKbDJY ???

Answer 4

您可以通過基於後續點之間的斜率計算進行非常基本的簡化來移除冗餘點。

這裏是有點，但不是完整的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. 

我希望它能幫助。

Answer 5

上面給出的代碼有幾個問題，可能使其不適合：

• 「相同的斜率」寬容措施梯度而非角度差，所以NNE向西北偏北被認爲比一個更大的區別NE到SE（假設y軸運行南北）。

  解決這個問題的一種方法是測量兩個區段點積與其長度乘積的比較公差。 （這可能有助於理解記住兩個向量的點積是它們長度和它們之間角度的餘弦的乘積。）但是，請參閱下一點。

• 僅考慮斜率誤差而非位置誤差，所以長ENE段跟隨長ESE段可能會被壓縮爲單個段，如ENE和ESE之間交替的一段短段。

我想到的方法是查看矢量圖形應用程序如何將光標座標列表轉換爲曲線序列。例如。請參閱lib2geom的bezier-utils.cpp。請注意：（i）它幾乎完全是基於位置的，而不是基於方向的; （ii）它將三次貝塞爾曲線作爲輸出而不是多段線，儘管如果這是首選的（在這種情況下牛頓 - 拉夫遜步驟本質上只是一個簡單的點積），您可以使用相同的方法給出折線輸出。