kd

Documentation

Overview

Package kd implements a k-D tree with arbitrary data packing and duplicate data coordinate support.

k-D trees are generally a cacheing layer representation of the local state -- we do not expect to be making frequent mutations to this tree once constructed.

Read operations on this k-D tree may be done in parallel. Mutations on the k-D tree must be done serially.

N.B.: Mutating the data point positions must be accompanied by mutating the k-D tree. For large numbers of points, and for a large number of queries, the time taken to build the tree will be offset by the speedup of subsequent reads.

Index

• func Data[T point.P](t *KD[T]) []T
• func KNN[T point.P](t *KD[T], p vector.V, k int, f filter.F[T]) []T
• func RangeSearch[T point.P](t *KD[T], q hyperrectangle.R, f filter.F[T]) []T
• type KD
  • func New[T point.P](o O[T]) *KD[T]
  • func (t *KD[T]) Balance()
  • func (t *KD[T]) Insert(p T)
  • func (t *KD[T]) Remove(v vector.V, f filter.F[T]) (T, bool)
• type O

Functions

func Data

func Data[T point.P](t *KD[T]) []T

Data returns all points in the k-D tree.

This k-D tree implementation supports concurrent read operations.

func KNN

func KNN[T point.P](t *KD[T], p vector.V, k int, f filter.F[T]) []T

KNN returns the k nearest neighbors to the input vector p and matches the filter function.

This k-D tree implementation supports concurrent read operations.

func RangeSearch

func RangeSearch[T point.P](t *KD[T], q hyperrectangle.R, f filter.F[T]) []T

RangeSearch returns all points which are found in the given bounds and matches the filter function.

This k-D tree implementation supports concurrent read operations.

Types

type KD

type KD[T point.P] struct {
	// contains filtered or unexported fields
}

func New

func New[T point.P](o O[T]) *KD[T]

func (*KD[T]) Balance

func (t *KD[T]) Balance()

Balance reconstructs the k-D tree.

This k-D tree implementation does not support concurrent mutations.

func (*KD[T]) Insert

func (t *KD[T]) Insert(p T)

Insert adds a new point into the k-D tree.

Insert is not a balanced operation -- after many mutations, the tree should be explicitly reconstructed.

This k-D tree implementation does not support concurrent mutations.

func (*KD[T]) Remove

func (t *KD[T]) Remove(v vector.V, f filter.F[T]) (T, bool)

Remove pops a point from the k-D tree which lies at the input vector v and matches the filter. Note that if multiple points match both the location vector and the filter, an arbitrary one will be removed. This function will pop at most one element from the k-D tree.

Remove is not a balanced operation -- after many mutations, the tree should be explicitly reconstructed.

This k-D tree implementation does not support concurrent mutations.

If there is no matching point, the returned bool will be false.

type O

type O[T point.P] struct {
	Data []T
	K    vector.D

	// N is the nominal leaf size of the k-D tree. Leaf nodes are checked
	// via bruteforce methods.
	//
	// Note that individual nodes (including non-leaf nodes) may contain
	// elements that exceed this size constraint after inserts and removes.
	//
	// Leaf size will significantly impact performance -- users should
	// tailor this value to their specific use-case. We recommend setting
	// this value to 16 and up as the size of the data set increases.
	N int
}