Closest-pair problem/Objective-C
Closest-pair problem/Objective-C is part of Closest pair problem. You may find other members of Closest pair problem at Category:Closest pair problem.
#import <Foundation/Foundation.h>
#import <math.h>
@interface Point : NSObject {
double xCoord, yCoord;
}
+ (instancetype)x: (double)x y: (double)y;
- (instancetype)initWithX: (double)x andY: (double)y;
- (double)x;
- (double)y;
- (double)dist: (Point *)pt;
- (NSComparisonResult)compareX: (Point *)pt;
- (NSComparisonResult)compareY: (Point *)pt;
@end
@implementation Point
+ (instancetype)x: (double)x y: (double)y {
return [[self alloc] initWithX: x andY: y];
}
- (instancetype)initWithX: (double)x andY: (double)y {
if ((self = [super init])) {
xCoord = x;
yCoord = y;
}
return self;
}
- (double)x { return xCoord; }
- (double)y { return yCoord; }
- (double)dist: (Point *)pt {
return hypot([self x] - [pt x], [self y] - [pt y]);
}
- (NSComparisonResult)compareX: (Point *)pt {
if ( [self x] < [pt x] ) return NSOrderedAscending;
else if ( [self x] > [pt x] ) return NSOrderedDescending;
else return NSOrderedSame;
}
- (NSComparisonResult)compareY: (Point *)pt {
if ( [self y] < [pt y] ) return NSOrderedAscending;
else if ( [self y] > [pt y] ) return NSOrderedDescending;
else return NSOrderedSame;
}
@end
@interface ClosestPair : NSObject
+ (NSArray *)closestPairSimple: (NSArray *)pts;
+ (NSArray *)closestPair: (NSArray *)pts;
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP;
+ (id)minBetween: (id)minA and: (id)minB;
@end
@implementation ClosestPair
+ (NSArray *)closestPairSimple: (NSArray *)pts {
if ( [pts count] < 2 ) return @[ @HUGE_VAL ];
double c = [ pts[0] dist: pts[1] ];
NSArray *r = @[ @(c), pts[0], pts[1] ];
for(int i=0; i < ([pts count] - 1); i++) {
for(int j=i+1; j < [pts count]; j++) {
double t = [ pts[i] dist: pts[j] ];
if ( t < c ) {
c = t;
r = @[ @(t), pts[i], pts[j] ];
}
}
}
return r;
}
+ (NSArray *)closestPair: (NSArray *)pts {
return [self closestPairPriv: [pts sortedArrayUsingSelector: @selector(compareX:)]
and: [pts sortedArrayUsingSelector: @selector(compareY:)]
];
}
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP {
int nP, k;
if ( [xP count] <= 3 ) {
return [self closestPairSimple: xP];
} else {
int midx = ceil([xP count]/2.0);
NSArray *pL = [xP subarrayWithRange: NSMakeRange(0, midx)];
NSArray *pR = [xP subarrayWithRange: NSMakeRange(midx, [xP count] - midx)];
NSMutableArray *yL = [[NSMutableArray alloc] init];
NSMutableArray *yR = [[NSMutableArray alloc] init];
double middleVLine = [pL[midx-1] x];
for(int i=0; i < [yP count]; i++) {
if ( [yP[i] x] <= middleVLine ) {
[yL addObject: yP[i]];
} else {
[yR addObject: yP[i]];
}
}
NSArray *minR = [ClosestPair closestPairPriv: pR and: yR];
NSArray *minL = [ClosestPair closestPairPriv: pL and: yL];
NSMutableArray *minDist = [ClosestPair minBetween: minR and: minL];
NSMutableArray *joiningStrip = [NSMutableArray arrayWithCapacity: [xP count]];
for(int i=0; i < [yP count]; i++) {
if ( fabs([yP[i] x] - middleVLine) <
[minDist[0] doubleValue] ) {
[joiningStrip addObject: yP[i]];
}
}
NSMutableArray *tDist = minDist;
int nP = [joiningStrip count];
for(int i=0; i < (nP - 1); i++) {
int k = i + 1;
while( (k < nP) &&
( ([joiningStrip[k] y] - [joiningStrip[i] y]) < [minDist[0] doubleValue] ) ) {
double d = [joiningStrip[i] dist: joiningStrip[k]];
if ( d < [tDist[0] doubleValue] ) {
tDist = @[ @(d), joiningStrip[i], joiningStrip[k] ];
}
k++;
}
}
return tDist;
}
}
+ (id)minBetween: (id)minA and: (id)minB {
if ( [minA[0] doubleValue] < [minB[0] doubleValue] ) {
return minA;
} else {
return minB;
}
}
@end
Testing
#define NP 10000
int main()
{
@autoreleasepool {
NSMutableArray *p = [[NSMutableArray alloc] init];
srand(0);
for(int i = 0; i < NP; i++) {
[p addObject:
[Point x: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0
y: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0]
];
}
//NSArray *r1 = [ClosestPair closestPairSimple: p];
NSArray *r2 = [ClosestPair closestPair: p];
//NSLog(@"%lf", [r1[0] doubleValue]);
NSLog(@"%lf", [r2[0] doubleValue]);
}
return EXIT_SUCCESS;
}
Timing (with the time command):
d&c: 0.22user 0.00system 0:00.41elapsed brute force: 13.53user 0.06system 0:13.87elapsed