Среднее расстояние между точками в кластере

Question

Похоже, что я получил концепцию, но, похоже, неправильная реализация верна. eI имеет кластер (ArrayList) с несколькими точками, и я хочу рассчитать avg distance. Ex: Точки в кластере (A, B, C, D, E, F, ..., n), Расстояние AB, Расстояние AC, Расстояние AD, ... Расстояние A, N, Расстояние (B, C) Расстояние (B, D) ... Расстояние (B, N) ...

Заранее спасибо.

Answer 1

Вы не хотите удваивать счет любого сегмента, поэтому ваш алгоритм должен быть двойным для цикла. Внешний цикл идет от A до M (вам не нужно проверять N, потому что ему нечего будет с ним подключаться), каждый раз, переходя из curPoint в N, вычисляя каждое расстояние. Вы добавляете все расстояния и делите на количество точек (n-1)^2/2. Должно быть довольно просто.

Нет стандартных алгоритмов для улучшения этого, о котором я знаю, и это не является широко изученной проблемой. Я бы предположил, что вы можете получить довольно разумную оценку (если оценка полезна) путем выборки расстояний от каждой точки до нескольких других. Но это предположение.

(Осмотрев ваш пример кода) Вот еще одна попытка:

public double avgDistanceInCluster() { 
    double totDistance = 0.0; 
    for (int i = 0; i < bigCluster.length - 1; i++) { 
     for (int j = i+1; j < bigCluster.length; j++) { 
      totDistance += distance(bigCluster[i], bigCluster[j]); 
     } 
    } 
    return totDistance/(bigCluster.length * (bigCluster.length - 1))/2; 
} 

Обратите внимание, что предел для первого цикла различна. Расстояние между двумя точками, вероятно, sqrt((x1 - x2)^2 + (y1 -y2)^2).

Answer 2

Спасибо за помощь, иногда после объяснения вопроса на форуме ответ просто всплывает на ваш взгляд. Это то, что я делаю.

У меня есть кластер точки, и мне нужно вычислить среднее расстояние точек (пар) в кластере. Итак, это то, что я сделал. Я уверен, что кто-то придет с лучшим ответом, если так, пожалуйста, напишите заметку. Заранее спасибо.

/** 
* Calculate avg distance between points in cluster 
* @return 
*/ 
public double avgDistanceInCluster() { 
    double avgDistance = 0.0; 
    Stack<Double> holder = new Stack<Double>(); 
    for (int i = 0; i < cluster.size(); i++) { 
     System.out.println(cluster.get(i)); 
     for (int j = i+1; j < cluster.size(); j++) { 
      avgDistance = (cluster.get(i) + cluster.get(j))/2; 
      holder.push(avgDistance); 
     } 
    } 
    Iterator<Double> iter = holder.iterator(); 
    double avgClusterDist = 0; 
    while (iter.hasNext()) { 
     avgClusterDist =+ holder.pop(); 
     System.out.println(avgClusterDist); 
    } 
    return avgClusterDist/cluster.size(); 
}