algorithm - 对一组点的浓度进行排序的算法

Question

我有坐标数组，我希望按点的集中区域对其进行排序。我尝试过使用 Graham 算法（如下所示），但没有得到想要的结果。我可以使用什么算法来对点进行排序，如下图所示：

资源：

def rotate(A,B,C):
return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])

def grahamscan(A):
    n = len(A) 
    P = range(n) 
    for i in range(1,n):
      if A[P[i]][0]<A[P[0]][0]: 
         P[i], P[0] = P[0], P[i] 
for i in range(2,n): 
  j = i
  while j>1 and (rotate(A[P[0]],A[P[j-1]],A[P[j]])<0): 
     P[j], P[j-1] = P[j-1], P[j]
     j -= 1
S = [P[0],P[1]] 
for i in range(2,n):
  while rotate(A[S[-2]],A[S[-1]],A[P[i]])<0:
    del S[-1] # pop(S)
    S.append(P[i]) # push(S,P[i])
return S

Answer 1

你需要某种聚类。首先尝试K_Means 方法。

Answer 2

谢谢大家的帮助！我为我的案例实现了一个专有算法（尽管它可能已经存在）（见下文）。

来源（目标 C）：

static inline NSArray* clustering (NSArray *aSetOfPoint, CGFloat radius, CGFloat delta) {

NSMutableArray *data = [NSMutableArray arrayWithArray:aSetOfPoint.copy];
NSMutableArray *result = [NSMutableArray new];

while (data.count > 0) {

  NSMutableArray *cluster = [NSMutableArray new];

  NSArray *zeroPoint = data[0];
  for (NSArray *aPoint in data) {
     if ([zeroPoint[0] floatValue] > [aPoint[0] floatValue]) {
        zeroPoint = aPoint;
     }
  }
  [cluster addObject:zeroPoint];
  [data removeObject:zeroPoint];

  CGPoint zeroCoordinate = CGPointMake([zeroPoint[0] floatValue], [zeroPoint[1] floatValue]);
  __block CGRect clusterRect = CGRectMake(zeroCoordinate.x, zeroCoordinate.y-radius, radius, 2 * radius);
  __block int count = 1;
  while (count > 0) {
     count =0;
     NSMutableArray *clusteringData = data.copy;

     [clusteringData enumerateObjectsUsingBlock:^(NSArray *aPoint, NSUInteger idx, BOOL *stop) {
        if (aPoint) {
           CGPoint aCoordinate = CGPointMake([aPoint[0] floatValue], [aPoint[1] floatValue]);

           if (CGRectContainsPoint(clusterRect, aCoordinate)) {
              [cluster addObject:aPoint];
              [data removeObject:aPoint];
              count++;
           }
        }
     }];

     clusterRect = CGRectMake(zeroCoordinate.x, zeroCoordinate.y - delta, clusterRect.size.width + delta, clusterRect.size.height + 2 * delta);
  }
  if (cluster.count == 1) {
     [cluster addObject:cluster[0]];
  }
  [result addObject:cluster];
}

  return [NSArray arrayWithArray:result];
}