最近邻居算法

Question

找到数据数组中最接近指向点的最​​快方法是什么？例如，我有3D空间，点（坐标 - （x，y，z））和点（xp，yp，zp）数组。 我需要找到最接近点（xp，yp，zp）。

据我所知，最慢的方法是使用线性搜索。有没有更好的解决方案？

可以添加任何辅助数据。

Answer 1

你可以在八叉树中组织你的观点。那么你只需要搜索一个小的子集。

参见：en.wikipedia.org/wiki/Octree

这是一个相当简单的数据结构，你可以实现你自己（这将是一个宝贵的学习经验），或者你可能会发现一些有用的库，让你去。

注意：我最初说的Quadtree（这是二维）意外。感谢@marcog的更正。

Answer 2

其我的理解四叉树是为2d，但你可以计算出3d的东西是非常相似的。这将加快您的搜索速度，但如果在飞行中完成，则需要更多时间来计算索引。我建议先计算索引并存储一次。在每次查找时，你都会找出所有外部四边形，然后按照自己的方式寻找点击......它看起来像是一个橙色。随着四边形变小，速度将大大增加。一切都有折衷。

Answer 3

除非它们没有按照正确的数据结构进行组织，唯一的方法就是线性搜索。

Answer 4

我会使用KD树在O（log（n））时间内做到这一点，假设点是随机分布的，或者您有一种方法来保持树平衡。

http://en.wikipedia.org/wiki/Kd-tree

KD树非常适合这种空间查询，甚至允许您检索最近ķ邻居查询点。

Answer 5

如果您正在进行一次性最近邻居查询，那么线性搜索确实是您可以获得的最佳选择。这当然假定数据不是预先结构化的。

但是，如果您要做很​​多查询，有几个space-partitioning data structures。这些都需要一些预处理来形成结构，但可以非常快地回答最近邻居查询。

由于您正在处理3D空间，因此我建议您查看octrees或kd-trees。如果你实现了一个合适的平衡算法（例如，中位数工作正常），Kd树更通用（它们适用于任意维度），并且可以比八进制更高效，但八进制更容易实现。

ANN是利用这些数据结构一个伟大的图书馆，而且还允许近似近邻查询这是显著快，但有一个小错误，因为他们只是近似值。如果您不能接受任何错误，则将错误界限设置为0。

Answer 6

考虑到仅搜索，“最快”的方法就是使用voxels。使用1：1点体素映射，访问时间是恒定的，速度非常快，只需将坐标移动到以体素原点为中心的点（如果需要），然后向下旋转位置并访问体素数组那个价值。对于某些情况，这是一个不错的选择。正如我之前所解释的，当1：1的地图很难获得时，八叉树会更好（太多的点，太少的体素分辨率，太多的可用空间）。

Answer 7

检查了这一点。你可以咨询CLRS计算几何章还.. http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

Answer 8

我建议KD树将努力为近邻搜索fine.Also好。

Answer 9

我需要在实时环境中为很多最近的邻居搜索这么做，而且在简单性和速度方面都采用了更好的算法。

把你所有的观点放到d列表中，其中d是空间的维度。在你的情况下3.根据它们的维度对这三个列表进行排序。这花费d（nlog（n））时间。这就是数据结构。

我们维护这些正确排序的列表，在每个维度中针对所有问题。诀窍是根据定义，一个方向上的距离必须小于或等于欧式距离。因此，如果一个方向上的距离大于我们当前最近已知点的最近距离，那么该点不能靠近，更重要的是，该方向上的所有点不能更大。一旦对于2 * d方向来说这是真的，我们根据定义就有最接近的点。

对于每个特定的元素，我们可以进行二元搜索到排序列表中以找到最近的位置，其中所需的点可以在两个不同的维度中。在数学上，我们知道如果+ x -x + y -y（其他维度很容易添加）中的距离超过了最小的已知欧几里得距离点，那个点必须超过距离，并且由于它是一个有序数组，根据定义，当我们超出那个方向时，我们知道我们可以放弃这个方向，因为在这个方向上没有更好的答案。但是，随着我们向这四个方向扩展，我们可以减少m的值，因为它等于我们找到的最近点的欧氏距离。

所以我们只有需要根据该轴排序的每个轴的排序列表。这很简单。

然后查询列表：

• 我们二进制搜索到每个列表（DLOG（N））。
• 我们发现我们当前的最小距离m。 （最初可以是无限的）
• 对于每个列表，我们沿正向和负向行进。
• 对于每一个我们有2个* d方向，
  • 我们横穿名单，降低m如果我们发现接近点。
• 当一个方向证明自己在数学上没有结果时，我们停止以这种方式进行搜索。
• 当没有方向时，我们找到了最近的点。

我们已经排序了列表，并且需要找到我们要在列表中的每个方向上搜索的点。我们进行二进制搜索以保持时间复杂度log（n）。然后，我们有最佳的当前距离（可能无限），然后我们向我们提供给我们的每个方向移动。当我们找到新的点时，我们更新目前为止的最近点。诀窍是，只要沿着一个方向的距离远远超过我们目前已知的最近点，我们就会放弃。

所以，如果我们有一个点在已知的最近距离13，那么只要在那个方向上的距离超过我们最近的已知距离，我们就可以中止在+ x，-x，+ y，-y方向上的检查距离。因为如果它比我们当前的m更远+ x，所有其余的+ x值可以在数学上被证明是更远的。随着我们获得更好更好的最近点，我们需要搜索的空间量越来越小。

如果我们用完一个方向的点，那个方向就完成了。 如果沿着该线的一个维度的点的距离本身大于m，则该方向完成。

当所有方向证明只有点必须远远超过我们的最佳点时，解决方案是m。

- 由于我们逐渐减少m，每个维度所需的距离整体上迅速下降，尽管像所有算法一样，它在较高维度上的下降速度较慢。但是，如果仅在一个维度上的距离大于迄今为止的最好距离，那么在这个方向上的所有其他点都不可能更好。

时间复杂性似乎与更好的一样。但是，在数据结构简单的情况下，这种算法明显胜出。还有很多其他属性使得这个算法成为一个非常有力的竞争者。当你更新东西的时候，你可以通过非常好的表现对列表进行处理，因为你经常对已排序的列表或几乎排序的列表进行排序。你正在迭代数组。在实际性能方面，大多数数据结构都很糟糕。通常由于缓存和内存布局，我们应该对这些事情不可知，但这很重要。您当前相关数据旁边的数据是，实际访问速度更快。如果我们已经知道我们要在列表中查找它的位置，我们可以更快地解决它（因为我们不必使用二分查找来找到它）。还有其他允许的技巧重复使用前面迭代中的信息。其他维度基本上是空闲的（除了那个值不收敛得更快，但这是因为球体中的随机分布点多于同一半径的圆）。

---

public class EuclideanNeighborSearch2D { 
    public static final int INVALID = -1; 
    static final Comparator<Point> xsort = new Comparator<Point>() { 
     @Override 
     public int compare(Point o1, Point o2) { 
      return Double.compare(o1.x, o2.x); 
     } 
    }; 
    static final Comparator<Point> ysort = new Comparator<Point>() { 
     @Override 
     public int compare(Point o1, Point o2) { 
      return Double.compare(o1.y, o2.y); 
     } 
    }; 

    ArrayList<Point> xaxis = new ArrayList<>(); 
    ArrayList<Point> yaxis = new ArrayList<>(); 

    boolean dirtySortX = false; 
    boolean dirtySortY = false; 

    public Point findNearest(float x, float y, float minDistance, float maxDistance) { 
     Point find = new Point(x,y); 

     sortXAxisList(); 
     sortYAxisList(); 

     double findingDistanceMaxSq = maxDistance * maxDistance; 
     double findingDistanceMinSq = minDistance * minDistance; 

     Point findingIndex = null; 

     int posx = Collections.binarySearch(xaxis, find, xsort); 
     int posy = Collections.binarySearch(yaxis, find, ysort); 
     if (posx < 0) posx = ~posx; 
     if (posy < 0) posy = ~posy; 

     int mask = 0b1111; 

     Point v; 

     double vx, vy; 
     int o; 
     int itr = 0; 
     while (mask != 0) { 
      if ((mask & (1 << (itr & 3))) == 0) { 
       itr++; 
       continue; //if that direction is no longer used. 
      } 
      switch (itr & 3) { 
       default: 
       case 0: //+x 
        o = posx + (itr++ >> 2); 
        if (o >= xaxis.size()) { 
         mask &= 0b1110; 
         continue; 
        } 
        v = xaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vx > findingDistanceMaxSq) { 
         mask &= 0b1110; 
         continue; 
        } 
        break; 
       case 1: //+y 
        o = posy + (itr++ >> 2); 
        if (o >= yaxis.size()) { 
         mask &= 0b1101; 
         continue; 
        } 
        v = yaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vy > findingDistanceMaxSq) { 
         mask &= 0b1101; 
         continue; 
        } 
        break; 
       case 2: //-x 
        o = posx + ~(itr++ >> 2); 
        if (o < 0) { 
         mask &= 0b1011; 
         continue; 
        } 
        v = xaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vx > findingDistanceMaxSq) { 
         mask &= 0b1011; 
         continue; 
        } 
        break; 
       case 3: //-y 
        o = posy + ~(itr++ >> 2); 
        if (o < 0) { 
         mask = mask & 0b0111; 
         continue; 
        } 
        v = yaxis.get(o); 
        vx = x - v.x; 
        vy = y - v.y; 
        vx *= vx; 
        vy *= vy; 
        if (vy > findingDistanceMaxSq) { 
         mask = mask & 0b0111; 
         continue; 
        } 
        break; 
      } 
      double d = vx + vy; 

      if (d <= findingDistanceMinSq) continue; 

      if (d < findingDistanceMaxSq) { 
       findingDistanceMaxSq = d; 
       findingIndex = v; 
      } 

     } 
     return findingIndex; 
    } 

    private void sortXAxisList() { 
     if (!dirtySortX) return; 
     Collections.sort(xaxis, xsort); 
     dirtySortX = false; 
    } 

    private void sortYAxisList() { 
     if (!dirtySortY) return; 
     Collections.sort(yaxis,ysort); 
     dirtySortY = false; 
    } 

    /** 
    * Called if something should have invalidated the points for some reason. 
    * Such as being moved outside of this class or otherwise updated. 
    */ 
    public void update() { 
     dirtySortX = true; 
     dirtySortY = true; 
    } 

    /** 
    * Called to add a point to the sorted list without needing to resort the list. 
    * @param p Point to add. 
    */ 
    public final void add(Point p) { 
     sortXAxisList(); 
     sortYAxisList(); 
     int posx = Collections.binarySearch(xaxis, p, xsort); 
     int posy = Collections.binarySearch(yaxis, p, ysort); 
     if (posx < 0) posx = ~posx; 
     if (posy < 0) posy = ~posy; 
     xaxis.add(posx, p); 
     yaxis.add(posy, p); 
    } 

    /** 
    * Called to remove a point to the sorted list without needing to resort the list. 
    * @param p Point to add. 
    */ 
    public final void remove(Point p) { 
     sortXAxisList(); 
     sortYAxisList(); 
     int posx = Collections.binarySearch(xaxis, p, xsort); 
     int posy = Collections.binarySearch(yaxis, p, ysort); 
     if (posx < 0) posx = ~posx; 
     if (posy < 0) posy = ~posy; 
     xaxis.remove(posx); 
     yaxis.remove(posy); 
    } 
} 

---

更新：关于，在评论中，k点问题。你会注意到很少有变化。唯一相关的是如果发现点v小于当前m（findingDistanceMaxSq），那么该点被添加到堆中，并且m的值被设置为等于发现位置和发现位置之间的欧几里德距离第k个元素。算法的常规版本可以被看作是k = 1的情况。我们搜索我们想要的1个元素，并且当发现v更接近时，我们更新m以等于唯一的（k = 1）元素。请记住，我只做过距离平方的距离比较，因为我只需要知道它是否离得更远，并且我不会浪费时钟周期在平方根函数上。

而且我知道有一个完美的数据结构，用于将k元素存储在大小有限的堆中。显然，数组插入不是最优的。但是，除了太多依赖java的apis之外，根本没有一个用于那个特定的类，尽管显然Google Guava做了一个。但是，考虑到这种可能性不大，你根本不会注意到你的k值可能不那么大。但是，它在k时间内存储的点中插入时间复杂性。还有一些东西像缓存元素距发现点的距离。

最后，也许最紧张的是，我用来测试代码的项目正处于转型阶段，所以我没有设法测试这个。但是，它肯定显示了你是如何做到的：迄今为止存储了k个最佳结果，并使m等于到第k个最近点的距离。 - 其他一切保持不变。

举例来源。

public static double distanceSq(double x0, double y0, double x1, double y1) { 
    double dx = x1 - x0; 
    double dy = y1 - y0; 
    dx *= dx; 
    dy *= dy; 
    return dx + dy; 
} 
public Collection<Point> findNearest(int k, final float x, final float y, float minDistance, float maxDistance) { 
    sortXAxisList(); 
    sortYAxisList(); 

    double findingDistanceMaxSq = maxDistance * maxDistance; 
    double findingDistanceMinSq = minDistance * minDistance; 
    ArrayList<Point> kpointsShouldBeHeap = new ArrayList<>(k); 
    Comparator<Point> euclideanCompare = new Comparator<Point>() { 
     @Override 
     public int compare(Point o1, Point o2) { 
      return Double.compare(distanceSq(x, y, o1.x, o1.y), distanceSq(x, y, o2.x, o2.y)); 
     } 
    }; 

    Point find = new Point(x, y); 
    int posx = Collections.binarySearch(xaxis, find, xsort); 
    int posy = Collections.binarySearch(yaxis, find, ysort); 
    if (posx < 0) posx = ~posx; 
    if (posy < 0) posy = ~posy; 

    int mask = 0b1111; 

    Point v; 

    double vx, vy; 
    int o; 
    int itr = 0; 
    while (mask != 0) { 
     if ((mask & (1 << (itr & 3))) == 0) { 
      itr++; 
      continue; //if that direction is no longer used. 
     } 
     switch (itr & 3) { 
      default: 
      case 0: //+x 
       o = posx + (itr++ >> 2); 
       if (o >= xaxis.size()) { 
        mask &= 0b1110; 
        continue; 
       } 
       v = xaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vx > findingDistanceMaxSq) { 
        mask &= 0b1110; 
        continue; 
       } 
       break; 
      case 1: //+y 
       o = posy + (itr++ >> 2); 
       if (o >= yaxis.size()) { 
        mask &= 0b1101; 
        continue; 
       } 
       v = yaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vy > findingDistanceMaxSq) { 
        mask &= 0b1101; 
        continue; 
       } 
       break; 
      case 2: //-x 
       o = posx + ~(itr++ >> 2); 
       if (o < 0) { 
        mask &= 0b1011; 
        continue; 
       } 
       v = xaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vx > findingDistanceMaxSq) { 
        mask &= 0b1011; 
        continue; 
       } 
       break; 
      case 3: //-y 
       o = posy + ~(itr++ >> 2); 
       if (o < 0) { 
        mask = mask & 0b0111; 
        continue; 
       } 
       v = yaxis.get(o); 
       vx = x - v.x; 
       vy = y - v.y; 
       vx *= vx; 
       vy *= vy; 
       if (vy > findingDistanceMaxSq) { 
        mask = mask & 0b0111; 
        continue; 
       } 
       break; 
     } 
     double d = vx + vy; 
     if (d <= findingDistanceMinSq) continue; 
     if (d < findingDistanceMaxSq) { 
      int insert = Collections.binarySearch(kpointsShouldBeHeap, v, euclideanCompare); 
      if (insert < 0) insert = ~insert; 
      kpointsShouldBeHeap.add(insert, v); 
      if (k < kpointsShouldBeHeap.size()) { 
       Point kthPoint = kpointsShouldBeHeap.get(k); 
       findingDistanceMaxSq = distanceSq(x, y, kthPoint.x, kthPoint.y); 
      } 
     } 
    } 
    //if (kpointsShouldBeHeap.size() > k) { 
    // kpointsShouldBeHeap.subList(0,k); 
    //} 
    return kpointsShouldBeHeap; 
}