Compressing GPS Points

Question

I have a device that records GPS data. A reading is taken every 2-10 seconds. For an activity taking 2 hours there are a lot of GPS points.

Does anyone know of an algorithm for compressing the dataset by removing redundant data points. i.e. If a series of data points are all in a straight line then only the start and end point are required.

Answer 1

There is a research paper on Compressing GPS Data on Mobile Devices.

Additionally, you can look at this CodeProject article on Writing GPS Applications. I think the problem you will have is not for straight points, but curved roads. It all depends on how precise you want your path to be.

Answer 2

i think that a vanilla zip algorithm would be the simplest and most effective for the widest variety of cases. Of course you wouldn't want to zip/unzip every few seconds but a clever use of a zip archive as a persistence mechanism would do.

Answer 3

You probably want to approximate your path x(t), y(t) with a polynomial approximation of it. Are you looking for something like this: http://www.youtube.com/watch?v=YtcZXlKbDJY ???

Answer 4

check out the Douglas Peucker Algorithm which is used to simplify a polygon. i´ve used this successfully to reduce the amount of gps waypoints when trasmitted to clients for displaying purposes.

Answer 5

You can remove redundant points by performing a very basic simplification based on calculation of slope between subsequent points.

Here is a bit of but not complete C++ code presenting possible algorithm:

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.

I hope it helps.