距离计算优化

我正在写一个算法来计算2d平面中点的最近邻点。目前，我蛮力计算每一个距离通过两个for循环距离计算优化

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）的对称性？我还有其他意见吗？

此外，你可以向我描述另一种算法，这将是更好的方法来执行此计算？我研究过二叉树，但是我不确定它们是如何应用于我的问题的！

来源

2017-02-24 AngusTheMan

你想返回一个解决方案或所有方案的算法的细节？（有一般的多最近的邻居） – niceman

你可以通过j在i+1来解释对称性。这也将照顾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 
    } 
}

来源

2017-02-24 12:14:37 dasblinkenlight

-1

计算出所有的点（0,0）之间的距离。然后按升序排序距离。

现在，特殊点的后继者和前辈是最近的邻居。

来源

2017-02-24 12:21:49 Liju

即使在1D中，这也不起作用。按照距离0排序的点[-2,1,3]给出[1，-2，3]。与3最近的邻居不是-2。 –

我们的电脑屏幕像素协调是图的“第四象限”。其中（0,0）是左上角。不存在负值的可能性。 – Liju

你想用quadtrees为你的数据结构

这nice post为您提供关于如何进行

来源

2017-02-24 12:52:42 Fezvez

距离计算优化

回答

相关问题