平滑GPS跟蹤路線座標

Question

我有一些我記錄的座標數據。不幸的是，它們似乎並不真實。他們有時會跳過地圖。所以現在我正在尋找一些使路線看起來更真實的展平或過濾算法。

目前我唯一的過濾器是計算一秒鐘內（在公交車或汽車或步行中）行駛的最大可能的米數，並將它們與座標進行比較，將它們扔掉，這在一段時間內是不可能的。所以如果一個人一秒鐘可以走到2.5米，而且我有兩個彼此相距10米的座標，並且在兩秒鐘內記錄下來，我試圖找到它們並將它們扔掉。這有一點幫助。

這是代碼：

filters.max_possible_travel = function(data) { 
    //http://en.wikipedia.org/wiki/Preferred_walking_speed 
    //I switched to 16, as the route was made by driving with a bus... 
    var maxMetersPerSec = 16, 
     i, m, last, result = []; 

    for(i=0;i<data.length;i++) { 
     m = data[i]; 
     if (last) { 
      // seconds between current and last coord 
      var diff = (m.created.getTime() - last.created.getTime())/1000; 
      // the maximum amount of meters a person,bus,car etc can make per sec. 
      var maxDistance = diff * maxMetersPerSec; 
      // the actual distance traveled 
      var traveledDistance = google.maps.geometry.spherical.computeDistanceBetween(last.googLatLng, m.googLatLng); 

      if (traveledDistance > maxDistance) { 
       continue; 
      } else { 
       result.push(m); 
      } 
     } 
     last = m; 
    } 
    return result; 
}; 

爲了讓你的東西更容易，我創造了這個撥弄它已經實現了我的第一個過濾器，也使您能夠添加新的篩選器的能力。

http://jsfiddle.net/z4hB7/7/

一些futher的想法，我有：

• 罰球全部COORDS遠是在一個特定的半徑。這最終會刪除一些令人不安的座標，如果你只是站在幾分鐘內
• 將所有座標按n秒幀分組，並嘗試確定在該程序段中最相關的座標。可惜的是我沒有任何想法:(

如何所以我覺得這是一個真的interessting的問題，我希望你明白我說的一切。我感謝你們的幫助！

編輯 ：我發現一些關於線性最小二乘和卡爾曼濾波I'm進去，但因爲I'm絕對不是數學專家，我希望在這個任何幫助

EDIT 2個 進展:)我。實現了@geocodezip p。的DouglasPeucker算法romoted給我。算法本身並不能解決所有問題，但我目前的「max_possible_travel」組合看起來幾乎完美。如果我用第二個參數稍微玩一下，它會得到互動。請看看新的小提琴，並確保您檢查過濾器「walkfilter」和「gdouglaspeucker」。 http://jsfiddle.net/z4hB7/8/

Answer 1

你可以嘗試Douglas Peuker algorithm

的道格拉斯 - 普克算法是減少由一系列點的近似曲線點的數量的算法。

至少有one implementation for the Google Maps API v3

perl implementation

Javascript實現代碼Bill Chadwick's site：

/* Stack-based Douglas Peucker line simplification routine 
    returned is a reduced google.maps.LatLng array 
    After code by Dr. Gary J. Robinson, 
    Environmental Systems Science Centre, 
    University of Reading, Reading, UK 
*/ 

function GDouglasPeucker (source, kink) 
/* source[] Input coordinates in google.maps.LatLngs */ 
/* kink in metres, kinks above this depth kept */ 
/* kink depth is the height of the triangle abc where a-b and b-c are two consecutive line segments */ 
{ 
    var n_source, n_stack, n_dest, start, end, i, sig;  
    var dev_sqr, max_dev_sqr, band_sqr; 
    var x12, y12, d12, x13, y13, d13, x23, y23, d23; 
    var F = ((Math.PI/180.0) * 0.5); 
    var index = new Array(); /* aray of indexes of source points to include in the reduced line */ 
    var sig_start = new Array(); /* indices of start & end of working section */ 
    var sig_end = new Array(); 

    /* check for simple cases */ 

    if (source.length < 3) 
     return(source); /* one or two points */ 

    /* more complex case. initialize stack */ 

    n_source = source.length; 
    band_sqr = kink * 360.0/(2.0 * Math.PI * 6378137.0); /* Now in degrees */ 
    band_sqr *= band_sqr; 
    n_dest = 0; 
    sig_start[0] = 0; 
    sig_end[0] = n_source-1; 
    n_stack = 1; 

    /* while the stack is not empty ... */ 
    while (n_stack > 0){ 

     /* ... pop the top-most entries off the stacks */ 

     start = sig_start[n_stack-1]; 
     end = sig_end[n_stack-1]; 
     n_stack--; 

     if ((end - start) > 1){ /* any intermediate points ? */   

       /* ... yes, so find most deviant intermediate point to 
         either side of line joining start & end points */         

      x12 = (source[end].lng() - source[start].lng()); 
      y12 = (source[end].lat() - source[start].lat()); 
      if (Math.abs(x12) > 180.0) 
       x12 = 360.0 - Math.abs(x12); 
      x12 *= Math.cos(F * (source[end].lat() + source[start].lat()));/* use avg lat to reduce lng */ 
      d12 = (x12*x12) + (y12*y12); 

      for (i = start + 1, sig = start, max_dev_sqr = -1.0; i < end; i++){          

       x13 = (source[i].lng() - source[start].lng()); 
       y13 = (source[i].lat() - source[start].lat()); 
       if (Math.abs(x13) > 180.0) 
        x13 = 360.0 - Math.abs(x13); 
       x13 *= Math.cos (F * (source[i].lat() + source[start].lat())); 
       d13 = (x13*x13) + (y13*y13); 

       x23 = (source[i].lng() - source[end].lng()); 
       y23 = (source[i].lat() - source[end].lat()); 
       if (Math.abs(x23) > 180.0) 
        x23 = 360.0 - Math.abs(x23); 
       x23 *= Math.cos(F * (source[i].lat() + source[end].lat())); 
       d23 = (x23*x23) + (y23*y23); 

       if (d13 >= (d12 + d23)) 
        dev_sqr = d23; 
       else if (d23 >= (d12 + d13)) 
        dev_sqr = d13; 
       else 
        dev_sqr = (x13 * y12 - y13 * x12) * (x13 * y12 - y13 * x12)/d12;// solve triangle 

       if (dev_sqr > max_dev_sqr ){ 
        sig = i; 
        max_dev_sqr = dev_sqr; 
       } 
      } 

      if (max_dev_sqr < band_sqr){ /* is there a sig. intermediate point ? */ 
       /* ... no, so transfer current start point */ 
       index[n_dest] = start; 
       n_dest++; 
      } 
      else{ 
       /* ... yes, so push two sub-sections on stack for further processing */ 
       n_stack++; 
       sig_start[n_stack-1] = sig; 
       sig_end[n_stack-1] = end; 
       n_stack++; 
       sig_start[n_stack-1] = start; 
       sig_end[n_stack-1] = sig; 
      } 
     } 
     else{ 
       /* ... no intermediate points, so transfer current start point */ 
       index[n_dest] = start; 
       n_dest++; 
     } 
    } 

    /* transfer last point */ 
    index[n_dest] = n_source-1; 
    n_dest++; 

    /* make return array */ 
    var r = new Array(); 
    for(var i=0; i < n_dest; i++) 
     r.push(source[index[i]]); 
    return r; 

}