iOS path following: convert list of coordinates to a bezier curve

Question

I have an array of coordinates which represents a users route. I want to be able to redraw this route and have another user follow it exactly. Although I only want to save significant coordinates (waypoints) when the route will change direction.

Is there a way I can convert the array of coordinates to a bezier curve and use this so I only get significant coordinates instead of saving every one in an array(most of which are in the same direction and aren't needed)

I want to be able to reconstruct the route to give waypoints. These waypoints will be used to direct the user along the route as eventually I will be using MKDirections to direct them to each waypoint.

Answer 1

You should not use MKDirections since it is not made for following a precalculated path but to give you the fastest route to the destination! Therefore I will use MKMapOverlayRenderer instead!

There are several things you can to achieve this. I want to talk about easy algorithm for removing the unnecessary waypoints:

NSArray* path = YOURPATH
NSMutableArray* waypoints = [path mutableCopy];

CGFloat smoothness = 0.01;

for(NSInteger scale=1;scale<log2(waypoints.count);scale++)
{
    for(NSInteger index = 0; index<waypoints.count-2;index++)
    {
        CLLocation *start = [waypoints objectAtIndex:index];
        CLLocation *middle = [waypoints objectAtIndex:index+1];
        CLLocation *end = [waypoints objectAtIndex:index+2];

        CGFloat dist_start_end = [end distanceFromLocation:start];
        CGFloat dist_start_middle_end = [middle distanceFromLocation:start]+[end distanceFromLocation:middle];

        CGFloat diff = dist_start_end-dist_start_middle_end;
        CGFloat ratio = diff/(dist_start_end);

        if (ratio<1+smoothness) {
            [waypoints removeObjectAtIndex:index+1];
            index-=1;
        }
    }
}

This should remove the unwanted points. You should playaround with the 'smoothness' variable. The bigger the value, the more details will be removed! (therefore better compression)

Now with this array, you can construct your bezier path!

I will not go into the details on how to actually put the bezier path onto the map, there are so many other questions about this on Stackoverflow and also tutorials on the internet. But I will shortly touch on how you should create/use the two control points of the bezier path:

Given the waypoints array we created above, you will probably add some additional control points, in order to avoid driving directions taking a shortcut through a building. Therefore you should calculate the control points between two actual points on the path like this:

CGFloat cornerRadius = 5;
NSMutableArray* pathPoints = [NSMutableArray new];

if (waypoints.count>1) {
    [pathPoints addObject:[waypoints objectAtIndex:0]];
    [pathPoints addObject:[waypoints objectAtIndex:0]];
    [pathPoints addObject:[waypoints objectAtIndex:1]];
    [pathPoints addObject:[waypoints objectAtIndex:1]];
}
for (NSInteger index = 1;index<waypoints.count-1;index++) {
    CLLocation* lastLocation = [waypoints objectAtIndex:index-1];
    CLLocation* currentLocation = [waypoints objectAtIndex:index];
    CLLocation* nextLocation = [waypoints objectAtIndex:index+1];

    [pathPoints addObject:currentLocation];

    CGFloat latDiff = currentLocation.coordinate.latitude - lastLocation.coordinate.latitude;
    CGFloat longDiff = currentLocation.coordinate.longitude - lastLocation.coordinate.longitude;
    CGFloat dist = [currentLocation distanceFromLocation:lastLocation];
    CGFloat controlPointALat = cornerRadius*latDiff/dist;
    CGFloat controlPointALong = cornerRadius*longDiff/dist;

    CLLocation* controlPointA =
    [[CLLocation alloc] initWithLatitude:controlPointALat longitude:controlPointALong];
    [pathPoints addObject:controlPointA];

    if (index<waypoints.count-2) {
        CLLocation* nextNextLocation = [waypoints objectAtIndex:index+2];

        latDiff = nextNextLocation.coordinate.latitude - nextLocation.coordinate.latitude;
        longDiff = nextNextLocation.coordinate.longitude - nextLocation.coordinate.longitude;
        dist = [nextNextLocation distanceFromLocation:nextLocation];
        CGFloat controlPointBLat = cornerRadius*latDiff/dist;
        CGFloat controlPointBLong = cornerRadius*longDiff/dist;

        CLLocation* controlPointB =
        [[CLLocation alloc] initWithLatitude:controlPointBLat longitude:controlPointBLong];
        [pathPoints addObject:controlPointB];
    }else{
        [pathPoints addObject:controlPointA];
    }
    [pathPoints addObject:nextLocation];
}

Now you can use this pathArray to build your bezierPaths with a simple for loop:

for(NSInteger index=0;index<pathPoints.count-3;index+=4)
{
   CLLocation *start = [pathPoints objectAtIndex:index];
   CLLocation *controlPointA = [pathPoints objectAtIndex:index+1];
   CLLocation *controlPointB = [pathPoints objectAtIndex:index+2];
   CLLocation *end = [pathPoints objectAtIndex:index+3];

   //BEZIER CURVE HERE
}

You can either use a UIBezierPath and use the CGPath property to create your MKMapOverlayRenderer, or you can directly use a CGPath. Later adding the path to your map is described here: MKMapOverlayRenderer

Createing a UIBezierPath is described here: UIBezierPath

Answer 2

You can take an array of NSValues because you can't add a CGPoint directly into an Array

This is how we do it

NSMutableArray *arrayOfPoints = [[NSMutableArray alloc] init];
[arrayOfPoints addObject:[NSValue valueWithCGPoint:CGPointMake(10, 20)]];
// here point is the cgpoint you want to add 

Now you have your points added to an array what you can do is traverse every object and add them to your UIBezierPath

  NSInteger  i = 0;
   UIBezierPath _path1 = [UIBezierPath bezierPath];

for(NSValue *val in arrayOfPoints){
    if (i==0){
        [_path1 moveToPoint:[val CGPointValue]];
    }
    else{
        [_path1 addLineToPoint:[val CGPointValue]];
    }
    i++;
}

I hope this helps and solve your problem