How to determine the next POI in a navigation route?

Question

I have a route (MKPolyline derived from an MKRoute retrieved from Apple's MKDirections API) and a bunch of points of interest (array of MKAnnotations) that are close to the route.

I would like to know how to select the next POI the user is going to meet following the route, in order to present it through a UI.

Two different approaches come to mind, but none of them is really adequate:

• The first one would be to mark the POIs as checked each time you get close enough to them, and simply display the first unmarked POI in the array (we'll assume that they are correctly ordered). The problem is that if for a reason or another one of the POIs is not checked, then the app will forever display it instead of displaying the actual next POI coming. This situation can arise e.g. if the user followed a slightly different route than the one suggested, that didn't come close enough to the POI to get it checked; or the user starts the navigation after the first POI; etc.

• The second one one would be to select the POI closest to the user (probably also with a marking system to avoid presenting the POI you just checked). But this would only work for routes straight enough: sometimes in mountain zones or other sinuous routes you can get closer to a point that you will actually cross later. I expect this situation to happen actually quite often.

Any idea?

Answer 1

When I had to implement a turn-by-turn in one of our apps I used what you describe as first bullet. To figure out if user diverged from original polyline I calculated distance between current position and line segments each time I read a new position. Once I detected I was NOT following the path, I re-calculated the route while showing a "Recalculating..." message for user.

This is my code

- (BOOL)isCoordinate:(CLLocationCoordinate2D)coordinate closeToPolyline:(MKPolyline *)polyline {
  CLLocationCoordinate2D polylineCoordinates[polyline.pointCount];
  [polyline getCoordinates:polylineCoordinates range:NSMakeRange(0, polyline.pointCount)];

  for (int i = 0; i < polyline.pointCount - 1; i++) {
    CLLocationCoordinate2D a = polylineCoordinates[i];
    CLLocationCoordinate2D b = polylineCoordinates[i + 1];

    double distance = [self distanceToPoint:MKMapPointForCoordinate(coordinate) fromLineSegmentBetween:MKMapPointForCoordinate(a) and:MKMapPointForCoordinate(b)];
    if (distance < 25) {
      return YES;
    }
  }

  return NO;
}

- (double)distanceToPoint:(MKMapPoint)p fromLineSegmentBetween:(MKMapPoint)l1 and:(MKMapPoint)l2 {
  double A = p.x - l1.x;
  double B = p.y - l1.y;
  double C = l2.x - l1.x;
  double D = l2.y - l1.y;

  double dot = A * C + B * D;
  double len_sq = C * C + D * D;
  double param = dot / len_sq;

  double xx, yy;

  if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
    xx = l1.x;
    yy = l1.y;
  }
  else if (param > 1) {
    xx = l2.x;
    yy = l2.y;
  }
  else {
    xx = l1.x + param * C;
    yy = l1.y + param * D;
  }

  return MKMetersBetweenMapPoints(p, MKMapPointMake(xx, yy));
}

Then I call - (BOOL)isCoordinate:(CLLocationCoordinate2D)coordinate closeToPolyline:(MKPolyline *)polyline { with coordinate being users current location and polyline being path from your MKDirections.

In my case I wouldn't allow more than 25 meters off but it might depend on your lat/lng precision.

Maybe it will help you or someone.

Answer 2

Use the following pseudometric, which I'll call route distance. Intuitively, it works like highway location markers. Assume that the route polyline does not touch or cross itself (is simple). For each point q on some segment pr of the polyline where p comes first, the location of that point in our 1D coordinate system is the Euclidean (spherical?) distance from p to q, plus the lengths of all segments that come before pr. The route distance between two such points is the absolute value of the difference of their locations in our 1D coordinate system. Extend route distance to points off of the route by treating such points as the closest point on the route (the answers to this question about computing point-to-segment distance should be helpful for computing the closest route point).

Present the closest POI to the user by route distance (check it off when this distance is sufficiently small).