periodic_kdtree

This is the periodicCKDTree class written by Patrick Varilly.

Some minor modifications were done to make it work with Python 3

See https://github.com/patvarilly/periodic_kdtree

Classes

class periodic_kdtree.PeriodicCKDTree(bounds, data, leafsize=10)

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.

Parameters:
  • bounds – array_like, shape (k,) Size of the periodic box along each spatial dimension. A negative or zero size for dimension k means that space is not periodic along k.
  • data – array-like, shape (n,m) The n data points of dimension mto be indexed. This array is not copied unless this is necessary to produce a contiguous array of doubles, and so modifying this data will result in bogus results.
  • leafsize – positive integer The number of points at which the algorithm switches over to brute-force.
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:

list or array of lists 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.
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.