KDTree

class compas.geometry.KDTree

Bases: object

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

Parameters:

objectssequence[[float, float, float] | compas.geometry.Point], optional

A list of objects to populate the tree with. If objects are provided, the tree is built automatically. Otherwise, use build().

Attributes:

rootNode

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.