Find out if a GPS waypoint has been passed

Question

Think of several runners on a marathon. The athletes are all wearing GPS devices. The track itself has no sensors, and I need to know when each athlete crosses a predetermined set of GPS coordinates. However, each athlete may cross the waypoint at a slightly different lat/long, since the track/road might be wide enough that different parts of the track/road are used.

What is the best way to determine whether an athlete has passed a waypoint?

I'm using Python, and am open to using an external library. I'm working with pre-processed GPS data, so I have only the latitude and longitude at each time point (and a few other bits and pieces like speed and distance travelled).

Answer 1

IMHO there are few ways of solving your problem. First one which came to my mind is this:

from shapely.geometry import LineString

line1 = LineString([(i, i) for i in range(5)])
line2 = zip(range(5)[::-1], range(5))

if line1.crosses(line2):
    print 'yeah!'

add a loop and iterate every waypoint-line

Other possible options:

• simple math calculation using intersection of two strait lines - high school stuff
• import your data into postgres with postgis and use postgis function eg ST_Crosses (if postgres is to heavy for you I would give SpatialLite-sqlite a try)
• pyshp, shapely, gdal/geos, geodjango, geoalchemy
• combine some of the above and write a bit more fancy algo like creating a buffer around one line/point and check if it "ST_Contains" GPS position also checking if any later positions are off buffer zone(?)

Answer 2

You may try this: The waypoint is the point at which two track (line) segments meet (black lines in the picture). Draw a line orthogonal to one of the line segments through the waypoint for each of the two line segments meeting in the waypoint (the red and blue line through the way point in the picture). The runner is considered to be near the waypoint when it enters the area marked red in the picture (assuming the runner comes from the right). After some time the runner may enter the area marked blue in the picture - when this happens, the runner has passed the waypoint.

If the runner never shows up in the area marked blue the runner deviated from the track, the waypoint has not been passed.