|
| | KDTree (const NDArray< T, 2 > &points, math::Pool pool={}) |
| | Constructs a KDTree using a given set of points.
|
| std::vector< std::size_t > | query (const NDArray< T, 1 > &query_point, T radius, std::int64_t limit=-1) const |
| | Finds points within a specified radius of a query point.
|
| index::CoreAdjacency | query (T radius, std::size_t minPts, math::Pool pool) const |
| | Returns the full radius-neighborhood adjacency over the indexed point cloud.
|
| std::pair< NDArray< std::int32_t, 2 >, NDArray< T, 2 > > | knnQuery (std::int32_t k, math::Pool pool) const |
| | Returns the k nearest neighbours of every indexed point, self-excluded.
|
| std::pair< std::span< const T >, std::span< const T > > | nodeBounds (const KDTreeNode *node) const noexcept |
| | Axis-aligned bounding box of the points routed through node.
|
| std::span< const std::size_t > | indexPermutation () const noexcept |
| | Permutation from reordered-slot index to original point index.
|
| std::span< const T > | reorderedPoints () const noexcept |
| | Points in reordered (tree-build) order as a flat row-major buffer.
|
| std::size_t | nodeCount () const noexcept |
| | Total node count, equal to one past the largest m_id assigned during construction.
|
| const KDTreeNode * | root () const noexcept |
| | Root of the tree; nullptr for an empty point set.
|
| std::size_t | dim () const noexcept |
| | Dimension count of the indexed point cloud.
|
| | ~KDTree () |
| | Destroys the KDTree, deallocating its nodes.
|
template<class T,
KDTreeDistanceType distanceType = KDTreeDistanceType::kEucledian, std::size_t LeafSize = 16, class AllocT = LinearAllocator<KDTreeNode>>
class clustering::KDTree< T, distanceType, LeafSize, AllocT >
Implements a KDTree data structure.
KDTree is a space-partitioning data structure for organizing points in a K-dimensional space. It is efficient in range-search and nearest neighbor search. This implementation contains a vector of points and an allocator for KDTree nodes, with the root node representing the tree's starting point.
- Template Parameters
-
| T | Data type of the points. |
| LeafSize | Maximum number of points in a leaf node before splitting (default 16). |
| AllocT | Allocator type for KDTree nodes, defaults to LinearAllocator<KDTreeNode>. |
- Warning
- The KDTree does not manage the lifecycle of the points array. Ensure the array remains valid during KDTree's lifetime.
- Usage Example
auto indices = kdtree.query(query_point, radius);
for (
size_t index : indices) {
std::cout <<
index << std::endl;
}
KDTree(const NDArray< T, 2 > &points, math::Pool pool={})
Constructs a KDTree using a given set of points.
Represents a multidimensional array (NDArray) of a fixed number of dimensions N and element type T.
Definition at line 93 of file kdtree.h.
template<class T,
KDTreeDistanceType distanceType = KDTreeDistanceType::kEucledian, std::size_t LeafSize = 16, class AllocT = LinearAllocator<KDTreeNode>>
Returns the k nearest neighbours of every indexed point, self-excluded.
For every row i of the original point cloud, the method finds the k original-index points minimizing squared Euclidean distance to row i (excluding i itself) and writes the result as two parallel (n x k) arrays: indices[i][j] is the original index of the j-th closest neighbour, sqDists[i][j] is its squared distance. Each row is sorted ascending by sqDist. Ties in distance resolve on smaller neighbour index so results are reproducible bit-for-bit across runs at matched input.
Traversal is depth-first with the bounded max-heap's current worst retained distance serving as the pruning bound (heap.top().first). Until the heap fills, the bound is std::numeric_limits<T>::max() and pruning is inactive.
- Precondition
- k >= 1 and
k < n.
- Parameters
-
| k | Number of neighbours per point (self-excluded). The signed 32-bit argument mirrors the neighbour-index type carried through the (indices, sqDists) output; the preconditions clamp it to [1, n). |
| pool | Parallelism injection for the outer per-point loop; follows the shouldParallelize policy the radius-query path uses. |
- Returns
- Pair of two arrays:
std::int32_t array of neighbour indices; T array of squared distances.
Definition at line 390 of file kdtree.h.
template<class T,
KDTreeDistanceType distanceType = KDTreeDistanceType::kEucledian, std::size_t LeafSize = 16, class AllocT = LinearAllocator<KDTreeNode>>
| std::pair< std::span< const T >, std::span< const T > > clustering::KDTree< T, distanceType, LeafSize, AllocT >::nodeBounds |
( |
const KDTreeNode * | node | ) |
const |
|
inlinenodiscardnoexcept |
Axis-aligned bounding box of the points routed through node.
For a leaf, the bounds enclose every point stored at the leaf. For an internal node, the bounds enclose the union of the child boxes plus the pivot. Callers consume the result as two d-element spans into the tree's contiguous bounds buffer; the pointers are valid for the tree's lifetime.
- Parameters
-
| node | Node to query; must belong to this tree. Passing nullptr is a precondition violation. |
- Returns
- Pair of spans (min, max), each of length
d.
Definition at line 441 of file kdtree.h.
1.16.1