平滑GPS跟踪的路线坐标 [英] Smoothing GPS tracked route-coordinates
问题描述
我有一些我记录的坐标数据。不幸的是，它们似乎并不真实。他们有时会跳过地图。所以现在我正在寻找一些平坦化或过滤算法，使路线看起来更加逼真。
目前我唯一的过滤器是计算最大可能的米数第二步（在公共汽车或汽车或步行中），并将它们与坐标进行比较，将其扔掉，这在一段时间内是不可能的。所以如果一个人一秒钟可以走到2.5米，而且我有两个彼此相距10米的坐标，并且在两秒钟内记录下来，我试图找到它们并将它们扔掉。这有一点帮助。
这是代码：
filters.max_possible_travel = function数据）{
//http：//en.wikipedia.org/wiki/Preferred_walking_speed
//我换成了16，因为这条路线是通过公共汽车行驶的...
var maxMetersPerSec = 16，
i，m，last，result = [];
for（i = 0; i< data.length; i ++）{
m = data [i];
if（last）{
//当前与最后一个coord之间的秒数
var diff =（m.created.getTime（） - last.created.getTime（））/ 1000;
//一个人，公共汽车，汽车等每秒能够达到的最大数量。
var maxDistance = diff * maxMetersPerSec;
//实际行驶距离
var traveledDistance = google.maps.geometry.spherical.computeDistanceBetween（last.googLatLng，m.googLatLng）;
if（traveledDistance> maxDistance）{
continue;
} else {
result.push（m）;
}
}
last = m;
}
返回结果;
};
为了让您更轻松，我创建了一个已经实现了我的第一个过滤器的小提琴，并且还为您提供了添加新过滤器的能力。
我有一些进一步的想法：
- 全部抛出在特定半径内的线索。这最终会删除一些令人不安的坐标，如果你只是站着几分钟，那么
- 会将所有坐标以n秒的帧为单位进行分组，并尝试确定该程序段中最相关的坐标。不幸的是，我没有任何想法：（b / b）
$ b因此，我认为这是一个非常有意思的问题，我希望你能理解我所说的一切关于。我感谢你们的帮助！
编辑：我找到了线性最小二乘和卡尔曼滤波器。 ，但因为我绝对不是数学专家，所以我非常感谢这方面的帮助。
编辑2
进度： ）我实现了@geocodezip提升给我的DouglasPeucker算法。算法本身并不能解决所有问题，但我目前的max_possible_travel组合看起来几乎完美。如果我用第二个参数稍微玩一下，它会得到互动。请看看新的小提琴，并确保您检查过滤器walkfilter和gdouglaspeucker。
http://jsfiddle.net/z4hB7/8/解决方案您可以尝试 Douglas Peuker算法
Ramer-Douglas-Peucker算法是减少曲线中由一系列点数近似的点数。
Javascript实现代码来自 Bill Chadwick的网站：
/ *基于堆栈的Douglas Peucker线条简化ro utine
返回的是一个简化的google.maps.LatLng数组
经过Dr. Gary J. Robinson的代码，
环境系统科学中心，
University of Reading，Reading，£ b $ b * /
函数GDouglasPeucker（source，kink）
/ * source []在google.maps.LatLngs中输入坐标* /
/ *扭曲，单位为米，扭结* /
/ *扭结深度是三角形abc的高度，其中ab和bc是两个连续的线段* /
{
var n_source，n_stack，n_dest，start，结束，我，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（）; / *源点索引包含在简化的行中* /
var sig_start = new Array（）; / *开始和结束的指数工作结束部分* /
var sig_end = new Array（）;
$ b $ *检查简单案例* /
if（source.length< 3）
return（source）; / *一点或两点* /
/ *更复杂的情况。初始化堆栈* /
n_source = source.length;
band_sqr = kink * 360.0 /（2.0 * Math.PI * 6378137.0）; / *现在度数* /
band_sqr * = band_sqr;
n_dest = 0;
sig_start [0] = 0;
sig_end [0] = n_source-1;
n_stack = 1;
/ *堆栈不为空... * /
while（n_stack> 0）{
/ * ...弹出top-大多数条目都不在堆栈中* /
start = sig_start [n_stack-1];
end = sig_end [n_stack-1];
n_stack--;如果（（结束 - 开始）> 1）{/ *任何中间点？
* /
/ * ...是的，所以找到最偏离的中间点为
，结束点* /
x12 =（source [end] .lng（） - source [start] .lng（））;
y12 =（source [end] .lat（） - source [start] .lat（））; （Math.abs（x12）> 180.0）
x12 = 360.0 - Math.abs（x12）;
if
x12 * = Math.cos（F *（source [end] .lat（）+ source [start] .lat（）））; / *使用avg lat减少lng * /
d12 = （x12 * x12）+（y12 * y12）; （i = start + 1，sig = start，max_dev_sqr = -1.0; i
x13 =（source [i] .lng （） - source [start] .lng（））;
y13 =（source [i] .lat（） - source [start] .lat（））; （Math.abs（x13）> 180.0）
x13 = 360.0 - Math.abs（x13）;
if
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）;如果（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; //解决三角形
if（dev_sqr> max_dev_sqr）{
sig = i;
max_dev_sqr = dev_sqr;
}
}
if（max_dev_sqr< band_sqr）{/ *是否有sig。中间点？ * /
/ * ...不，所以传送当前起始点* /
索引[n_dest] =开始;
n_dest ++;
}
else {
/ * ...是的，所以在栈上推入两个子部分以作进一步处理* /
n_stack ++;
sig_start [n_stack-1] = sig;
sig_end [n_stack-1] = end;
n_stack ++;
sig_start [n_stack-1] =开始;
sig_end [n_stack-1] = sig;
其他{
/ * ...没有中间点，所以传输当前起始点* /
index [n_dest] = start;
n_dest ++;
}
}
/ *传输最后一点* /
index [n_dest] = n_source-1;
n_dest ++;
/ *返回数组* /
var r = new Array（）;
for（var i = 0; i< n_dest; i ++）
r.push（source [index [i]]）;
return r;
}
I have some data of coordinates that I recorded. Unfortunatelly they seem to be not realy good. They jump sometimes over the map. So now I´m searching for some flattening or filtering algorithm that would make the route look more realistic.
Currently my only filter is to calculate the max possible meters travelled in a second (in bus or car or walking) and compare them with the coordinates, throwing those away, that are just not possible within a timeframe. So if a person can walk up to 2.5 meters in a second, and I have two coords that are 10 meters away from each other and they were recorded within two seconds, I try to find them and throw them away. This helps a little bit.
This is the code:
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; };To make things easier for you, I created this fiddle that already implements my first filter and also gives you the ability to add a new filter.
Some futher ideas I have:
- throw all coords away that are in a specific radius. This eventually would remove some disturbing coords, if you just stand around for a few minutes
- group all coords by n seconds frames and try to determine the most relevant in this block. Unfortunatelly I dont have any idea how :(
So I think this is a realy interessting issue, I hope you understand everything I was talking about. I thank You guys for any help!
Edit: I found something about Linear least squares and Kalman Filter. I´m into it, though because I´m absolutely not the math expert, I would appreciate any help in this.
EDIT 2 Progress :) I implemented the DouglasPeucker algorithm which @geocodezip promoted to me. The algorithm alone does not fix it all, but the combination of my current "max_possible_travel" it looks almost perfect. If I play a little bit with the second param it will get interessting. Please look at the new fiddle and make sure you check both the filters "walkfilter" and "gdouglaspeucker". http://jsfiddle.net/z4hB7/8/
解决方案You can try the Douglas Peuker algorithm
The Ramer–Douglas–Peucker algorithm is an algorithm for reducing the number of points in a curve that is approximated by a series of points.
There is at least one implementation for the Google Maps API v3
Javascript implementation code from 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; }这篇关于平滑GPS跟踪的路线坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
