package OCADml
Library
Module
Module type
Parameter
Class
Class type
Construction of 2d vector space partitioning ball tree structures for nearest neighbour search. Implementation adapted from the BOSL2 vectors module.
Construction of these trees should be O(n log n) and searches should be O(log n), though real life performance depends on how the data is distributed. Thus, this structure is primarily useful when performing many searches of the same data. Below a certain number of points, it may be better to perform a direct search.
t.%(idx)
Indexed access to vectors/points used to build the ball tree t.
points t
Return a list of the vectors/points used to build the ball tree t.
points' t
Return a copied array of the vectors/points used to build the ball tree t.
make ?leaf_size pts
Build a ball tree from the list of vectors pts. Recursive construction of the tree will cease branching when a node holds a number of points less than or equal to leaf_size.
make' ?leaf_size pts
Build a ball tree from the array of vectors pts. Recursive construction of the tree will cease branching when a node holds a number of points less than or equal to leaf_size.
search_idxs ?radius t p
Search through the ball tree t for points that are within a distance radius of the target point p. Matches are returned as an arbitrarily ordered list of indices (into the point array used to construct t).