scipy.spatial.KDTree¶

class
scipy.spatial.
KDTree
(data, leafsize=10)[source]¶ kdtree for quick nearestneighbor lookup
This class provides an index into a set of kdimensional points which can be used to rapidly look up the nearest neighbors of any point.
Parameters: data : (N,K) array_like
The data points to be indexed. This array is not copied, and so modifying this data will result in bogus results.
leafsize : int, optional
The number of points at which the algorithm switches over to bruteforce. Has to be positive.
Raises: RuntimeError
The maximum recursion limit can be exceeded for large data sets. If this happens, either increase the value for the leafsize parameter or increase the recursion limit by:
>>> import sys >>> sys.setrecursionlimit(10000)
Notes
The algorithm used is described in Maneewongvatana and Mount 1999. The general idea is that the kdtree is a binary tree, each of whose nodes represents an axisaligned hyperrectangle. Each node specifies an axis and splits the set of points based on whether their coordinate along that axis is greater than or less than a particular value.
During construction, the axis and splitting point are chosen by the “sliding midpoint” rule, which ensures that the cells do not all become long and thin.
The tree can be queried for the r closest neighbors of any given point (optionally returning only those within some maximum distance of the point). It can also be queried, with a substantial gain in efficiency, for the r approximate closest neighbors.
For large dimensions (20 is already large) do not expect this to run significantly faster than brute force. Highdimensional nearestneighbor queries are a substantial open problem in computer science.
The tree also supports allneighbors queries, both with arrays of points and with other kdtrees. These do use a reasonably efficient algorithm, but the kdtree is not necessarily the best data structure for this sort of calculation.
Methods
count_neighbors
(other, r[, p])Count how many nearby pairs can be formed. innernode
(split_dim, split, less, greater)leafnode
(idx)node
query
(x[, k, eps, p, distance_upper_bound])Query the kdtree for nearest neighbors query_ball_point
(x, r[, p, eps])Find all points within distance r of point(s) x. query_ball_tree
(other, r[, p, eps])Find all pairs of points whose distance is at most r query_pairs
(r[, p, eps])Find all pairs of points within a distance. sparse_distance_matrix
(other, max_distance)Compute a sparse distance matrix