A vantage point tree.

Quality of the constructed tree. Tree construction takes more time with higher quality. Tree query time takes less time with higher tree quality. If you have 100k or more points, use a Good or Random tree.

create quality points create a vantage point tree of given quality containing all points.

nearest_neighbor p vpt return the distance along with the nearest neighbor to query point p in vpt. Warning: there may be several points at this distance from p in vpt, but a single (arbitrary) one is returned. If you are not happy with that, use a point type that is deduplicated (i.e. a point that holds the info for all points with the same coordinates).

neighbors p tol vpt return all points in vpt within tol distance from query point p. I.e. all points returned are within (d <= tol) distance from p.

to_list vpt return the list of points in vpt.

is_empty vpt test if vpt is empty.

find query tree return the first point with distance to query = 0.0.

• raises [Not_found]

  if no such element exists. Warning: there may be several points at this distance from p in vpt, but a single (arbitrary) one is returned.

mem query tree return true if query can be found in tree; false otherwise.

root tree return the root point of the tree.

• raises [Not_found]

  if tree is empty.

check tree test the tree invariant. Should always be true. If invariant doesn't hold, then this library has a bug (or your distance function is not a proper metric).

remove quality query tree return an updated tree where the first element with distance = 0.0 to query was removed. The sub-tree that is reconstructed upon removal of query uses the specified quality.

• raises [Not_found]

  if not (mem query tree).