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
Name | Type | Description |
---|---|---|
dimensionCount | number | The 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 ) => Float64Array | A 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
Name | Type | Description |
---|---|---|
element | T | The 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
Name | Type | Description |
---|---|---|
elements | Iterable <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
Name | Type | Description |
---|---|---|
element | T | The 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
Name | Type | Description |
---|---|---|
elements | Iterable <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
Name | Type | Description |
---|---|---|
toRemove | Iterable <T > | An iterable of the elements to remove. |
toInsert | Iterable <T > | An iterable of the elements to insert. |
Returns
void
Defined in
src/sdk/utils/datastructures/KdTree.ts:470
search
▸ 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
Name | Type | Description |
---|---|---|
element | T | The query element. |
radius | number | The radius around the query element's key to search. |
visitor | KdTreeSearchVisitor <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
Name | Type | Description |
---|---|---|
element | T | The query element. |
radius | number | The radius around the query key to search. |
maxResultCount | number | The maximum number of search results to return. |
out | T [] | 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
Name | Type | Description |
---|---|---|
key | Readonly <Omit <Float64Array , "set" | "sort" | "copyWithin" >> | The query key. |
radius | number | The radius around the query key to search. |
visitor | KdTreeSearchVisitor <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
Name | Type | Description |
---|---|---|
key | Readonly <Omit <Float64Array , "set" | "sort" | "copyWithin" >> | The query key. |
radius | number | The radius around the query key to search. |
maxResultCount | number | The maximum number of search results to return. |
out | T [] | 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