Nearest Neighbor Search: Python

Thanks to John Vinyard for suggesting scipy. After some good research and testing, here is the solution to this question:

Prerequisites:
Install Numpy and SciPy

  1. Import the SciPy and Numpy Modules

  2. Make a copy of the 5 dimensional array including just the X and Y values.

  3. Create an instance of a cKDTree as such:

    YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
    #Play with the leafsize to get the fastest result for your dataset
    
  4. Query the cKDTree for the Nearest Neighbor within 6 units as such:

    for item in YourArray:
        TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)
    

    for each item in YourArray, TheResult will be a tuple of the distance between the two points, and the index of the location of the point in YourArray.

Leave a Comment