Skip to main content

Class: KdTree<T>

A k-dimensional search tree.

Type parameters

Name
T

Constructors

constructor

new KdTree<T>(dimensionCount, keyFunc): KdTree<T>

Constructor.

Type parameters

Name
T

Parameters

NameTypeDescription
dimensionCountnumberThe number of dimensions supported by this tree. If this argument is not an integer, it will be truncated to one.
keyFunc(element: T, out: Float64Array) => Float64ArrayA function which generates keys from elements. Keys are an N-tuple of numbers, where N is equal to the dimension count of this tree.

Returns

KdTree<T>

Throws

Error if the dimension count is less than 2.

Defined in

src/sdk/utils/datastructures/KdTree.ts:83

Properties

dimensionCount

Readonly dimensionCount: number

Defined in

src/sdk/utils/datastructures/KdTree.ts:54

Accessors

size

get size(): number

The number of elements in this tree.

Returns

number

Defined in

src/sdk/utils/datastructures/KdTree.ts:71

Methods

clear

clear(): void

Removes all elements from this tree.

Returns

void

Defined in

src/sdk/utils/datastructures/KdTree.ts:591


insert

insert(element): void

Inserts an element into this tree. This operation will trigger a rebalancing if, after the insertion, the length of this tree's longest branch is more than twice the length of the shortest branch.

Parameters

NameTypeDescription
elementTThe element to insert.

Returns

void

Defined in

src/sdk/utils/datastructures/KdTree.ts:319


insertAll

insertAll(elements): void

Inserts a batch of elements into this tree. This tree will be rebalanced after the elements are inserted.

Parameters

NameTypeDescription
elementsIterable<T>An iterable of the elements to insert.

Returns

void

Defined in

src/sdk/utils/datastructures/KdTree.ts:337


rebuild

rebuild(): void

Rebuilds and balances this tree.

Returns

void

Defined in

src/sdk/utils/datastructures/KdTree.ts:486


remove

remove(element): boolean

Removes an element from this tree. This tree will be rebalanced after the element is removed.

Parameters

NameTypeDescription
elementTThe element to remove.

Returns

boolean

Whether the element was removed.

Defined in

src/sdk/utils/datastructures/KdTree.ts:393


removeAll

removeAll(elements): boolean

Removes a batch of elements from this tree. This tree will be rebalanced after the elements are removed.

Parameters

NameTypeDescription
elementsIterable<T>An iterable of the elements to remove.

Returns

boolean

Whether at least one element was removed.

Defined in

src/sdk/utils/datastructures/KdTree.ts:409


removeAndInsert

removeAndInsert(toRemove, toInsert): void

Removes elements from this tree, then inserts elements into this tree as a single operation. The tree will be rebalanced at the end of the operation.

Using this method is more efficient than calling removeAll() and insertAll() separately.

Parameters

NameTypeDescription
toRemoveIterable<T>An iterable of the elements to remove.
toInsertIterable<T>An iterable of the elements to insert.

Returns

void

Defined in

src/sdk/utils/datastructures/KdTree.ts:470


search(element, radius, visitor): void

Searches this tree for elements whose keys are located near the key of a query element and visits each of them with a function.

Parameters

NameTypeDescription
elementTThe query element.
radiusnumberThe radius around the query element's key to search.
visitorKdTreeSearchVisitor<T>A visitor function. This function will be called once per element found within the search radius. If the visitor returns true, then the search will continue; if the visitor returns false, the search will immediately halt.

Returns

void

Defined in

src/sdk/utils/datastructures/KdTree.ts:153

search(element, radius, maxResultCount, out, filter?): T[]

Searches this tree for elements whose keys are located near the key of a query element and returns them in order of increasing distance from the query key.

Parameters

NameTypeDescription
elementTThe query element.
radiusnumberThe radius around the query key to search.
maxResultCountnumberThe maximum number of search results to return.
outT[]An array in which to store the search results.
filter?KdTreeSearchFilter<T>A function to filter the search results.

Returns

T[]

An array containing the search results, in order of increasing distance from the query key.

Defined in

src/sdk/utils/datastructures/KdTree.ts:164


searchKey

searchKey(key, radius, visitor): void

Searches this tree for elements whose keys are located near a query key and visits each of them with a function.

Parameters

NameTypeDescription
keyReadonly<Omit<Float64Array, "set" | "sort" | "copyWithin">>The query key.
radiusnumberThe radius around the query key to search.
visitorKdTreeSearchVisitor<T>A visitor function. This function will be called once per element found within the search radius. If the visitor returns true, then the search will continue; if the visitor returns false, the search will immediately halt.

Returns

void

Defined in

src/sdk/utils/datastructures/KdTree.ts:123

searchKey(key, radius, maxResultCount, out, filter?): T[]

Searches this tree for elements whose keys are located near a query key and returns them in order of increasing distance from the query key.

Parameters

NameTypeDescription
keyReadonly<Omit<Float64Array, "set" | "sort" | "copyWithin">>The query key.
radiusnumberThe radius around the query key to search.
maxResultCountnumberThe maximum number of search results to return.
outT[]An array in which to store the search results.
filter?KdTreeSearchFilter<T>A function to filter the search results.

Returns

T[]

An array containing the search results, in order of increasing distance from the query key.

Defined in

src/sdk/utils/datastructures/KdTree.ts:134