package OCADml

  1. Overview
  2. Docs

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.

type t

Ball Tree structure.

val (.%()) : t -> int -> V2.t

t.%(idx)

Indexed access to vectors/points used to build the ball tree t.

val points : t -> V2.t list

points t

Return a list of the vectors/points used to build the ball tree t.

val points' : t -> V2.t array

points' t

Return a copied array of the vectors/points used to build the ball tree t.

val make : ?leaf_size:int -> V2.t list -> 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.

val make' : ?leaf_size:int -> V2.t array -> t

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.

val search_idxs : ?radius:float -> t -> V2.t -> int list

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

val search_points : ?radius:float -> t -> V2.t -> V2.t list

search_points ?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 (not sorted from nearest to furthest) list of points.