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.

Works with: GNUstep

Works with: Cocoa

<lang objc>#import <Foundation/Foundation.h>

1. 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</lang>

<lang objc>@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</lang>

Testing

<lang objc>#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;

}</lang>

Timing (with the time command):

d&c:         0.22user 0.00system 0:00.41elapsed
brute force: 13.53user 0.06system 0:13.87elapsed