Check user is following the route or not (iphone)

Question

i am making an navigation based application. In this application i am drawing a route from points selected by the user. I have requirement of recalculating route if user is not following the route.

for Calculating the route i have used Google direction API. and for drawing the route i have used this code

- (void) drawRoute:(NSArray *) path
{
    NSInteger numberOfSteps = path.count;
    [self.objMapView removeOverlays: self.objMapView.overlays];

    CLLocationCoordinate2D coordinates[numberOfSteps];
    for (NSInteger index = 0; index < numberOfSteps; index++)
    {
        CLLocation *location = [path objectAtIndex:index];
        CLLocationCoordinate2D coordinate = location.coordinate;

        coordinates[index] = coordinate;
    }

    for( id <MKOverlay> ovr in [self.objMapView overlays])
    {
        MKPolylineView *polylineView = [[MKPolylineView alloc] initWithPolyline:ovr];


        if (polylineView.tag == 22)
        {
            [self.objMapView removeOverlay:ovr];
        }
        [polylineView release];
    }

    MKPolyline *polyLine = [MKPolyline polylineWithCoordinates:coordinates count:numberOfSteps];
    [self.objMapView addOverlay:polyLine];


}

Till now every thing is okey.

Now, i want a notification if user is out of route (more than 100 meters).and i can get the notification also

PROBLEM:~ if road is straight (more than 100mt) then i cant get points on the road. To explain the problem i have attached the image...

In this image suppose black line is my path (polyline) and red circles are the points i got form google apis. but in the straight path shown as blue circle i cant get points to compare and in this path recalculation function is called.

Can any one tell me the solution from which i can get all points of route even if it is a straight road.

Answer 1

I know this is an old thread, but recently ran into the same problem and found an OK solution. The concept is that you don't calculate the distance to EACH line segment but only to the TWO segments connected to the closest point.

1. calculate the distance of your current location to all the points in the MKPolyline and take the minimum from that. (There's probably some nice way to optimize this. Like not iterating through all the points on every location update, but don't have time to dig in to that now).
2. You now know the distance to the closest polyline-point. However that point might still be far away while the polyline itself (connecting this point and the previous or the next point) might be closer. So, calculate the distance between your current location and these two line-segments and you have the closest distance.

Now, this is not waterproof. While it minimizes the nr of api calls, on some occasions (If you have crazy bends and curves in the MKPolyline) it might call the api while not needed, but hey, then the same line will be drawn again, no damage done. In my tests it worked fine and you can also adjust the accuracy. I've set it to 200m (0.2km) in the code below.

//Get Coordinates of points in MKPolyline
NSUInteger pointCount = routeLineGuidanceTurn.pointCount;
CLLocationCoordinate2D *routeCoordinates = malloc(pointCount * sizeof(CLLocationCoordinate2D));
[routeLineGuidanceTurn getCoordinates:routeCoordinates
                         range:NSMakeRange(0, pointCount)];
NSLog(@"route pointCount = %d", pointCount);


//Determine Minimum Distance and GuidancePoints from
double MinDistanceFromGuidanceInKM = 1000;
CLLocationCoordinate2D prevPoint;
CLLocationCoordinate2D pointWithMinDistance;
CLLocationCoordinate2D nextPoint;

for (int c=0; c < pointCount; c++)
{
    double newDistanceInKM = [self distanceBetweentwoPoints:Currentcordinate.latitude longitude:Currentcordinate.longitude Old:routeCoordinates[c].latitude longitude:routeCoordinates[c].longitude];
    if (newDistanceInKM < MinDistanceFromGuidanceInKM) {
        MinDistanceFromGuidanceInKM = newDistanceInKM;
        prevPoint = routeCoordinates[MAX(c-1,0)];
        pointWithMinDistance = routeCoordinates[c];
        nextPoint = routeCoordinates[MIN(c+1,pointCount-1)];
    }
}
free(routeCoordinates);


NSLog(@"MinDistanceBefore: %f",MinDistanceFromGuidanceInKM);

//If minimum distance > 200m we might have to recalc GuidanceLine.
//To be sure we take the two linesegments connected to the point with the shortest distance and calculate the distance from our current position to that linedistance.
if (MinDistanceFromGuidanceInKM > 0.2) {
    MinDistanceFromGuidanceInKM = MIN(MIN([self lineSegmentDistanceFromOrigin:Currentcordinate onLineSegmentPointA:prevPoint pointB:pointWithMinDistance], [self lineSegmentDistanceFromOrigin:Currentcordinate onLineSegmentPointA:pointWithMinDistance pointB:nextPoint]),MinDistanceFromGuidanceInKM);

    if (MinDistanceFromGuidanceInKM > 0.2) {
        // Call the API and redraw the polyline.
    }
}

Here's the fun that calculate sthe distance between two points. I know there is a built in function for it, but had it in my code already.

-(double)distanceBetweentwoPoints:(double)Nlat longitude:(double)Nlon Old:(double)Olat longitude:(double)Olon  {
    //NSLog(@"distanceBetweentwoPoints");
    double Math=3.14159265;
    double radlat1 = Math* Nlat/180;
    double radlat2 = Math * Olat/180;
    double theta = Nlon-Olon;
    double radtheta = Math * theta/180;
    double dist = sin(radlat1) * sin(radlat2) + cos(radlat1) * cos(radlat2) * cos(radtheta);
    if (dist>1) {dist=1;} else if (dist<-1) {dist=-1;}
    dist = acos(dist);
    dist = dist * 180/Math;
    dist = dist * 60 * 1.1515;
    return dist * 1.609344;
}

And here's the bit that calculates the distance between a point and a line segment between two other points. I got this from here: https://stackoverflow.com/a/28028023/3139134 Modified it a bit to work with CLLocationCoordinate2D and return the distance.

- (CGFloat)lineSegmentDistanceFromOrigin:(CLLocationCoordinate2D)origin onLineSegmentPointA:(CLLocationCoordinate2D)pointA pointB:(CLLocationCoordinate2D)pointB {

    CGPoint dAP = CGPointMake(origin.longitude - pointA.longitude, origin.latitude - pointA.latitude);
    CGPoint dAB = CGPointMake(pointB.longitude - pointA.longitude, pointB.latitude - pointA.latitude);
    CGFloat dot = dAP.x * dAB.x + dAP.y * dAB.y;
    CGFloat squareLength = dAB.x * dAB.x + dAB.y * dAB.y;
    CGFloat param = dot / squareLength;

    CGPoint nearestPoint;
    if (param < 0 || (pointA.longitude == pointB.longitude && pointA.latitude == pointB.latitude)) {
        nearestPoint.x = pointA.longitude;
        nearestPoint.y = pointA.latitude;
    } else if (param > 1) {
        nearestPoint.x = pointB.longitude;
        nearestPoint.y = pointB.latitude;
    } else {
        nearestPoint.x = pointA.longitude + param * dAB.x;
        nearestPoint.y = pointA.latitude + param * dAB.y;
    }

    CGFloat dx = origin.longitude - nearestPoint.x;
    CGFloat dy = origin.latitude - nearestPoint.y;
    return sqrtf(dx * dx + dy * dy) * 100;

}

Answer 2

For each pair of points in each step, you can calculate the distance between them using the Pythagorean Theorem:

distance = sqrt(  pow((point1.x - point2.x), 2)   +   pow((point1.y - point2.y), 2)  )

Then, if the distance is greater than 100m, add intermediary points along the line segment.