PeriodicCKDTree

class sknano.core.analysis.PeriodicCKDTree(data, boxsize=None, leafsize=10)

Bases: scipy.spatial.cKDTree

Cython kd-tree for quick nearest-neighbor lookup with periodic boundaries

See scipy.spatial.ckdtree for details on kd-trees.

Searches with periodic boundaries are implemented by mapping all initial data points to one canonical periodic image, building an ordinary kd-tree with these points, then querying this kd-tree multiple times, if necessary, with all the relevant periodic images of the query point.

Note that to ensure that no two distinct images of the same point appear in the results, it is essential to restrict the maximum distance between a query point and a data point to half the smallest box dimension.

Attributes

boxsize
data
indices
leafsize
m
maxes
mins
n
tree

Methods

count_neighbors(self, other, r[, p])	Count how many nearby pairs can be formed.
query(x[, k, eps, p, distance_upper_bound])	Query the kd-tree for nearest neighbors
query_ball_point(x, r[, p, eps])	Find all points within distance r of point(s) x.
query_ball_tree(self, other, r[, p, eps])	Find all pairs of points whose distance is at most r
query_pairs(self, r[, p, eps])	Find all pairs of points whose distance is at most r.
sparse_distance_matrix(self, other, max_distance)	Compute a sparse distance matrix

Methods Summary

query(x[, k, eps, p, distance_upper_bound])	Query the kd-tree for nearest neighbors
query_ball_point(x, r[, p, eps])	Find all points within distance r of point(s) x.

Methods Documentation

query(x, k=1, eps=0, p=2, distance_upper_bound=inf)

Query the kd-tree for nearest neighbors

Parameters:

• x (array_like, last dimension self.m) – An array of points to query.
• k (integer) – The number of nearest neighbors to return.
• eps (non-negative float) – Return approximate nearest neighbors; the kth returned value is guaranteed to be no further than (1+eps) times the distance to the real k-th nearest neighbor.
• p (float, 1<=p<=infinity) – Which Minkowski p-norm to use. 1 is the sum-of-absolute-values “Manhattan” distance 2 is the usual Euclidean distance infinity is the maximum-coordinate-difference distance
• distance_upper_bound (nonnegative float) – Return only neighbors within this distance. This is used to prune tree searches, so if you are doing a series of nearest-neighbor queries, it may help to supply the distance to the nearest neighbor of the most recent point.

Returns:

• d (array of floats) – The distances to the nearest neighbors. If x has shape tuple+(self.m,), then d has shape tuple+(k,). Missing neighbors are indicated with infinite distances.
• i (ndarray of ints) – The locations of the neighbors in self.data. If x has shape tuple+(self.m,), then i has shape tuple+(k,). Missing neighbors are indicated with self.n.

query_ball_point(x, r, p=2.0, eps=0)

Find all points within distance r of point(s) x.

Parameters:

• x (array_like, shape tuple + (self.m,)) – The point or points to search for neighbors of.
• r (positive float) – The radius of points to return.
• p (float, optional) – Which Minkowski p-norm to use. Should be in the range [1, inf].
• eps (nonnegative float, optional) – Approximate search. Branches of the tree are not explored if their nearest points are further than r / (1 + eps), and branches are added in bulk if their furthest points are nearer than r * (1 + eps).

Returns:

results – If x is a single point, returns a list of the indices of the neighbors of x. If x is an array of points, returns an object array of shape tuple containing lists of neighbors.

Return type:

list or array of lists

Notes

If you have many points whose neighbors you want to find, you may save substantial amounts of time by putting them in a PeriodicCKDTree and using query_ball_tree.