用oc写一个道格拉斯算法

// Objective-C code for Douglas-Peucker algorithm

#import "DouglasPeucker.h"

@implementation DouglasPeucker

+ (NSArray *)douglasPeucker:(NSArray *)points epsilon:(double)epsilon {
NSUInteger count = [points count];
if (count < 3) {
return points;
}

// Find the point with the maximum distance
double dmax = 0.0;
NSUInteger index = 0;
NSUInteger end = count - 1;
for (NSUInteger i = 1; i < end; i++) {
double d = [self perpendicularDistance:[points objectAtIndex:i] start:[points objectAtIndex:0] end:[points objectAtIndex:end]];
if (d > dmax) {
index = i;
dmax = d;
}
}

// If max distance is greater than epsilon, recursively simplify
NSMutableArray *result = [NSMutableArray array];
if (dmax > epsilon) {
NSArray *recResults1 = [self douglasPeucker:[points subarrayWithRange:NSMakeRange(0, index + 1)] epsilon:epsilon];
NSArray *recResults2 = [self douglasPeucker:[points subarrayWithRange:NSMakeRange(index, count - index)] epsilon:epsilon];
[result addObjectsFromArray:recResults1];
[result removeLastObject];
[result addObjectsFromArray:recResults2];
} else {
[result addObject:[points objectAtIndex:0]];
[result addObject:[points objectAtIndex:end]];
}

return result;
}

+ (double)perpendicularDistance:(CLLocationCoordinate2D)point start:(CLLocationCoordinate2D)start end:(CLLocationCoordinate2D)end {
double x = point.longitude;
double y = point.latitude;
double x1 = start.longitude;
double y1 = start.latitude;
double x2 = end.longitude;
double y2 = end.latitude;

double A = x - x1;
double B = y - y1;
double C = x2 - x1;
double D = y2 - y1;

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

double xx, yy;

if (param < 0) {
xx = x1;
yy = y1;
} else if (param > 1) {
xx = x2;
yy = y2;
} else {
xx = x1 + param * C;
yy = y1 + param * D;
}

double dx = x - xx;
double dy = y - yy;

return sqrt(dx * dx + dy * dy);
}

@end