In an iPhone app, I'm trying to generate a roadbook automatically based on a real recorded route. I have figured out an algorithm to use a directions service to do it, but my algorithm needs to be able to tell if the real route follows the one calculated by the directions service for any particular segment of it.

My real route is a series of GPS positions that are pretty regularly spaced. The theoretical route returned by the directions service gives my less points and they are not spaced regularly since it basically puts a point whenever there is a significant heading change like turns and so on.

And what I would like to do is to make sure both routes are somewhat similar, because if there is a local difference, then it probably means the directions service took a shortcut and I need to recalculate a road for this segment.

I found this question that mentions the Hausdorff distance (How to calculate 'off track' error from GPS data?) and it looks like what I'm trying to do, but implementing an algorithm for it in Swift based on pure mathematical notation in the Wikipedia article is way out there for me.

I have tried to implement a naive version to calculate the maximum of the minimum distance between 2 points (see below) but it doesn't work very well because the points on both paths are not aligned so sometimes I have a big distance because a point on the real route is just too far away from the closest point on the theoretical one.

func hausdorffDistance(from:[CLLocationCoordinate2D], to:[CLLocationCoordinate2D]) -> Double {
   var maxDistance = 0.0
   for point in from {
       let pointLocation = CLLocation(latitude: point.latitude, longitude: point.longitude)
       let sortedTo = to.sorted(by: { left, right -> Bool in
           let leftLocation = CLLocation(latitude: left.latitude, longitude: left.longitude)
           let rightLocation = CLLocation(latitude: right.latitude, longitude: right.longitude)
           return leftLocation.distance(from: pointLocation) < rightLocation.distance(from: pointLocation)
       let closestPointLocation = CLLocation(latitude: sortedTo.first!.latitude, longitude: sortedTo.first!.longitude)
       let distanceToClosestPoint = pointLocation.distance(from: closestPointLocation)
       if distanceToClosestPoint > maxDistance {
           maxDistance = distanceToClosestPoint
   return maxDistance

Any idea how I could proceed?

  • So you are trying to see where the two routes differ significantly? – AnserGIS Sep 15 '16 at 18:50
  • Indeed. And if they don't differ anywhere significantly, then the theoretical route matches the real one, otherwise I have to recalculate it somehow. – Sebastien Sep 15 '16 at 19:12
  • I just found that, that looks very promising: etd.dtu.dk/thesis/268267/ep10_81.pdf – Sebastien Sep 15 '16 at 19:54
  • Rasterizing the data is rather risky I think due to the arbitrary relationship to the grid for each path. I would suggest simply buffering one route by a small distance then intersecting this with the other to find overlaps. – AnserGIS Sep 16 '16 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.