java - 在寻找最近的位置时，我怎样才能比蛮力做得更好？

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;  
}  

考虑到 Blob 的大小不是那么大，目前可以正常工作 ~ 最多 200 个。
我可以做些什么来改进我的方法？
除了 geohashing 之外，我还可以使用其他算法来获得更好的性能吗？
是否有一些坐标属性可以用来跳过循环的某些部分？

Answer 1

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

但是，为了避免每次要存储最近点时都必须运行此函数的麻烦，请将所有点的 HashMap 添加到最接近的点，并检查该点是否已添加。如果添加了一个新点，只检查它和所有原始点。

希望这能有所帮助，即使只是一点点。