Note
Go to the end to download the full example code.
12.3.10.9.2. Nearest neighbors#
import numpy as np
from scipy import spatial
Make a grid of 0:9 in X and 0:20 in Y.
[X, Y] = np.meshgrid(range(0, 10), range(0, 20))
Make one XY array [10*20 x 2] where each line is the x, y position of one point.
XY = np.vstack([X.flatten(), Y.flatten()]).transpose()
Make the fast search tree.
kdtree = spatial.cKDTree(XY, leafsize=4)
Choose some random points in the grid and get the 8 nearest neighbours.
rand = np.random.randint(0, XY.shape[1], size=(20,))
for r in rand:
# random point:
point = XY[r, :]
# query the 8 nearest neighbours with an euclidean distance
[dists, indices] = kdtree.query(point, k=8, p=2)
print("Nearest points to point:", point)
print("------------------------------------------")
for idx in range(0, len(indices)):
print(" ", idx, ".:", XY[indices[idx], :], " -> dist:", dists[idx])
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [0 0]
------------------------------------------
0 .: [0 0] -> dist: 0.0
1 .: [1 0] -> dist: 1.0
2 .: [0 1] -> dist: 1.0
3 .: [1 1] -> dist: 1.4142135623730951
4 .: [2 0] -> dist: 2.0
5 .: [0 2] -> dist: 2.0
6 .: [1 2] -> dist: 2.23606797749979
7 .: [2 1] -> dist: 2.23606797749979
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [0 0]
------------------------------------------
0 .: [0 0] -> dist: 0.0
1 .: [1 0] -> dist: 1.0
2 .: [0 1] -> dist: 1.0
3 .: [1 1] -> dist: 1.4142135623730951
4 .: [2 0] -> dist: 2.0
5 .: [0 2] -> dist: 2.0
6 .: [1 2] -> dist: 2.23606797749979
7 .: [2 1] -> dist: 2.23606797749979
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [0 0]
------------------------------------------
0 .: [0 0] -> dist: 0.0
1 .: [1 0] -> dist: 1.0
2 .: [0 1] -> dist: 1.0
3 .: [1 1] -> dist: 1.4142135623730951
4 .: [2 0] -> dist: 2.0
5 .: [0 2] -> dist: 2.0
6 .: [1 2] -> dist: 2.23606797749979
7 .: [2 1] -> dist: 2.23606797749979
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [0 0]
------------------------------------------
0 .: [0 0] -> dist: 0.0
1 .: [1 0] -> dist: 1.0
2 .: [0 1] -> dist: 1.0
3 .: [1 1] -> dist: 1.4142135623730951
4 .: [2 0] -> dist: 2.0
5 .: [0 2] -> dist: 2.0
6 .: [1 2] -> dist: 2.23606797749979
7 .: [2 1] -> dist: 2.23606797749979
Nearest points to point: [0 0]
------------------------------------------
0 .: [0 0] -> dist: 0.0
1 .: [1 0] -> dist: 1.0
2 .: [0 1] -> dist: 1.0
3 .: [1 1] -> dist: 1.4142135623730951
4 .: [2 0] -> dist: 2.0
5 .: [0 2] -> dist: 2.0
6 .: [1 2] -> dist: 2.23606797749979
7 .: [2 1] -> dist: 2.23606797749979
Nearest points to point: [0 0]
------------------------------------------
0 .: [0 0] -> dist: 0.0
1 .: [1 0] -> dist: 1.0
2 .: [0 1] -> dist: 1.0
3 .: [1 1] -> dist: 1.4142135623730951
4 .: [2 0] -> dist: 2.0
5 .: [0 2] -> dist: 2.0
6 .: [1 2] -> dist: 2.23606797749979
7 .: [2 1] -> dist: 2.23606797749979
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [0 0]
------------------------------------------
0 .: [0 0] -> dist: 0.0
1 .: [1 0] -> dist: 1.0
2 .: [0 1] -> dist: 1.0
3 .: [1 1] -> dist: 1.4142135623730951
4 .: [2 0] -> dist: 2.0
5 .: [0 2] -> dist: 2.0
6 .: [1 2] -> dist: 2.23606797749979
7 .: [2 1] -> dist: 2.23606797749979
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Nearest points to point: [1 0]
------------------------------------------
0 .: [1 0] -> dist: 0.0
1 .: [0 0] -> dist: 1.0
2 .: [1 1] -> dist: 1.0
3 .: [2 0] -> dist: 1.0
4 .: [0 1] -> dist: 1.4142135623730951
5 .: [2 1] -> dist: 1.4142135623730951
6 .: [3 0] -> dist: 2.0
7 .: [1 2] -> dist: 2.0
Total running time of the script: (0 minutes 0.011 seconds)