Geospatial Routing

Question

I'm a logistics programmer, and I've been asked to figure out if a GPS point is "off route" where the route consists of a number of geospatial points (latitude,longitude).

What is the best algorithm for determining if a point is near the route? I will be using C# and SQL Server, but really that doesn't matter a whole lot if I know what algorithm to use.

I've considered

1. Finding the two nearest points and determining if the area of the triangle is above a specific limit.
2. Using vectors for all pairs of points and then checking to see if any of them are "similar" to the vector defined by the GPS point and the point I determine to be "next" in the route.

I don't have a mathematics degree, but I can probably handle about anything given the correct terms and a search engine.

I will have to make at least 4000 calculations an hour so using a mapping solution is probably not acceptable due to volume.

Answer 1

I will have to make at least 4000 calculations an hour so using a mapping solution is probably not acceptable due to volume.

In fact, this is a PERFECT example where a mapping solution would be beneficial. Not your traditional "look at a map and determine distance", but rather "let the database determine what is the closest route to your GPS point.

Since you say you are not opposed to using a different database, you could consider:

1. SQL Server 2008, which has Spatial Database Engine functions, or
2. PostgreSQL with the open-source PostGIS (spatial) extension, which has significantly more spatial analysis functions that MS SQL 2008.

Take a look at the PostGIS ST_Distance function or MS SQL Server 2008 STDistance function. This is a good blog entry that describes the benefits of SQL2005 vs SQL2008.

You might also consider reading (or asking more detailed mapping) posts over at gis.stackexchange. That whole group is dedicated to spatial analysis. Some good discussions for you to take a look at would be

• Find closest lat long to an input lat long (SQL Server 2008)
• PostGIS : nearest point on a linestring to a given point

Answer 2

Google for "Along-track distance" and you should find the formulas commonly used in aviation. Alternatively, the cross-track distance could also be what you want.

Answer 3

How about the following...

Iterate through all line segments

lineSegSlope = Calculate slope for each line segment

draw a pretend line from the point in question that intersects the current line segment. this is done by inverting the lineSegSlope and multiplying by -1 to get the new slope, then substitute your target point X, Y, and new slope into y-y1 = b * (x-x1). Your X goes into x1, your Y goes into Y1, and your newSlope goes into B.

make an equation for the line segment.

if you draw the two lines on top of each other, they should make an X where each corner is 90 degrees.

calculate the intersection of the two lines

calculate the distance between the intersection point and your new point. If it's greater than some tolerable value, the new point is too far.

this looks like a mess, but hopefully it should work.