Сжатие точек 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

код, указанный выше, имеет несколько проблем, которые могли бы сделать его непригодным:

• «же склон» толерантность измеряет разницу в градиенте, а не под углом, так что нне к NNW считается гораздо больше разницы, чем NE до SE (при условии, что ось y работает на север-юг).

  Одним из способов решения этой проблемы является толерантность к измерению того, как точечный продукт двух сегментов сравнивается с продуктом их длины. (Это может помочь понять, что точечный продукт двух векторов является произведением их длин и косинуса угла между ними.) Однако см. Следующий пункт.

• Рассматривается только ошибка склона, а не погрешность положения, поэтому длинный сегмент ENE, за которым следует длинный сегмент ESE, также сжимается до одного сегмента как цепочка коротких сегментов, чередующихся между ENE и ESE.

Подход, о котором я думал, будет состоять в том, чтобы посмотреть, что делают векторные графические приложения, чтобы преобразовать список координат курсора в последовательность кривых. Например. см. статью bezier-utils.cpp от lib2geom. Обратите внимание, что (i) он почти полностью основан на позиции, а не основан на указаниях; и (ii) он дает кривые кубического безрезультата как выходную, а не полилинию, хотя вы можете использовать тот же подход, чтобы дать выход полилинии, если это предпочтительнее (в этом случае шаг Ньютона-Рафсона становится по существу просто простым точечным продуктом).