Compresión GPS Puntos

Question

que tienen un dispositivo que registra los datos del GPS. Se toma una lectura cada 2-10 segundos. Para una actividad que toma 2 horas hay muchos puntos de GPS.

¿Alguien sabe de un algoritmo para comprimir el conjunto de datos mediante la eliminación de puntos de datos redundantes. es decir, si una serie de puntos de datos están todos en línea recta, solo se requieren el punto inicial y el punto final.

Answer 1

echa un vistazo a Douglas Peucker Algorithm que se utiliza para simplificar un polígono. Lo he utilizado con éxito para reducir la cantidad de puntos de referencia GPS cuando se transmite a los clientes con fines de visualización.

Answer 2

Hay un trabajo de investigación en Compressing GPS Data on Mobile Devices.

Además, puede consultar este artículo de CodeProject en Writing GPS Applications. Creo que el problema que tendrás no es por puntos rectos, sino por caminos curvos. Todo depende de qué tan preciso quieras que sea tu camino.

Answer 3

Probablemente desee aproximar su trayectoria x (t), y (t) con una aproximación polinómica de la misma. ¿Estás buscando algo como esto: http://www.youtube.com/watch?v=YtcZXlKbDJY ???

Answer 4

Se puede quitar puntos redundantes mediante la realización de una simplificación muy básica basada en el cálculo de la pendiente entre los puntos siguientes.

Aquí es un poco de pero no completa la presentación de código C++ posible algoritmo:

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. 

espero que ayude.

Answer 5

El código proporcionado anteriormente tiene un par de cuestiones que podrían hacer que no sea adecuado:

• tolerancia "misma pendiente" mide la diferencia en gradiente en lugar de ángulo, de modo NNE a NNO se considera una diferencia mucho más grande de lo NE a SE (suponiendo que el eje y se ejecuta de norte a sur).

  Una forma de abordar esto sería la tolerancia para medir cómo el producto escalar de dos segmentos se compara con el producto de sus longitudes. (Podría ayudar la comprensión de recordar que el producto escalar de dos vectores es el producto de sus longitudes y el coseno del ángulo entre ellos.) Sin embargo, véase el punto siguiente.

• Considera solo error de pendiente en lugar de error de posición, por lo que un segmento ENE largo seguido de un segmento ESE largo es tan probable que se comprima en un solo segmento como una serie de segmentos cortos alternando entre ENE y ESE.

El enfoque que yo estaba pensando que sería mirar lo que hacen los gráficos de vectores aplicaciones para convertir una lista de coordenadas del cursor en una secuencia de curvas. P.ej. ver bezier-utils.cpp de lib2geom. Tenga en cuenta que (i) está casi completamente basado en la posición en lugar de en la dirección; y (ii) que da las curvas de Bézier cúbicas como salida en lugar de una línea poligonal, aunque se puede utilizar el mismo método para dar salida polilínea si eso es preferible (en cuyo caso el paso de Newton-Raphson se convierte simplemente en una producto de punto simple).