У меня есть устройство, которое записывает данные GPS. Показания снимаются каждые 2-10 секунд. Для мероприятия, занимающего 2 часа, есть много точек GPS.
Кто-нибудь знает алгоритм сжатия набора данных путем удаления избыточных точек данных. т. е. если ряд точек данных находится на прямой линии, то требуются только начальная и конечная точки.
ознакомьтесь с алгоритмом Douglas Peucker, который используется упростить многоугольник. Я успешно использовал это, чтобы уменьшить количество путевых точек GPS при передаче клиентам для целей отображения.
Существует исследовательская работа по сжатию данных GPS на мобильных устройствах.
Кроме того, вы можете ознакомиться с этой статьей CodeProject о Написание приложений GPS. Я думаю, что проблема у вас будет не с прямыми точками, а с кривыми дорогами. Все зависит от того, насколько точным вы хотите, чтобы ваш путь был.
Вы, вероятно, хотите аппроксимировать свой путь 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.
Я надеюсь, что это помогает.
Приведенный выше код имеет пару проблем, которые могут сделать его непригодным:
Допуск «одинакового уклона» измеряет разницу в градиенте, а не в угле, поэтому ССВ и ССЗ считается гораздо большей разницей, чем ССВ и ЮВ (при условии, что ось Y проходит с севера на юг).
Один из способов решить эту проблему — использовать допуск для измерения того, как скалярное произведение двух сегментов сравнивается с произведением их длин. (Может помочь понять, что скалярное произведение двух векторов — это произведение их длин и косинуса угла между ними.) Однако см. следующий пункт.
Учитывается только ошибка наклона, а не ошибка положения, поэтому длинный сегмент ENE, за которым следует длинный сегмент ESE, с такой же вероятностью будет сжат в один сегмент, как и строка коротких сегментов, чередующихся между ENE и ESE.
Подход, о котором я думал, заключался в том, чтобы посмотреть, что делают приложения векторной графики для преобразования списка координат курсора в последовательность кривых. Например. см. bezier-utils.cpp от lib2geom. Обратите внимание, что (i) это почти полностью основано на позиции, а не на направлении; и (ii) он дает кубические кривые Безье в качестве выходных данных, а не полилинию, хотя вы можете использовать тот же подход, чтобы получить полилинейный вывод, если это предпочтительнее (в этом случае шаг Ньютона-Рафсона становится просто простым скалярным произведением).
