GPS Data time to distance base transformation

I am developing an application that logs a GPS trace over time.

After the trace is complete, I need to convert the time based data to distance based data, that is to say, where the original trace had a lon/lat record every second, I need to convert that into having a lon/lat record every 20 meters.

Smoothing the original data seems to be a well understood problem and I suppose I need something like a开发者_运维知识库 smoothing algorithm, but I'm struggling to think how to convert from a time based data set to a distance based data set.

This is an excellent question and what makes it so interesting is the data points should be assumed random. Which means you cannot expect a beginning to end data graph that represents a well behaved polynomial (like SINE or COS wave). So you will have to work in small increments such that values on your x-axis (so to speak) do not oscillate meaning Xn cannot be less than Xn-1. The next consideration would be the case of overlap or near overlap of data points. Imagine I’m recording my GPS coordinates and we have stopped to chat or rest and I walk randomly within a twenty five foot circle for the next five minutes. So the question would be how to ignore this type of “data noise”?

For simplicity let’s consider linear calculations where there is no approximation between two points; it’s a straight line. This will probably be more than sufficient for your calculations. Now given the comment above regarding random data points, you will want to traverse your data from your start point to the end point sequentially. Sequential termination occurs when you exceed the last data point or you have exceeded the overall distance to produce coordinates (like a subset). Let’s assume your plot precision is X. This would be your 20 meters. As you traverse there will be three conditions:

1. The distance between the two points is greater than your precision. Therefore save the start point plus the precision X. This will also become your new start point.
2. The distance between the two points is equal to your precision. Therefore save the start point plus the precision X (or save end point). This will also become your new start point.
3. The distance between the two points is less than your precision. Therefore precision is adjusted to precision minus end point. The end point will become your new start point.

Here is pseudo-code that might help get you started. Note, point y minus point x = distance between. And, point x plus value = new point on line between poing x and point y at distance value.

recordedPoints = received from trace;
newPlotPoints = emplty list of coordinates;
plotPrecision = 20

immedPrecision = plotPrecision;
startPoint = recordedPoints[0];
for(int i = 1; i < recordedPoints.Length – 1; i++)
{
    Delta = recordedPoints[i] – startPoint;

    if (immedPrecision < Delta)
    {
        newPlotPoints.Add(startPoint + immedPrecision);
        startPoint = startPoint + immedPrecision;
        immedPrecsion = plotPrecsion;
        i--;
    }

    else if (immedPrecision = Delta)
    {       
        newPlotPoints.Add(startPoint + immedPrecision);
        startPoint = startPoint + immediatePrecision;
        immedPrecision = plotPrecision;
    }

    else if (immedPrecision > Delta)
    {
        // Store last data point regardless
        if (i == recordedPoints.Length - 1)
        {
            newPlotPoints.Add(startPoint + Delta)
        }

        startPoint = recordedPoints[i];
        immedPrecision = Delta - immedPrecision;
    }
}

Previously I mentioned "data noise". You can wrap the "if" and "else if's" in another "if" which detemines scrubs this factor. The easiest way is to ignore a data point if it has not moved a given distance. Keep in mind this magic number must be small enough such that sequentially recorded data points which are ignored don't sum to something large and valuable. So putting a limit on ignored data points might be a benefit.

With all this said, there are many ways to accurately perform this operation. One suggestion to take this subject to the next level is Interpolation. For .NET there is a open source library at http://www.mathdotnet.com. You can use their Numberics library which contains Interpolation at http://numerics.mathdotnet.com/interpolation/. If you choose such a route your next major hurdle will be deciding the appropriate Interpolation technique. If you are not a math guru here is a bit of information to get you started http://en.wikipedia.org/wiki/Interpolation. Frankly, Polynomial Interpolation using two adjacent points would be more than sufficient for your approximations provided you consider the idea of Xn is not < Xn-1 otherwise your approximation will be skewed.

The last item to note, these calculations are two-dimensional and do consider altitude (Azimuth) or the curvature of the earth. Here is some additional information in that regard: Calculate distance between two latitude-longitude points? (Haversine formula).

Never the less, hopefully this will point you in the correct direction. With no doubt this is not a trivial problem therefore keeping the data point range as small as possible while still being accurate will be to your benefit.

One other consideration might be to approximate using actual data points using the precision to disregard excessive data. Therefore you are not essentially saving two lists of coordinates.

Cheers, Jeff