Sorting an Array of X and Y Vertice Points ? iOS / Objective C [closed]

Question

I have a Core Data entity called Line. Each line contains an instance of a VerticePoint which contains an x and y property. These x and y vertices form simple 2D polygons.

What I want to do is sort an array of these Line objects which is in random order so that the origin of the shape, the bottom left point, is always the first element in the array, then followed by the remaining vertices wound in counter-clockwise direction from the origin.

So say the points in my original array are (x y axis is centred at 0,0) :

x = 20, y = 20
x = 20 , y= 10
x = 10, y=10
x = 10, y =20
x = 15, y = 10

I want to sort them like so :

x = 10, y=10
x = 15, y = 10
x = 20 , y= 10
x = 20, y = 20
x = 10, y =20

Many thanks

Answer 1

Here's a proposal for a precise specification:

1. Assume a first quadrant coordinate system (with the y axis pointing up).
2. Find the center of the axis aligned bounding box of all points.
3. Sort the points by the angle of a vector from the center to the point. To calculate the angle consider a vector pointing south west to be at 0° with angles ascending in counter-clockwise direction.

And here's a solution:

NSArray *points = @[
    [NSValue valueWithCGPoint:(CGPoint){20, 20}],
    [NSValue valueWithCGPoint:(CGPoint){20, 10}],
    [NSValue valueWithCGPoint:(CGPoint){10, 10}],
    [NSValue valueWithCGPoint:(CGPoint){10, 20}],
    [NSValue valueWithCGPoint:(CGPoint){15, 10}],
];

CGPoint min = [points[0] CGPointValue];
CGPoint max = min;
for (NSValue *value in points) {
    CGPoint point = [value CGPointValue];
    min.x = fminf(point.x, min.x);
    min.y = fminf(point.y, min.y);
    max.x = fmaxf(point.x, max.x);
    max.y = fmaxf(point.y, max.y);
}

CGPoint center = {
    0.5f * (min.x + max.x),
    0.5f * (min.y + max.y),
};

NSLog(@"center: %@", NSStringFromCGPoint(center));

NSNumber *(^angleFromPoint)(id) = ^(NSValue *value){
    CGPoint point = [value CGPointValue];
    CGFloat theta = atan2f(point.y - center.y, point.x - center.x);
    CGFloat angle = fmodf(M_PI - M_PI_4 + theta, 2 * M_PI);
    return @(angle);
};

NSArray *sortedPoints = [points sortedArrayUsingComparator:^NSComparisonResult(id a, id b) {
    return [angleFromPoint(a) compare:angleFromPoint(b)];
}];

NSLog(@"sorted points: %@", sortedPoints);

Answer 2

You can use

- (NSArray *)sortedArrayUsingDescriptors:(NSArray *)sortDescriptors

of NSArray.

You can use more then one descriptor. Just initialize two descriptors one with x, one with y property.