Objective-C Douglas Peucker Algorithm

Objective-C Douglas Peucker Algorithm
4 years, 10 months ago 3
Posted in: Programming

A problem that I’ve run across is needing to render onto a custom chart roughly 8000 or more data points. At first I naively attempted to render all 8000 points, only to discover that it could not. At 2 pixels per data point, that’s 16,000 pixels and no surprise that iOS could not handle all that at once. I had read that the recommended size for views was around 1024 pixels, but in practice for iOS 5.1 I’ve found that 2000 pixels is okay and anything more is dicy.

So, I was in the hunt for an algorithm that could reduce the number of data points without unduly getting rid of the peaks and valleys (which has importance). I stumbled across the Ramer-Douglas-Peucker algorithm in my hunt. It seemed to fit the bill, but I could not find an Objective-C implementation. No worries as I found the C# implementation of the algorithm, so all that was left to do was port it.

The code below is my port of the algorithm:


#import <Foundation/Foundation.h>

@interface DataPoint : NSObject

@property (assign, nonatomic) double x;
@property (assign, nonatomic) double y;

- (id)initWithX:(double)xValue andY:(double)yValue;
- (BOOL)equalsTo:(DataPoint *)point;

@end


#import "DataPoint.h"

@implementation DataPoint
@synthesize x;
@synthesize y;

- (id)initWithX:(double)xValue andY:(double)yValue
{
    self.x = xValue;
    self.y = yValue;
    
    return self;
}

- (BOOL)equalsTo:(DataPoint *)point
{
    if (point == nil)
        return NO;
    
    return (point.x == self.x && point.y == self.y);
}

@end


- (NSMutableArray *)douglasPeuckerReduction:(NSMutableArray *)points withTolerance:(double)tolerance
{
    if (points == nil || [points count] < 3)
        return points;
    
    NSUInteger firstPoint = 0;
    NSUInteger lastPoint = [points count] - 1;
    
    NSMutableArray * pointIndicesToKeep = [[NSMutableArray alloc] init];
    
    //Add the first and last index to the keepers
    [pointIndicesToKeep addObject:[NSNumber numberWithUnsignedInteger:firstPoint]];
    [pointIndicesToKeep addObject:[NSNumber numberWithUnsignedInteger:lastPoint]];
    
    //The first and the last point cannot be the same
    while ([[points objectAtIndex:firstPoint] equalsTo:[points objectAtIndex:lastPoint]])
    {
        lastPoint--;
    }
    
    NSMutableArray * pointsToKeep = [self douglasPeuckerReduction:points withFirstPoint:firstPoint lastPoint:lastPoint andTolerance:tolerance];
    [pointIndicesToKeep addObjectsFromArray:pointsToKeep];
    
    // Sort the points.
    NSSortDescriptor * sortOptions = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES selector:@selector(compare:)];
    [pointIndicesToKeep sortUsingDescriptors:[NSArray arrayWithObject:sortOptions]];
    
    return pointIndicesToKeep;
}

- (NSMutableArray *)douglasPeuckerReduction:(NSMutableArray *)points withFirstPoint:(NSUInteger)firstPoint lastPoint:(NSUInteger)lastPoint andTolerance:(double)tolerance
{
    NSMutableArray * pointIndicesToKeep = [[NSMutableArray alloc] init];
    
    double maxDistance = 0;
    NSUInteger indexFarthest = 0;
    
    for (NSUInteger index = firstPoint; index < lastPoint; index++)
    {
        double distance = [self perpendicularDistanceOf:[points objectAtIndex:index] from:[points objectAtIndex:firstPoint] to:[points objectAtIndex:lastPoint]];
        
        
        if (distance > maxDistance)
        {
            maxDistance = distance;
            indexFarthest = index;
        }
    }
    
    if (maxDistance > tolerance && indexFarthest != 0)
    {
        //Add the largest point that exceeds the tolerance
        [pointIndicesToKeep addObject:[NSNumber numberWithUnsignedInteger:indexFarthest]];
        
        NSMutableArray * leftSide = [self douglasPeuckerReduction:points withFirstPoint:firstPoint lastPoint:indexFarthest andTolerance:tolerance];
        NSMutableArray * rightSide = [self douglasPeuckerReduction:points withFirstPoint:indexFarthest lastPoint:lastPoint andTolerance:tolerance];
        
        [pointIndicesToKeep addObjectsFromArray:leftSide];
        [pointIndicesToKeep addObjectsFromArray:rightSide];
    }
    
    return pointIndicesToKeep;
}

- (double)perpendicularDistanceOf:(DataPoint *)point from:(DataPoint *)pointA to:(DataPoint *)pointB
{
    //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|   *Area of triangle
    //Base = v((x1-x2)²+(x1-x2)²)                               *Base of Triangle*
    //Area = .5*Base*H                                          *Solve for height
    //Height = Area/.5/Base
    
    double area = fabs(.5 * (pointA.x * pointB.y + pointB.x * 
                                 point.y + point.x * pointA.y - pointB.x * pointA.y - point.x * 
                                 pointB.y - pointA.x * point.y));
    double bottom = sqrt(pow(pointA.x - pointB.x, 2) + 
                              pow(pointA.y - pointB.y, 2));
    double height = area / bottom * 2;
    
    return height;
}

Using the code is fairly straight-forward. The algorithm assumes that the input is an array of objects of type DataPoint.


NSMutableArray * points = [[NSMutableArray alloc] init];
// Populate points array with DataPoint objects. You can use the initWithX:andY: 
// method for convenience.
// [points addObject:[[DataPoint alloc] initWithX:2.0 andY:10.0]];

NSMutableArray * reducedSet = [self douglasPeuckerReduction:points withTolerance:5.0];

Probably the hardest part is finding a good tolerance value. Unfortunately there’s no real good rule of thumb as it really is dependent upon the data values. I’ve found that larger numbers result in fewer data points, for better or worse.

In the end, I wasn’t entirely happy with the results of the reduction. It was far too spiky when reducing the data set to 10% of the total number of points. Regardless, the algorithm could still be useful for other scenarios.

Related Posts

3 Responses

  1. Siva says:

    Could you please explain me some details about how to find out good tolerance value!

    • Kelly says:

      Unfortunately there is no good method for determining the tolerance. It’s mainly trial and error. However you’ll want to pick a tolerance where it can smooth out small spikes in the data.

  2. Siva says:

    We are actually tracking the navigation path in unknown places. Whenever user starts navigation we will get his current location lat long values, based on that values we draw polyline on the mapview. Could you please suggest us.. Which tolerance value best fits in this scenario?

Leave a Reply

Your email address will not be published. Required fields are marked *