performance - 更快地找到最近的点对

Question

我正在尝试将数组的所有元素相互比较。我可以用嵌套循环来做，但这是一个非常低效的算法，我可以说这不是正确的方法。这就是我现在正在做的事情。

下面的 PER 答案我已经更改了这段代码，我正在扩展这个问题。

// Point from java.awt.Point;
private static void findShortestDistance(Point[] pt) {

  ArrayList<Double> distance = new ArrayList<Double>(1000);    

  for(int i=0; i<pt.length; i++) {
    for(int j=i+1; j<pt.length; j++) {
      double tmp = pt[i].distance(pt[j]);
      distance.add(tmp);        
    }
  }

  double min = distance.get(0);
  for(Double d : distance) {
    if(d < min) { min = d; }
  }

}

这是我目前使用的方法的完整代码。我试图找到给定数组中两点之间的最短距离。

Answer 1

看看维基百科。 http://en.wikipedia.org/wiki/Closest_pair_of_points

这个问题好像和 Shortest distance between points algorithm