android - How can I extrapolate farther along a road?

Question

Given realtime location data of a moving device over a short period of time, how can I get a lat/long pair further along this road, say, 2 miles, or even better, 5 minutes worth of driving?

I see that I can use Google's Roads API to snap to a road given a lat/long pair https://developers.google.com/maps/documentation/roads/snap, but that only gets me part way there.

This will be in an Android app.

Answer 1

Given a route represented as a List<LatLng>, this function calculates the point on the route that results from travelling distance meters from origin on that route (using the Google Maps API Utility Library to do some calculations):

private LatLng extrapolate(List<LatLng> path, LatLng origin, float distance) {
    LatLng extrapolated = null;

    if (!PolyUtil.isLocationOnPath(origin, path, false, 1)) { // If the location is not on path non geodesic, 1 meter tolerance
        return null;
    }

    float accDistance = 0f;
    boolean foundStart = false;
    List<LatLng> segment = new ArrayList<>();

    for (int i = 0; i < path.size() - 1; i++) {
        LatLng segmentStart = path.get(i);
        LatLng segmentEnd = path.get(i + 1);

        segment.clear();
        segment.add(segmentStart);
        segment.add(segmentEnd);

        double currentDistance = 0d;

        if (!foundStart) {
            if (PolyUtil.isLocationOnPath(origin, segment, false, 1)) {
                foundStart = true;

                currentDistance = SphericalUtil.computeDistanceBetween(origin, segmentEnd);

                if (currentDistance > distance) {
                    double heading = SphericalUtil.computeHeading(origin, segmentEnd);
                    extrapolated = SphericalUtil.computeOffset(origin, distance - accDistance, heading);
                    break;
                }
            }
        } else {
            currentDistance = SphericalUtil.computeDistanceBetween(segmentStart, segmentEnd);

            if (currentDistance + accDistance > distance) {
                double heading = SphericalUtil.computeHeading(segmentStart, segmentEnd);
                extrapolated = SphericalUtil.computeOffset(segmentStart, distance - accDistance, heading);
                break;
            }
        }

        accDistance += currentDistance;
    }

    return extrapolated;
}

Here are some tests:

List<LatLng> route = new ArrayList<>();
route.add(new LatLng(40, 4));
route.add(new LatLng(40.1, 4));
route.add(new LatLng(40.1, 4.1));
route.add(new LatLng(40.2, 4.1));
route.add(new LatLng(40.2, 4.2));
route.add(new LatLng(40.3, 4.2));
route.add(new LatLng(40.3, 4.3));

LatLng origin;
LatLng extrapolated;

origin = new LatLng(40.1, 4.05);
extrapolated = extrapolate(route, origin, 30000);
Log.e("Extrapolated1", "" + extrapolated); //  lat/lng: (40.25517043951189,4.2)

origin = new LatLng(40.05, 4);
extrapolated = extrapolate(route, origin, 100);
Log.e("Extrapolated2", "" + extrapolated); //  lat/lng: (40.05089932033549,4.0)

origin = new LatLng(40.05, 4);
extrapolated = extrapolate(route, origin, 50000);
Log.e("Extrapolated3", "" + extrapolated); //  lat/lng: (40.300010207449226,4.261348349980259)

origin = new LatLng(40.05, 4);
extrapolated = extrapolate(route, origin, 100000);
Log.e("Extrapolated4", "" + extrapolated); //  null (result out of the route)