Nearest Neighbors

KDTree(points, max_leaf_size=10, strategy='fast')

Implementation of a kd-tree for space partitionning and fast nearest point queries.

Parameters:

Name	Type	Description	Default
points	ndarray	array of points (shape (N,d)) to consider. Can be of any dimension d, though the kd-tree algorithm have poor performance when the dimension grows.	required
max_leaf_size	int	Maximum number of points inside a leaf. Defaults to 10.	10
strategy	str	Node splitting strategy. Can be either 'fast', 'balanced' or 'random'. Defaults to "fast".	'fast'

Raises:

Type	Description
Exception	fails if the points are not of the correct (N,d) shape.

query(pt, k=1)

Query the tree to find the k nearest neighbors of point 'pt'

Parameters:

Name	Type	Description	Default
pt	Vec	the position to query	required
k	int	number of nearest points to query. Defaults to 1.	1

Returns:

Name	Type	Description
list	list	the indices of the k nearest points of 'pt' in increasing distance order

query_radius(pt, r)

Query the tree to find all points that are at distance <= r from the position 'pt'.

Parameters:

Name	Type	Description	Default
pt	Vec	the position to query	required
r	float	radius of the query ball	required

Returns:

Name	Type	Description
list	list	all indices of points that are at distance at most r from the query point.