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

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添加到其最近点，并检查点是否已被添加。如果添加了一个新的点，只检查它和所有的原始点。

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

Answer 2

如果您的问题是从任何位置的所有“位置”中找到最近的“点”，并且您的函数将被多次调用(具有相同的“位置”和“点”)，也许您应该考虑创建某种类型的空间数据结构(这就是我所说的预处理)。例如四叉树(https://en.wikipedia.org/wiki/Quadtree)。四叉树的构建可能需要一些时间，但你在搜索时会非常有效。-元素插入需要O( logN) (即对于N个点，总共(N *logN)(您的情况可能是N= M*M)) -搜索只需要O(LogN)就可以在笛卡尔坐标下完美地工作。如果您使用的是地理坐标，则应首先对其进行转换。