Counting number of laps from GPS coordinate recordings

2.9k views Asked by At

I have a GPX file with large set of points (longitude and latitude sorted by time), how can I calculate how many laps my set contains?

The GPS is recorded during circuit racing session.

The lap is number of times vehicle passes start/finish of circuit.

2

There are 2 answers

0
moinudin On BEST ANSWER

The solution is going to require some trial and error to see what works, as it depends a lot on the quality of data and how many data points you have.

If data points are taken at a high frequency, it might be good enough to do use line-line intersection tests. If the line formed by two adjacent data points intersects with the finish line on the racing track, then you can count this as a lap. This will, however, fail when the data points are too far apart. It could also fail if a car leaves the track at the finish line, unless you're careful with your solution.

A more general solution is to separate the track into two polygons: each representing half the track. Make their coverage include off-track. Then use point in polygon tests to determine which data points are in which half of the track. Then iterate through the points and take note of when the car moves from one half to the other. Every second transition should indicate a lap. This, however, will fail if the car spins out of control and oscillates between the two halves without going around the full lap.

You can work around this by enforcing a minimum number of data points between transitions. Another idea is to break the track into three polygons and make sure the car always moves "forward".

5
David Norman On

Suppose that the track is small enough that we can assume that the points lie in a flat plane, e.g., we can ignore the curvature of the earth. In this case you can convert all the points to points in a plane, e.g., P(i) = (x(i), y(i)) without a z-coordinate.

Consider the following algorithm: Find a point C = (Cx, Cy) that is somewhere in the middle of track, e.g., the centroid of all the points. The exact position doesn't matter. Then imagine that an observer is standing at point C and is always rotating to face the vehicle. You want to count how many times the observer rotates as the vehicle travels.

To do this, you need to be able to find the signed angle the observer will rotate as the vehicle travels between two adjacent points P(i) and P(i+1) in the list of points. This is the same as finding the signed angle between the vectors P(i) - C and P(i+1) - C, which can be done using the cross product. This is particularly easy, since we have 2-dimensional points. We have

P = (x(i) - Cx) * (y(i+1) - Cy) + (x(i+1) - Cx) * (y(i) - Cy)

If P is positive then the observer is rotating counter-clockwise and if it is negative the the observer is rotating clockwise. The angle the observer rotates is

theta(i, i+1) = arcsin( P / (length(x(i) - C) * length(x(i+1) - C)))

where again theta(i, i+1) is positive or negative depending on which direction the observer is rotating.

Here we are using that adjacent points are close together, so that the observer just rotates through a small angle less than pi/2 between adjacent points.

To find the total amount the observer rotates just sum all the thetas from the beginning to the ending of the path, making sure to preserve the sign of the theta in case the vehicle moves backwards for some reason. Assuming that the theta are in radians, the total number of circuits is just the sum of the thetas divided by 2 * pi.

For the truly geeky, this is just calculating the winding number of the vehicle's path around C using the definition.