CODEWITHSUNDEEP
algorithmgpsgeospatial
BENBUN Coder
BENBUN Coder

Reputation: 4881

Compressing GPS Points

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.

Upvotes: 6

Views: 4482

Answers (5)

user195488
user195488

Reputation:

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.

Upvotes: 1

Peter Moulder
Peter Moulder

Reputation: 1

The code given above has a couple of issues that might make it unsuitable:

  • "same slope" tolerance measures difference in gradient rather than angle, so NNE to NNW is considered a much bigger difference than NE to SE (assuming y axis runs North-South).

    One way of addressing this would be for the tolerance to measure how the dot product of two segments compares with the product of their lengths. (It might help understanding to remember that dot product of two vectors is the product of their lengths and the cosine of the angle between them.) However, see next point.

  • Considers only slope error rather than position error, so a long ENE segment followed by long ESE segment is just as likely to be compressed to a single segment as a string of short segments alternating between ENE and ESE.

The approach that I was thinking of would be to look at what vector graphics applications do to convert a list of cursor coordinates into a sequence of curves. E.g. see lib2geom's bezier-utils.cpp. Note that (i) it's almost entirely position-based rather than direction-based; and (ii) it gives cubic bézier curves as output rather than a polyline, though you could use the same approach to give polyline output if that's preferred (in which case the Newton-Raphson step becomes essentially just a simple dot product).

Upvotes: 0

Joachim Kerschbaumer
Joachim Kerschbaumer

Reputation: 9871

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.

Upvotes: 8

mloskot
mloskot

Reputation: 38912

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.

Upvotes: 1

Hamish Grubijan
Hamish Grubijan

Reputation: 10820

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 ???

Upvotes: 1

Related Questions