用於排列點濃度數組的算法

我有座標數組，我希望通過點的集中區域對它進行排序。我曾嘗試使用格雷厄姆算法（如下所示），但我沒有得到期望的結果。我可以使用哪些算法進行排序的點，如圖所示在此圖像中：用於排列點濃度數組的算法

enter image description here

來源：

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

來源

2013-07-08 Dickordia

你有什麼時間限制？數據集有多大？ –

我想在本週結束之前完成這項任務。數據大小在1範圍內 - 接近5000個座標。 – Dickordia

我應該說「運行時間約束」。你想如何定義「濃度區」？ –

你需要某種clusterization。首先嚐試K_Means method。

來源

2013-07-09 06:07:57 MBo

是啊，我認爲這可能是NP-hard，這就是爲什麼我詢問運行時間和數據大小的原因。 –

謝謝大家的幫助！我爲我的案例實施了專有算法（儘管它可能已經存在）（請參閱下文）。

源（目標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]; 
}

來源

2013-07-10 14:21:34 Dickordia

用於排列點濃度數組的算法

回答

相關問題