Finding out if I've deviated from given route too much (computing similarity between routes)

Question

I'm making an Android app and I'm trying to find out whether I've deviated from the given route too much (I'm getting location via GPS and the route is predefined).

I've tried calculating Fréchet distance but to no avail - it is only useful to compare two complete routes, but what if I need to compare my track (which is not yet complete) to a given track?

Answer 1

There are two functions in the PolyUtil class in the android-maps-utils library that might help.

1. PolyUtil.isLocationOnPath() - Computes whether the given point lies on or near a polyline, within a specified tolerance in meters. The polyline is composed of great circle segments if geodesic is true, and of Rhumb segments otherwise. The polyline is not closed -- the closing segment between the first point and the last point is not included.
2. PolyUtil.distanceToLine() - Computes the distance on the sphere between the point p and the line segment start to end.

You could use either of these methods to determine if a single location is within a given threshold of a polyline. If not, then the user has deviated from the route.

If you want to compare more than one point of the users path to the polyline, you can loop through the points in path, testing each of the points against the polyline.

For example:

double tolerance = 10 // meters
List<LatLng> route = getRoute(); // Your given route
List<LatLng gpsPoints = getGpsPoints(); // Multiple GPS points
boolean exceededTolerance = false;    

for (LatLng l : gpsPoints) {
    if (!PolyUtil.isLocationOnPath(l, route, true, tolerance)) {
        exceededTolerance = true;
        break;
    }
}

if (exceededTolerance) {
    Log.d(TAG, "User deviated from path");
}

Just be careful how frequently you loop through all GPS points, and be careful with how large gpsPoints and route get. For each of these operations the library is looping through the entire route, which can hurt performance with large number of points and/or frequent executions.