对X和Y顶点的数组进行排序？iOS/Objective C

Question

我有一个名为Line的核心数据实体.每行包含一个VerticePoint实例,其中包含x和y属性.这些x和y顶点形成简单的2D多边形.

我想要做的是对这些Line对象的数组进行排序,这些对象是随机顺序,以便形状的原点(左下角点)始终是数组中的第一个元素,然后是其余的顶点缠绕在从原点顺时针方向.

所以说我的原始数组中的点是(xy轴以0,0为中心):

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

我想这样排序:

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

非常感谢

Answer 1

这是一个精确规范的提案:

1. 假设第一象限坐标系(y轴朝上).
2. 找到所有点的轴对齐边界框的中心.
3. 按照从中心到点的矢量角度对点进行排序.为了计算角度,考虑指向西南方向的矢量为0°,其中角度沿逆时针方向上升.

这是一个解决方案:

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);