最近鄰居算法

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