距离计算优化

Question

我正在编写一种算法，该算法计算2D平面中点的邻居。目前，我很暴力地通过两个循环计算每个距离

for(i=0; i<N ;i++){
   for (j=0; j<N; j++{ 
      /* distance computation */
      /* remember smallest distance for all i */
   }
}

我已经有一个if(i==j) continue;语句，因此我们避免计算同点点之间的距离。我想知道如何进一步优化该算法。例如，我如何计算距离的对称性（i，j）=距离（j，i）？我还有其他要考虑的要点吗？

此外，您能否向我描述另一种算法，这将是执行此计算的更好方法？我看过二进制树，但不确定它们实际上如何应用于我的问题！

Answer 1

您想将四分之一用作数据结构

这篇不错的帖子为您提供了有关如何继续

Answer 2

您可以通过在i+1上启动j来计算对称性。这也将在没有特例的情况下照顾i == j情况：

for (i = 0 ; i != N ; i++) {
    for (int j = i+1 ; j != N ; j++) {
        dist = ... // Compute the distance
        distance[i][j] = distance[j][i] = dist; // Set in both directions
    }
}