KDTree

class compas.geometry.KDTree(objects=None)[source]

Bases: object

A tree for nearest neighbor search in a k-dimensional space.

Parameters

objects (list, optional) – A list of objects to populate the tree with. If objects are provided, the tree is built automatically. Defaults to None.

Attributes

root (Node) – The root node of the built tree. This is the median with respect to the different dimensions of the tree.

Notes

For more info, see 1 and 2.

References

1

Wikipedia. k-d tree. Available at: https://en.wikipedia.org/wiki/K-d_tree.

2

Dell’Amico, M. KD-Tree for nearest neighbor search in a K-dimensional space (Python recipe). Available at: http://code.activestate.com/recipes/577497-kd-tree-for-nearest-neighbor-search-in-a-k-dimensional-space/.

Examples

>>>

Methods

build	Populate a kd-tree with given objects.
nearest_neighbor	Find the nearest neighbor to a given point, excluding neighbors that have already been found.
nearest_neighbors	Find the N nearest neighbors to a given point.