Skip to main content

Class: KdTree<T>

Defined in: src/sdk/utils/datastructures/KdTree.ts:53

A k-dimensional search tree.

Type Parameters

Type Parameter
T

Constructors

Constructor

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

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

Constructor.

Parameters

ParameterTypeDescription
dimensionCountnumberThe number of dimensions supported by this tree. If this argument is not an integer, it will be truncated to one.
keyFunc(element, out) => 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.

Properties

dimensionCount

readonly dimensionCount: number

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

Accessors

size

Get Signature

get size(): number

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

The number of elements in this tree.

Returns

number

Methods

clear()

clear(): void

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

Removes all elements from this tree.

Returns

void


insert()

insert(element): void

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

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

ParameterTypeDescription
elementTThe element to insert.

Returns

void


insertAll()

insertAll(elements): void

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

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

Parameters

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

Returns

void


rebuild()

rebuild(): void

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

Rebuilds and balances this tree.

Returns

void


remove()

remove(element): boolean

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

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

Parameters

ParameterTypeDescription
elementTThe element to remove.

Returns

boolean

Whether the element was removed.


removeAll()

removeAll(elements): boolean

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

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

Parameters

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

Returns

boolean

Whether at least one element was removed.


removeAndInsert()

removeAndInsert(toRemove, toInsert): void

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

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

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

Returns

void


Call Signature

search(element, radius, visitor): void

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

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
ParameterTypeDescription
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

Call Signature

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

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

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


searchKey()

Call Signature

searchKey(key, radius, visitor): void

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

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

Parameters
ParameterTypeDescription
keyReadonlyFloat64ArrayThe 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

Call Signature

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

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

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
ParameterTypeDescription
keyReadonlyFloat64ArrayThe 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.