Есть вот такой набор точек, каждая точка представляет собой gps координату автобус
(x,y), у каждой точки есть timestamp. На построенном графике видны явные ошибки измерения
Как их можно убрать? Решение должно быть простым, так как всего координат около 100 тысяч. Интересует идея, но желательно, чтобы ее можно было без особых проблем реализовать средствами Java
Пример исходных данных:
1447037729 3054.619968 2409.828279 570d8
Первое поле - UNIX-время, второе и третье - (x,y) соответственно, четвертое - идентификатор автобуса (автобусов около 50ти) .
Исходные данные : https://drive.google.com/file/d/0B4bA9d5B_O_BcVpPUXpYTmZBUFE/view
Ответы
Ответ 1
Приведённый набор точек - это две зависимости: x(t) и y(t), и по каждой идёт импульсны
шум. К таким данным идеально подходит алгоритм медианной обработки в скользящем окне на 7-9 элементов, когда i-тый во времени элемент заменяется на медианное значение элементов с номерами (i-h,i+h) при h=3...4.
Обработку для x(t) и y(t) следует проводить независимо, после чего подменить ими исходные массивы.
Обработка эффективна при высоком уровне импульсной помехи (в тестовом примере искажен
третья часть данных). Дополнительный плюс - что сохраняется формат исходных данных. Обработка краёв ведётся на окнах меньшего размера.
Минусы обработки в скользящем окне проявляются при разворотах последовательности, поскольку выступы и провалы шириной меньше h выполаживаются.
В демо-программе представлена рекуррентная сортировка массива в окне. Для этого точки
лежащие между старым (удаляемым) и новым (добавляемым) элементами, сдвигаются в сторону старого элемента, после чего на место крайнего из возникших дубликатов записывается новый элемент. Это резко снижает вычислительные затраты.
Демо-программа (PHP):
function print_a($a, $name){
print("$name: ");
foreach($a as $item){
printf("%2d, ",$item);
}
}
function slide_median($h, $a){
$size = count($a);
$result = [];
$slide = [];
array_push($slide, reset($a));
array_push($result,$slide[0]);
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
for($i=1; $i<=$h; $i++){
array_push($slide, next($a), next($a));
sort($slide);
array_push($result, $slide[$i]);
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
}
for($i=0; $i < $size-2*$h-1; $i++){
$old = $a[$i];
$new = $a[$i+2*$h+1];
if($old < $new){
for($key = 0; $key <= 2*$h; $key++){
if($new < $slide[$key]){
break;
}
if(($old <= $slide[$key])&&($slide[$key] < $new)) $slide[$key]
$slide[$key+1];
}
$slide[$key-1] = $new;
}
if($old > $new){
for($key = 2*$h; $key >= 0; $key--){
if($new > $slide[$key]){
break;
}
if(($old >= $slide[$key])&&($slide[$key] > $new)) $slide[$key]
$slide[$key-1];
}
$slide[$key+1] = $new;
}
array_push($result, $slide[$h]);
print(" old = $old, new =$new");
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
}
for($i = $h-1; $i > 0; $i--){
$slide = array_slice($a, $size-2*$i-1, 2*$i+1);
sort($slide);
array_push($result, $slide[$i]);
print_a($slide, " Сортировка в окне");
print_a($result, "
Массив результата");
}
$slide = [$a[$size-1]];
array_push($result, $slide[0]);
print_a([end($a)], " Сортировка в окне");
print_a($a, "
Исходный массив: ");
print_a($result, "
Массив результата");
return $result;
};
$a = range(20, 40);
foreach($a as &$item){
$item += 5*mt_rand(-1,1)*(int)(mt_rand(0,199)/100);
}
print_a($a, "Исходный массив: ");
slide_median(3, $a);
Результаты (импульсный шум, амплитуда 5):
Исходный массив: : 20, 21, 22, 23, 19, 20, 21, 27, 28, 29, 30, 31, 32, 28, 29, 35, 36, 42, 43, 39, 35, Сортировка в окне: 20,
Массив результата: 20, Сортировка в окне: 20, 21, 22,
Массив результата: 20, 21, Сортировка в окне: 19, 20, 21, 22, 23,
Массив результата: 20, 21, 21, Сортировка в окне: 19, 20, 20, 21, 21, 22, 23,
Массив результата: 20, 21, 21, 21, old = 20, new =27 Сортировка в окне: 19, 20
21, 21, 22, 23, 27,
Массив результата: 20, 21, 21, 21, 21, old = 21, new =28 Сортировка в окне: 19
20, 21, 22, 23, 27, 28,
Массив результата: 20, 21, 21, 21, 21, 22, old = 22, new =29 Сортировка в окне
19, 20, 21, 23, 27, 28, 29,
Массив результата: 20, 21, 21, 21, 21, 22, 23, old = 23, new =30 Сортировка в окне: 19, 20, 21, 27, 28, 29, 30,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, old = 19, new =31 Сортировк
в окне: 20, 21, 27, 28, 29, 30, 31,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, old = 20, new =32 Сортировка в окне: 21, 27, 28, 29, 30, 31, 32,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, old = 21, new =28 Сортировка в окне: 27, 28, 28, 29, 30, 31, 32,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, old = 27, new =29 Сортировка в окне: 28, 28, 29, 29, 30, 31, 32,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, old = 28, new =35 Сортировка в окне: 28, 29, 29, 30, 31, 32, 35,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, old = 29, new =36 Сортировка в окне: 28, 29, 30, 31, 32, 35, 36,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, old = 30, new =42 Сортировка в окне: 28, 29, 31, 32, 35, 36, 42,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, old = 31, new =43 Сортировка в окне: 28, 29, 32, 35, 36, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, old = 32, new =39 Сортировка в окне: 28, 29, 35, 36, 39, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, old = 28, new =35 Сортировка в окне: 29, 35, 35, 36, 39, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, Сортировка в окне: 35, 36, 39, 42, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, Сортировка в окне: 35, 39, 43,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, 39, Сортировка в окне: 35,
Исходный массив: : 20, 21, 22, 23, 19, 20, 21, 27, 28, 29, 30, 31, 32, 28, 29, 35, 36, 42, 43, 39, 35,
Массив результата: 20, 21, 21, 21, 21, 22, 23, 27, 28, 29, 29, 29, 30, 31, 32, 35, 36, 36, 39, 39, 35,
Сравнение скользящей медианы и скользящего среднего на интенсивной импульсной помехе проведено с помощью следующей программы:
function print_a($a, $name){
print("$name: ");
foreach($a as $item){
printf("%3d, ",$item);
}
}
function slide_median($h, $a){
$size = count($a);
$result = [];
$slide = [];
array_push($slide, reset($a));
array_push($result,$slide[0]);
for($i=1; $i<=$h; $i++){
array_push($slide, next($a), next($a));
sort($slide);
array_push($result, $slide[$i]);
}
for($i=0; $i < $size-2*$h-1; $i++){
$old = $a[$i];
$new = $a[$i+2*$h+1];
if($old < $new){
for($key = 0; $key <= 2*$h; $key++){
if($new < $slide[$key]){
break;
}
if(($old <= $slide[$key])&&($slide[$key] < $new)) $slide[$key]
$slide[$key+1];
}
$slide[$key-1] = $new;
}
if($old > $new){
for($key = 2*$h; $key >= 0; $key--){
if($new > $slide[$key]){
break;
}
if(($old >= $slide[$key])&&($slide[$key] > $new)) $slide[$key]
$slide[$key-1];
}
$slide[$key+1] = $new;
}
array_push($result, $slide[$h]);
}
for($i = $h-1; $i > 0; $i--){
$slide = array_slice($a, $size-2*$i-1, 2*$i+1);
sort($slide);
array_push($result, $slide[$i]);
}
$slide = [$a[$size-1]];
array_push($result, $slide[0]);
print_a($a, "
Исходный массив ");
print_a($result, "
Массив медиан ");
return $result;
};
function slide_average($h, $a){
$size = count($a);
$b = array_merge([0], $a);
$sum = reset($a);
$result = [$sum];
for($i=1; $i<=$h; $i++){
$sum += next($a)+next($a);
$average = (int)($sum/(2*$i+1)+.5);
array_push($result, $average);
}
reset($b);
for($i=0; $i < $size-2*$h-1; $i++){
$sum += next($a) - next($b);
$average = (int)($sum/(2*$h+1)+.5);
array_push($result, $average);
}
for($i = $h-1; $i >=0; $i--){
$sum -= (next($b) + next($b));
$average = (int)($sum/(2*$i+1)+.5);
array_push($result, $average);
}
print_a($a, "
Исходный массив ");
print_a($result, "
Массив средних ");
return $result;
};
$a = range(200, 240);
foreach($a as &$item){
$item += 50*mt_rand(-1,1)*(int)(mt_rand(0,149)/100);
}
slide_median(3, $a);
slide_average(3, $a);
Результаты:
Исходный массив : 200, 201, 202, 203, 204, 155, 206, 207, 208, 209, 210, 211, 212
213, 264, 265, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 183, 234, 235, 236, 287, 238, 239, 240,
Массив медиан : 200, 201, 202, 202, 203, 204, 206, 207, 208, 209, 210, 211, 212
213, 216, 217, 218, 219, 219, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 229, 230, 231, 232, 234, 235, 236, 238, 239, 239, 240,
Исходный массив : 200, 201, 202, 203, 204, 155, 206, 207, 208, 209, 210, 211, 212
213, 264, 265, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 183, 234, 235, 236, 287, 238, 239, 240,
Массив средних : 200, 201, 202, 196, 197, 198, 199, 200, 201, 209, 210, 218, 226
227, 228, 229, 230, 231, 225, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 223, 224, 225, 226, 234, 235, 236, 244, 248, 239, 240,
Видно, что скользящая медиана лучше сглаживает интенсивные случайные выбросы данных.
Для данных из реального массива (x,y округлялись до целых):
Обработка массива x80c48
Исходный массив : 10790, 10728, 10565, 10228, 10148, 9911, 9861, 9880, 9887, 9894
9907, 9910, 9917, 9932, 9937, 9925, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457
8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6848
6823, 6857, 6868, 6894, 6902, 6903, 6904, 7114, 7067, 7047, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3053, 2977, 2967, 3248, 3257, 3202, 2954, 2834, 2594, 2574, 2611, 2730, 2766, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 815, 825,
Массив медиан : 10790, 10728, 10565, 10228, 10148, 9911, 9894, 9894, 9894, 9894
9907, 9910, 9917, 9917, 9917, 9917, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457
8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6868
6868, 6868, 6868, 6894, 6902, 6903, 6904, 6994, 6994, 6994, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3086, 3086, 3086, 3053, 2977, 2967, 2954, 2834, 2730, 2730, 2611, 2594, 2574, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 825, 825,
Исходный массив : 10790, 10728, 10565, 10228, 10148, 9911, 9861, 9880, 9887, 9894
9907, 9910, 9917, 9932, 9937, 9925, 9900, 9684, 9579, 9446, 9040, 8912, 8703, 8457
8350, 8338, 8129, 8040, 7900, 7836, 7731, 7490, 7271, 7250, 7165, 7013, 6912, 6848
6823, 6857, 6868, 6894, 6902, 6903, 6904, 7114, 7067, 7047, 6994, 6883, 6848, 6787, 6722, 6412, 6236, 6136, 6012, 5991, 5659, 5648, 5595, 5327, 5079, 5015, 4678, 4639, 4569, 4294, 4241, 4164, 4137, 3948, 3905, 3771, 3731, 3664, 3577, 3422, 3304, 3086, 3053, 2977, 2967, 3248, 3257, 3202, 2954, 2834, 2594, 2574, 2611, 2730, 2766, 2514, 2387, 2368, 2365, 2344, 2312, 2098, 1905, 1722, 1579, 1233, 1206, 963, 815, 825,
Массив средних : 10790, 10694, 10492, 10319, 10189, 10069, 9973, 9927, 9893, 9894
9904, 9912, 9917, 9918, 9886, 9839, 9772, 9644, 9498, 9323, 9117, 8927, 8749, 8561
8418, 8274, 8150, 8046, 7923, 7771, 7645, 7520, 7394, 7262, 7136, 7040, 6981, 6927
6888, 6872, 6871, 6879, 6920, 6950, 6976, 6990, 6987, 6980, 6963, 6907, 6813, 6697, 6575, 6450, 6328, 6167, 6013, 5897, 5767, 5616, 5473, 5286, 5140, 4986, 4800, 4645, 4514, 4389, 4285, 4180, 4066, 3985, 3903, 3819, 3717, 3625, 3508, 3405, 3298, 3198, 3151, 3127, 3113, 3094, 3063, 3008, 2952, 2861, 2786, 2723, 2660, 2597, 2564, 2534, 2496, 2437, 2341, 2254, 2159, 2046, 1885, 1722, 1529, 1346, 1192, 1008, 868, 825,
Обработка массива y80c48
Исходный массив : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448
6379, 6264, 5869, 5709, 5448, 5353, 5083, 5081, 5083, 5063, 5062, 5042, 5166, 5186
5172, 4916, 4925, 4982, 5009, 5025, 5007, 4993, 4991, 4986, 4976, 4968, 4964, 4962
4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3462, 3475, 3480, 3489, 3498, 3542, 3567, 3581, 3598, 3586, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3797, 3831, 3837, 3743, 3710, 3550, 3511, 3406, 3379, 3435, 3520, 3455, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279,
Массив медиан : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448
6379, 6264, 5869, 5709, 5448, 5353, 5083, 5083, 5081, 5081, 5081, 5083, 5063, 5062
5042, 5009, 5009, 5007, 4993, 4993, 4993, 4993, 4991, 4986, 4976, 4968, 4964, 4962
4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3489, 3489, 3489, 3489, 3498, 3542, 3567, 3581, 3586, 3598, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3788, 3788, 3788, 3743, 3710, 3550, 3511, 3511, 3455, 3435, 3406, 3379, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279,
Исходный массив : 7289, 7275, 7243, 7178, 7163, 7119, 7109, 6903, 6785, 6680, 6448
6379, 6264, 5869, 5709, 5448, 5353, 5083, 5081, 5083, 5063, 5062, 5042, 5166, 5186
5172, 4916, 4925, 4982, 5009, 5025, 5007, 4993, 4991, 4986, 4976, 4968, 4964, 4962
4636, 4488, 4148, 4038, 4029, 4010, 3960, 3798, 3709, 3462, 3475, 3480, 3489, 3498, 3542, 3567, 3581, 3598, 3586, 3647, 3649, 3656, 3693, 3727, 3736, 3782, 3788, 3797, 3831, 3837, 3743, 3710, 3550, 3511, 3406, 3379, 3435, 3520, 3455, 3367, 3204, 3179, 3123, 3115, 2534, 2519, 2472, 2351, 2281, 2141, 2129, 2066, 1862, 1801, 1522, 1302, 1218, 1200, 1038, 851, 812, 778, 746, 721, 621, 529, 420, 386, 279,
Массив средних : 7289, 7269, 7230, 7197, 7141, 7071, 6991, 6887, 6775, 6653, 6475
6305, 6114, 5924, 5729, 5544, 5375, 5260, 5168, 5110, 5083, 5098, 5111, 5087, 5067
5056, 5051, 5031, 5005, 4980, 4990, 4999, 4998, 4992, 4984, 4977, 4926, 4854, 4735
4601, 4466, 4330, 4187, 4067, 3956, 3858, 3778, 3699, 3625, 3559, 3522, 3502, 3519, 3536, 3552, 3574, 3596, 3612, 3630, 3651, 3671, 3699, 3719, 3740, 3765, 3785, 3788, 3784, 3751, 3711, 3655, 3591, 3533, 3502, 3465, 3439, 3395, 3363, 3326, 3280, 3140, 3006, 2878, 2756, 2628, 2488, 2347, 2280, 2186, 2090, 1972, 1832, 1700, 1567, 1420, 1276, 1135, 1028, 949, 878, 795, 723, 661, 600, 529, 447, 362, 279,
По сравнению с алгоритмом скользящего среднего, скользящая медиана намного аккуратнее обращается с данными.
Есть перевод статьи на английский язык.
Ответ 2
Для обработки зашумленных данных стоит подумать о фильтре Калмана.
Так как у вас тут автобус - сразу вопрос - этот автобус движется по заранее известному маршруту?
Ответ 3
Если нужно сгладить график - есть алгоритмы фильтрации и аппроксимации. Во первы
это метод скользящего среднего, которым можно немного подкорректировать входные данны
для их большей гладкости. Далее, можно разбить график на небольшие куски и аппроксимировать их, скажем, параболами с помощью метода наименьших квадратов (о его идее я рассказывал здесь). Ещё можно использовать Фурье преобразование входных данных, убрать оттуда высокие частоты (что и будет шумом), после чего использовать обратное преобразование.
Ответ 4
На графике видны как явные, так и неявные ошибки. Имеются повороты, плюс на каждо
повороте есть сомнительные точки, по которым сразу и не скажешь, ошибка это, или автобус такой загогулиной ехал. То есть простые варианты типа отбрасывания точек для "невероятных" перемещений на участках поворотов вряд ли помогут.
Могу предложить использовать сглаживание методом локальной регрессии, затем построит
доверительный интервал (вернее, доверительную область), но не для регрессии, а для значений (см. здесь), и отбрасывать точки за его пределами. 95% интервал может оказаться очень широким, возможно, потребуется взять 90%, 80% и т.д.
Что касается 100 тыс. наблюдений, то никакой бигдаты тут нет, на вполне заурядном компе можно пробовать самые разные методы.
Ответ 5
Предлагаю два критерия отбрасывания плохих точек.
Зигзаги - два поворота в разные стороны больше 90 градусов подряд. Это на самом дел
возможно при откате и пробуксовывании, но если это происходит на одной линии, то н
повредит внешний вид графика, а если со смещением, то скорее всего это результат ошибки. Однако при редких точках возможно, что автобус действительно так ехал, здесь критерий мне не ясен.
Ещё часто наблюдается ошибочный дрейф во время стоянки. При обнаружении зигзага н
маленькой скорости вместо удаления можно скопировать соседнюю точку. Возможно так же считать критерием стоянки постоянную очень маленькую скорость длительное время, но это может быть и движение в пробке.
Слишком большое нормальное ускорение с чередованием знака (автобус не дрова везёт) - тут предлагаю порог 0,4 м/c^2 относительно предыдущего значения.
Программа
#include
#include
#include
#define ZZMAXLEN 40
#define MAXDA 0.4
int main(int argn, char **argv) {
double x[4], y[4]; // кольцевые буферы данных
int t[4]={0,0,0,0}, n=0, h=0;
char id[9];
if(argn!=2) {
fprintf(stderr, "Usage:\n\t%s bus-ID\n", argv[0]);
return 1;
}
while(scanf("%d %lf %lf %8s", t+h, x+h, y+h, id)==4) {
if(strcmp(id, argv[1])) continue;
h= h+1 & 3;
if(++n < 4) continue;
int dt1= t[h+1&3]-t[h];
int dt2= t[h+2&3]-t[h+1&3];
int dt3= t[h+3&3]-t[h+2&3];
double dx1= x[h+1&3]-x[h];
double dy1= y[h+1&3]-y[h];
double dx2= x[h+2&3]-x[h+1&3];
double dy2= y[h+2&3]-y[h+1&3];
double dx3= x[h+3&3]-x[h+2&3];
double dy3= y[h+3&3]-y[h+2&3];
int filter=0;
if(dx1*dx2+dy1*dy2 < 0 && dx2*dx3+dy2*dy3 < 0 && dx1*dx3+dy1*dy3 > 0 && dx2*dx2+dy2*dy2 < ZZMAXLEN*ZZMAXLEN) {
// разворот на угол более 90 градусов 2 раза подряд
if((dx2*dx2+dy2*dy2)>0 && (dx2*dx2+dy2*dy2)/(dt2*dt2)<0.05) {
fprintf(stderr, "D %d\n", n-1); // дрейф
filter=2;
} else {
fprintf(stderr, "Z %d\n", n-2);
filter=1;
}
}
// скорости
dx1/=dt1;
dx2/=dt2;
dx3/=dt3;
dy1/=dt1;
dy2/=dt2;
dy3/=dt3;
double vx12= (dx1+dx2)/(dt1+dt2);
double vy12= (dy1+dy2)/(dt1+dt2);
double vx23= (dx2+dx3)/(dt2+dt3);
double vy23= (dy2+dy3)/(dt2+dt3);
double v12= sqrt(vx12*vx12+vy12*vy12);
double v23= sqrt(vx23*vx23+vy23*vy23);
// ускорения
double ax1= (dx2-dx1)*2/(dt1+dt2);
double ay1= (dy2-dy1)*2/(dt1+dt2);
double ax2= (dx3-dx2)*2/(dt2+dt3);
double ay2= (dy3-dy2)*2/(dt2+dt3);
// нормальные ускорения
double an1= v12? (vx12*ay1-vy12*ax1)/v12 : 0;
double an2= v23? (vx23*ay2-vy23*ax2)/v23 : 0;
if(fabs(an1-an2) > MAXDA && an1*an2<0) {
fprintf(stderr, "N %d %f %f\n", n-2, an1, an2); // два резких поворота
filter=1;
}
if(filter) {
// определяем какую точку удалить
if(fabs(an1) > fabs(an2))
if(filter==2) {
x[h+1&3]=x[h+2&3];
y[h+1&3]=y[h+2&3];
} else {
x[h+1&3]=x[h+2&3];
y[h+1&3]=y[h+2&3];
t[h+1&3]=t[h+2&3];
}
else
if(filter==2) {
x[h+2&3]=x[h+1&3];
y[h+2&3]=y[h+1&3];
} else {
x[h+2&3]=x[h+1&3];
y[h+2&3]=y[h+1&3];
t[h+2&3]=t[h+1&3];
}
}
// тут можно пропустить точки с поворяющимся временем, но я оставил для построения графиков
printf("%d\t%lf\t%lf\t%s\n", t[h], x[h], y[h], id);
}
t[h]=0;
do { h=h-1&3; } while (t[h-1&3]0);
do {
printf("%d\t%lf\t%lf\t%s\n", t[h], x[h], y[h], argv[1]);
h= h+1&3;
} while (t[h-1&3]0);
return 0;
}
Результаты работы получаем на стандартном выводе, а в стандартном выводе ошибок список удалённых точек и причина (N - нормальное ускорение, Z - зигзаг, D - зигзаг в дрейфе):
$ ./a.out 80c48 < data.txt > 80c48.txt
N 154 -0.163844 0.490944
D 249
D 252
Z 303
Z 444
Z 567
N 631 0.283293 -0.136238
Z 636
N 727 0.321036 -0.103197
N 984 -0.366378 0.309231
Z 991
N 1082 0.414078 -0.203378
N 1199 -0.020139 0.572870
D 1213
Z 1414
D 1507
D 1515
D 1517
D 1538
И иллюстрация удаления точки 154:
Видимо исходные данные уже обработаны каким-то фильтром, так как отсчёты времен
неравномерны.
Данный метод вырезает одиночные ошибки, но данные GPS часто могут накапливать ошибк
(и фильтр Калмана тоже) , и для борьбы с этим можно предложить притягивать слишком отклонённые точки к сетке дорог, которую можно получить усредняя много траекторий.
