找到每個點的最近點（最近的鄰居）

Question

我正在寫一個方法，它將一個點數組作爲輸入，併爲數組中的每個點找到除它自身以外的最近點。我目前正在以一種蠻橫的方式來做這件事（每隔一點就對每一點都進行討論）。我目前的implimentation沒有數組排序，但我可以使用CompareByX方法通過p.x值進行排序。我非常喜歡算法的運行時間，而且它的n值很大，所以非常耗時。我對這個主題並不十分了解，並且對不同類型的數據結構非常瞭解，任何簡單的幫助都會很棒！

我當前的代碼是：

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class My2dPoint { 
    double x; 
    double y; 

    public My2dPoint(double x1, double y1) { 
    x=x1; 
    y=y1; 
    } 

} 


class CompareByX implements Comparator<My2dPoint> { 
    public int compare(My2dPoint p1, My2dPoint p2) { 
    if (p1.x < p2.x) return -1; 
     if (p1.x == p2.x) return 0; 
     return 1; 
    } 
} 

    /* An object of the above comparator class is used by java.util.Arrays.sort() in main to sort an array of points by x-coordinates */ 

class Auxiliaries { 

    public static double distSquared(My2dPoint p1, My2dPoint p2) { 
     double result; 
     result = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y); 
     return result; 
    } 

} 

public class HW3 { 
    public static void main (String argv []) throws IOException { 
     int range = 1000000; // Range of x and y coordinates in points 

     System.out.println("Enter the number of points"); 

     InputStreamReader reader1 = new InputStreamReader(System.in); 
     BufferedReader buffer1 = new BufferedReader(reader1); 
     String npoints = buffer1.readLine(); 
     int numpoints = Integer.parseInt(npoints); 

     // numpoints is now the number of points we wish to generate 

     My2dPoint inputpoints [] = new My2dPoint [numpoints]; 

     // array to hold points 

     int closest [] = new int [numpoints]; 

     // array to record soln; closest[i] is index of point closest to i'th 

     int px, py; 
     double dx, dy, dist; 
     int i,j; 
     double currbest; 
     int closestPointIndex; 
     long tStart, tEnd; 

     for (i = 0; i < numpoints; i++) { 

      px = (int) (range * Math.random()); 
      dx = (double) px; 
      py = (int) (range * Math.random()); 
      dy = (double) py; 
      inputpoints[i] = new My2dPoint(dx, dy); 

     } 

     // array inputpoints has now been filled 



     tStart = System.currentTimeMillis(); 

     // find closest [0] 


     closest[0] = 1; 
     currbest = Auxiliaries.distSquared(inputpoints[0],inputpoints[1]); 
     for (j = 2; j < numpoints; j++) { 
      dist = Auxiliaries.distSquared(inputpoints[0],inputpoints[j]); 
      if (dist < currbest) { 
       closest[0] = j; 
       currbest = dist; 
      } 
     } 

     // now find closest[i] for every other i 

     for (i = 1; i < numpoints; i++) { 
      closest[i] = 0; 
      currbest = Auxiliaries.distSquared(inputpoints[i],inputpoints[0]); 
      for (j = 1; j < i; j++) { 
       dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]); 
       if (dist < currbest) { 
       closest[i] = j; 
       currbest = dist; 
      } 
      } 

      for (j = i+1; j < numpoints; j++) { 
       dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]); 
       if (dist < currbest) { 
      closest[i] = j; 
        currbest = dist; 
      } 
      } 
     } 

     tEnd = System.currentTimeMillis(); 
     System.out.println("Time taken in Milliseconds: " + (tEnd - tStart)); 
    } 
} 

Answer 1

的近鄰搜索強力只是一個小點的數量是可行的。

您可能希望查看kd-Trees或空間數據結構。

Here is a demo for kd-Tree. This is what wikipedia says.

Answer 2

我鐵定排序X第一。然後，我將使用點之間的x距離作爲快速拒絕測試：一旦你有一個鄰居的距離，任何更近的鄰居必須靠近x。這避免了x範圍之外的點的所有distSquared計算。每當你找到一個更近的鄰居時，你也會收緊你需要搜索的x的範圍。另外，如果P2是最接近P1的鄰居，那麼我將使用P1作爲P2的最近鄰居的初始猜測。

編輯：關於第二個想法，我按任何尺寸排序最大的範圍。

Answer 3

有一些相當標準的方法來改善這種搜索，並且想要得到多麼複雜取決於您正在搜索的點數。

一個相當普遍的簡單方法是用X或Y對點進行排序。然後，對於每個點，您可以查找近點，在數組中向前和向後。記住你找到的距離最近的那個距離有多遠，並且當X（或Y）的差別大於你知道的差距時，就不會有任何可找到的更近的點。

您還可以使用樹來劃分您的空間。維基百科有a page that gives some possible algorithms。有時，設置它們的成本比您節省的成本要大。這是你必須根據你正在搜索的點數來決定的事情。

Answer 4

可以使用kd-tree，也可以使用良好的庫來進行最近鄰居搜索。 Weka包括一個。

Answer 5

另一種可能性，比創建kd樹更簡單，它使用鄰域矩陣。

首先將所有點放入二維方陣中。然後，您可以運行全部或部分空間排序，因此點將在矩陣內排序。

具有小Y的點可以移動到矩陣的頂行，同樣，具有大Y的點也會移動到底行。對於X座標較小的點也會發生同樣的情況，這應該移動到左側的列上。並且對稱地，X值較大的點將轉到右側的列。

在完成空間排序之後（有很多方法可以通過串行或並行算法實現這一點），您可以通過訪問實際存儲點P的相鄰單元來查找給定點P的最近點鄰域矩陣。

您可以閱讀這一想法在下面的紙張的詳細信息（你會在網上找到的這PDF份）：基於自發行爲在GPU 超大質量的羣組模擬。

排序步驟爲您提供了有趣的選擇。您可以使用本文中描述的奇偶換位排序，這很容易實現（甚至可能在CUDA中）。如果你只運行一次，它會給你一個部分排序，如果你的矩陣是近似排序的，這可能已經很有用。也就是說，如果你的積分緩慢移動，它會爲你節省很多計算。

如果你需要一個完整的排序，你可以運行這樣的奇偶換位通過多次（如下面的維基百科頁面描述）：

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

如果變化很小，一個或兩個偶數次傳遞足以讓數組重新排序。