在找到最近的位置时,我怎么能比蛮力更好？

Question

我有以下代码:

public static Location findClosest(Location myPosition, ArrayList<Location> spots) {  
  double min = Double.MAX_VALUE;  
  Location closer = null;  
  for(MyPosition aPosition:spots) {  
     float dist = Math.abs(aPosition.distanceTo(myPosition));  
     if(dist < min) {  
         min = dist;  
         closer = aPosition;  
     }  
  }  
  return closer;  
}  

这是一种强力O(N ^ 2)方法,因为这是从以下函数调用的:

public static Location findClosest(Location myPosition, ArrayList<Places> places) {   
   Location closer = null;  
   double min = Double.MAX_VALUE;    
   for(Places place:places) {  
      Location currentMin = findClosest(myPosition, places.getSpots());  
      float dist = Math.abs(currentMin.distanceTo(myPosition));  
      if(dist < min) {  
         min = dist;  
         closer = currentMin;  
      }  
   }  
   return closer;  
}  

现在可以正常工作,考虑到斑点的大小不是那么大~200最大.
我该怎么做才能改进我的方法？
除了geohashing之外还有其他算法可以用来提高性能吗？
是否有一些坐标属性我可以用来跳过循环的某些部分？

Answer 1

因为你说的是​​ O(N^2)，但这是一个 O(N) 函数，所以我假设你在循环内调用它来确定每个点最接近的点。那样的话，我不知道什么会更快。

但是，为了省去每次要存储最近点时都必须运行此函数的麻烦，请添加所有距离最近的点的 HashMap，并检查该点是否已添加。如果添加了新点，只需检查它以及所有原始点。

希望这会有所帮助，哪怕只是一点点。