What is the best way to interpolate points between coordinates in google path? Is this approach correct?

Question

Am trying to plot Polyline on Googlemap to show the position of driver/delivery boy to user like in Uber.

I use google directions API get overview Polyline and draw it on map. Now I get the driver location from our own server and in order to update the user location on map I iterate through the co-ordinates in GMSPath which I obtained by decoding the over-view Polyline as

            if let jsonArray = jsonResult["routes"].array, jsonArray.count > 0 {
                for json in jsonArray {
                    if let polyline = json["overview_polyline"]["points"].string {
                        self.possibleOverViewPolylines.append(polyline)
                    }
                }
            }
            self.currentPolyline =  self.possibleOverViewPolylines[0]
            self.path = GMSMutablePath.init(fromEncodedPath: self.currentPolyline)
            self.polyline = GMSPolyline(path: self.path)

Google usually returns multiple routes when sent alternative=true so I cache all the overview_polyline and use the first one as current over line.

Now from reading and trial-error I have figured out that there can be error in lat-long of driver captured and it might range from 5-50meters. So once I get the driver location I iterate through entire coordinates in path to find the closest point in map and snap driver to that location

           var overallDistance: CLLocationDistance = 50
           for index in 0 ..< strongSelf.path.count() {
                let coordinate = strongSelf.path.coordinate(at: UInt(index))
                let distance = location.distance(to: coordinate)
                if distance < overallDistance {
                    foundIndex = Int(index)
                    overallDistance = distance
                }
            }
            if overallDistance >= 50 {
                debugPrint("\(location)")
                evaluateAlternativeRoutes()
            }
            else {
                updatepolyline(location: strongSelf.path.coordinate(at: UInt(foundIndex)))
            }

update Polyline as

            self?.polyline.map = nil
            while strongSelf.path.coordinate(at: UInt(0)).latitude != location.latitude &&  strongSelf.path.coordinate(at: UInt(0)).longitude != location.longitude {
                self?.path.removeCoordinate(at: 0)
            }
            if strongSelf.path.coordinate(at: 0).latitude == location.latitude && strongSelf.path.coordinate(at: UInt(0)).longitude == location.longitude {
                self?.path.removeCoordinate(at: 0)
            }
            self?.polyline = GMSPolyline(path: strongSelf.path)

Finally alternative routes are evaluated as

        var overallDistance: CLLocationDistance = 50
        var foundIndex = -1

        for (polylineIndex,polyline) in strongSelf.possibleOverViewPolylines.enumerated() {
            if let path = GMSMutablePath.init(fromEncodedPath: polyline) {
                for index in 0 ..< path.count() {
                    let coordinate = path.coordinate(at: UInt(index))
                    let distance = location.distance(to: coordinate)
                    if distance < overallDistance {
                        foundIndex = polylineIndex
                        overallDistance = distance
                    }
                }
            }
        }
        if foundIndex != -1 {
             self?.path = GMSMutablePath.init(fromEncodedPath: strongSelf.possibleOverViewPolylines[foundIndex])
        }
        else {
             //make routes API call again
        }

If none of the alternative routes available matches the driver location, driver might be taking a whole different route so I make routes API call again with driver location

Why So many optimisation?

Google's routes APIs are costly and calling google routes API unnecessarily will add financial burden as well as screw up the whole user experience, hence want to make most of the calculations locally

But above code works sub-optimally :( It works but not great :|

Issues with this approach

Issue 1: Method assumes the possible error rate in drivers location is 50m max, and when I evaluate all the distance to points in path are checked against this 50, but unfortunately coordinates in google paths are not equally distributed, on a lengthy straight road, distance between 2 subsequent points in path's coordinates can be up to 200m. I tested it with

           for i in 0 ..< self.path.count() {
                if i == 0 {
                    debugPrint(self.path.coordinate(at: i))
                }
                else {
                    debugPrint("distance between \(self.path.coordinate(at: (i - 1))) and \(self.path.coordinate(at: (i))) is \(self.path.coordinate(at: (i - 1)).distance(to: self.path.coordinate(at: (i))))")
                }
            }

So logic of comparing drivers location to all points in path with 50m as cap logic fails there.

Solution I can think of

If I can interpolate the points between any two coordinates in google path with a regular interval of 50m, and raise the cap to 100m (50m distance between two points in path, 50m for error in lat-long) that should give fairly better chance for me to reduce number of API calls

What I have tried?

I tried solving it with linear interpolation using

No need to tell the result is disastrous, because equation assumes a Cartesian plane and earth is not flat :|

So finally What the heck are you asking?

1. Is it a correct approach to interpolate the points between two coordinates of google path to achieve what am trying to achieve?

2. If yes, what is the better interpolation algorithm I should be using? Clearly linear doesn't make much sense :(

Please help, thanks in advance

Answer 1

Google itself has provided various methods for interpolating within GMSGeometryUtils module. I think what you need for interpolating could be the: https://developers.google.com/maps/documentation/ios-sdk/reference/group___geometry_utils.html#gad0c5870bd9d182d22310f84a77888124

GMSGeometryInterpolate uses shortest path between 'from' and 'to' coordinate that you provide at a given fraction, and GMSPath indeed connects shortest paths between each sub-sequential coordinates you provide so it should be sufficient.