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

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?

• can you truncate the route you are following at the point you should be at as you go along? – Ian Turton Aug 17 '16 at 15:28
• I'm not sure. The routes are polylines of latitude, longitude and time. And thay can differ a lot at any moment. My goal is to inform the user that he deviated too much. What algorithm would you suggest to truncate the reference route? – FelisManulus Aug 17 '16 at 15:42

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.