PackedTrees and OpTrees¶

Count how many nearby pairs can be formed.

Count the number of pairs (x1, x2) can be formed, with x1 drawn from self and x2 drawn from other, and where distance(x1, x2, p) <= r.

Data points on self and other are optionally weighted by the weights argument. (See below)

Parameters:

• other (OpTree) –

  The other tree to draw points from, can be the same tree as self

• r (float | NDArray) –

  The radius to produce a count for. Mulltiple radii are searched with a single tree traversal. If the count is non-cumulative (cumulative=False), r defines the edges of the bins, and must be non-decreasing

• p (float | None, default: None ) –

  Which Minkowski p-norm to use. Default 2.0. A finite large p may cause a ValueError if overflow can occur

• weights (tuple[float | None, float | None] | NDArray | None, default: None ) –

  If None, the pair-counting is unweighted. If given as a tuple, weights[0] is the weights of points in self, and weights[1] is the weights of points in other; either can be None to indicate the points are unweighted. If given as an array_like, weights is the weights of points in self and other. For this to make sense, self and other must be the same tree. If self and other are two different trees, a ValueError is raised. Default: None

• cumulative (bool | None, default: None ) –

  Whether the returned counts are cumulative. When cumulative is set to False the algorithm is optimized to work with a large number of bins (>10) specified by r. When cumulative is set to True, the algorithm is optimized to work with a small number of r. Default: True

Returns:

• result ( scalar or 1-D array ) –

  The number of pairs. For unweighted counts, the result is integer. For weighted counts, the result is float. If cumulative is False, result[i] contains the counts with (-inf if i == 0 else r[i-1]) < R <= r[i]

Raises:

• NotImplementedError –

Query the OpTree for nearest neighbors

Parameters:

• x (ArrayLike) –

  An array of points to query

• k (int | Sequence[int], default: 1 ) –

  Either the number of nearest neighbors to return or a list of the kth nearest neighbors to return, starting from 1. E.g., [2,3] will return the 2^nd and 3^rd nearest neighbors

• eps (float | None, default: None ) –

  Return approximate nearest neighbors; Note that this parameter is unused

• p (int | None, default: None ) –

  The Minkowski p-norm to use. 1 is the sum of absolute-values distance ("Manhattan" distance). 2 is the Euclidean distance. infinity is the maximum-coordinate-difference distance. Currently only p=2 is supported

• distance_upper_bound (float | None, default: None ) –

  Return only neighbors from other nodes within this distance. This is used for tree pruning, 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.

• workers (int | None, default: None ) –

  Number of workers to use for parallel processing. Only 1 is supported, for more, see Cubes

• return_data_indices (bool | None, default: None ) –

  Return indices into the sorted data if True instead of into the original. Specify None to have this set by the copy_data argument used during tree construction.

• return_sorted (bool | None, default: None ) –

  Flag to return the distances and indices in distance-sorted order. Set to False for a performance boost. Default True

Returns:

• d ( float or array of floats ) –

  The distances to the nearest neighbors. If x has shape tuple+(self.m,), then d has shape tuple+(k,). When k==1, the last dimension of the output is squeezed. Missing neighbors are indicated with infinite distances. Hits are sorted by distance (nearest first)

• i ( integer or array of integers ) –

  The index of each neighbor in self.data. i is the same shape as d. Missing neighbors are indicated with self.n.

Raises:

• NotImplementedError –

  if p!=2

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 ((array_like, float)) –

  The radius of points to return, must broadcast to the length of x.

• p (float, default: 2.0 ) –

  Which Minkowski p-norm to use. Should be in the range [1, inf]. A finite large p may cause a ValueError if overflow can occur.

• eps (nonnegative float, default: None ) –

  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).

• workers (int, default: -1 ) –

  Number of jobs to schedule for parallel processing. If -1 is given all processors are used. Default: -1. Note: SciPy's kdtree parallelizes across the number of points queried. Thus, querying on a single point gets no speed-up from parallelization. We parallelize on single point queries, thus the different default

• return_sorted (bool, default: False ) –

  Sorts returned indices if True and does not sort them if False. If None, does not sort single point queries, but does sort multi-point queries which was the behavior before this option was added. Default False.

• return_length (bool, default: False ) –

  Return the number of points inside the radius instead of a list of the indices. Note that this is much faster for large trees.

• return_lists (bool, default: False ) –

  Force returning lists instead of arrays. OpTrees return arrays of indices by default, but this doesn't match the expected query_ball_point signature. To exactly match SciPy, set this to True.

• return_data_indices (bool | None, default: None ) –

  Return indices into the sorted data if True instead of into the original. Specify None to have this set by the copy_data argument used during tree construction.

• strict (bool | None, default: None ) –

  If False, compare only the approximate node distance. Should be significantly faster, but may include some amount of false positives. Default True

Returns:

• results ( 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.

Examples:

>>> import numpy as np
>>> from packingcubes import OpTree
>>> x, y = np.mgrid[0:5, 0:5]
>>> points = np.c_[x.ravel(), y.ravel()]
>>> tree = OpTree(points)
>>> sorted(tree.query_ball_point([2, 0], 1))
[5, 10, 11, 15]

Query multiple points and plot the results:

>>> import matplotlib.pyplot as plt
>>> points = np.asarray(points)
>>> plt.plot(points[:,0], points[:,1], '.')
>>> for results in tree.query_ball_point(([2, 0], [3, 3]), 1):
...     nearby_points = points[results]
...     plt.plot(nearby_points[:,0], nearby_points[:,1], 'o')
>>> plt.margins(0.1, 0.1)
>>> plt.show()

Find all pairs of points between self and other whose distance is at most r.

Parameters:

• other (OpTree) –

  The tree containing points to search against

• r –

  The maximum distance, has to be positive

• p (float, default: 2 ) –

  Which Minkowski norm to use. p has to meet the condition 1 <= p <= infinity

• eps (float | None, default: None ) –

  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). eps has to be non-negative.

• strict (bool | None, default: None ) –

  If False, compare only the approximate node distance. Should be significantly faster, but may include substantial amounts of false positives. Default True

• return_lists (bool | None, default: None ) –

  Force returning lists instead of arrays. OpTrees return arrays of indices by default, but this doesn't match the expected query_ball_tree signature. For a slight performance increase, set this to False

• return_sorted (bool | None, default: None ) –

  Force returning sorted lists. If the copy_data flag was passed during tree construction, the data used to generate the results may be in a different order than originally imposed. For example, results[0] = [5, 1, 2]. If order of output is important, set this flag to True, at a performance penalty.

Returns:

• results ( list of lists ) –

  For each element self.data[i] of this tree, results[i] is a list of the indices of its neighbors in other.data

Raises:

• NotImplementedError –

  if p!=2

Find all pairs of points in self whose distance is at most r.

Parameters:

• r (float) –

  The maximum distance, has to be positive

• p (float, default: 2.0 ) –

  Which Minkowski norm to use. p has to meet the condition 1 <= p <= infinity

• eps (float | None, default: None ) –

  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). eps has to be non-negative.

• output_type (str | None, default: None ) –

  Choose the output container, 'set' or 'ndarray'. Default: 'set'

• strict (bool | None, default: None ) –

  If False, compare only the approximate node distance. Should be significantly faster, but may include substantial amounts of false positives. Default True

Returns:

• results ( set or NDArray ) –

  Set of pairs (i, j) with i<j, for which the corresponding positions are close. If output_type is 'ndarray', an ndarray is returned instead of a set.

Raises:

• NotImplementedError –

  if p!=2

Compute a sparse distance matrix

Computes a distance matrix between two OpTrees, leaving as zero any distance greater than max_distance.

Parameters:

• other (OpTree) –
• max_distance (float) –
• p (float | None, default: None ) –

  Which Minkowski p-norm to use. A finite large p may cause a ValueError if overflow can occur

• output_type (str | None, default: None ) –

  Which container to use for output data. Default: "dok_matrix"

Returns:

• result ( dok_matrix, coo_matrix, dict, or ndarray ) –

  Sparse matrix representing the results in a "dictionary of keys" format. If a dict is returned the keys are (i,j) tuples of indices. If output_type is "ndarray" a record array with fields "i", "j", and "v" is returned.

Raises:

• NotImplementedError –

Iterate through all nodes of the octree.

Note that no guarantee is made of what order the nodes are traversed in

Return the number of particles in the tree

Count how many nearby pairs can be formed.

Parameters:

• other (PackedTree) –

  The other tree to compare against

• r (float) –

  The radius to produce a count for.

Returns:

• result ( scalar or 1-d array ) –

  The number of pairs

Get nearest particle index (and distance) to point.

Parameters:

• xyz (ArrayLike) –

  Coordinates of point to check

• check_neighbors (bool, default: True ) –

  Flag to check whether we should look at neighbors of the smallest containing node. Default True

Returns:

• closest_ind ( int ) –

  Absolute index of closest particle

• closest_dist ( float ) –

  Distance to closest particle

Raises:

• NotImplementedError –

  This function is not implemented, see get_closest_particles instead

Get kth nearest particle distances and indices to point.

Parameters:

• data (DataContainer | Dataset) –

  Source of particle position data

• xyz (NDArray) –

  Coordinates of point to check

• distance_upper_bound (float | None, default: None ) –

  Return only neighbors from other nodes within this distance. This is used for tree pruning, 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.

• p (float, default: 2 ) –

  Which Minkowski p-norm to use. 1 is the sum of absolute-values distance ("Manhattan" distance). 2 is the usual Euclidean distance. Infinity is the maximum-coordinate-difference distance. Currently, only p=2 is supported.

• k (int, default: 1 ) –

  Number of closest particles to return. Default 1

• use_data_indices (bool, default: True ) –

  Flag to return indices into the sorted dataset (True, default) or into the shuffle list (False)

• return_sorted (bool, default: True ) –

  Flag to return the distances and indices in distance-sorted order. Set to False for a performance boost. Default True

Returns:

• distances ( NDArray[float] ) –

  Distances to the kth nearest neighbors. Has shape (min(N,k),), where N is the number of particles in the sphere bounded by distance_upper_bound

• indices ( NDArray[int] ) –

  Indices in data of the kth nearest neighbors. Has same shape as distances

Raises:

• NotImplementedError –

  If a p value of then 2 is provided

Return a list of all leaf octree nodes in depth-first order

Return the node corresponding to the provided tag or None if not found.

Parameters:

• tag (str) –

  The tag to search for

Returns:

• node –

  Node in octree with specified tag or None if it does not exist

Return all particles contained within the box.

Parameters:

• data (DataContainer | Dataset) –

  Dataset containing the particle positions. Pass a DataContainer object for a slight performance increase

• box (BoxLike) –

  Box to check

• strict (bool, default: False ) –

  Flag to specify whether only particles inside box will be returned. If False (default), additional nearby particles may be included for signficantly increased performance

Returns:

• indices ( NDArray[int]] ) –

  List of original particle indices contained within sphere

Return all particles contained within sphere defined by center and radius.

Parameters:

• data (DataContainer | Dataset) –

  Dataset containing the particle positions. Pass a DataContainer object for a slight performance increase

• center (NDArray) –

  Center point of the sphere

• radius (float) –

  Radius of the sphere

• strict (bool, default: False ) –

  Flag to specify whether only particles inside the sphere will be returned. If False (default), additional nearby particles may be included for signficantly increased performance

Returns:

• indices ( NDArray[int] ) –

  List of original particle indices contained within sphere

Return all particles contained within the box.

Parameters:

• box (BoxLike) –

  Box to check

Returns:

• indices ( list[tuple[int, int]] ) –

  List of particle start-stop indices contained within sphere Third element of each tuple is a flag for whether only some particles (1) among the start-stop indices are contained or all (0)

Return all particles contained within sphere defined by center and radius.

Parameters:

• center (NDArray) –

  Center point of the sphere

• radius (float) –

  Radius of the sphere

Returns:

• indices ( list[tuple[int, int, int]] ) –

  List of particle start-stop indices contained within sphere Third element of each tuple is a flag for whether only some particles (1) among the start-stop indices are contained or all (0)