The kd_tree with K dimensions container Class. K the number of dimensions. Every node in the tree is a k-dimensional point. Every non-leaf node generates a splitting hyperplane that divides the space into two parts. Points to the left of the splitting hyperplane are represented by the left subtree of that node and points to the right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: it is perpendicular to the axis corresponding to the depth of the node (modulo k). The tree is balanced when constructed with points that are uniformly distributed. More...

#include <KDTree.h>

Classes
struct	Node
	Structure representing a node in the kd tree. More...

Public Types
using	item = std::array<float, K>
	using item instead of point in k d.

Public Member Functions
	kd_tree ()
	Constructor to initialize the kd_tree with a null root.

virtual	~kd_tree ()
	Destructor Function.

void	insert (const std::vector< item > &points)
	Insert a point into the kd_tree. Start at the root, comparing the new point’s first dimension with the root’s first dimension. If the new point’s value is less than the root’s, go to the left child; otherwise, go to the right child. At the next level, compare the second dimension. Continue this process, cycling through dimensions. When a leaf is reached, create a new node and insert the new point.

void	insert_async (const std::vector< item > &points, Spices::ThreadPool *threadPool)
	Insert a point into the kd_tree async. Start at the root, comparing the new point’s first dimension with the root’s first dimension. If the new point’s value is less than the root’s, go to the left child; otherwise, go to the right child. At the next level, compare the second dimension. Continue this process, cycling through dimensions. When a leaf is reached, create a new node and insert the new point.

bool	search (const item &point) const
	Search for a point in the kd_tree. Start at the root, comparing the search point’s first dimension with the root’s first dimension. If the search point’s value is less than the root’s, go to the left child; otherwise, go to the right child. At the next level, compare the second dimension. Continue this process, cycling through dimensions. If an exact match is found, return true. If a leaf is reached without finding a match, return false.

auto	nearest_neighbour_search (const item &point, const item &condition) const -> item
	Search for a nearest point in the kd_tree. Traverse the tree as in a normal search to find the leaf node closest to the query point. Unwind the recursion, considering at each step whether there could be any points on the other side of the splitting plane that are closer to the query point than the current best. If there could be, recurse down the other branch, adding any closer points found to the current best. The final best point is the nearest neighbor.

auto	range_search (const item &point, const item &condition) const -> std::vector< item >
	Search for all points within given range. Start at the root. If the current node is within the range, add it to the result. Recursively search the left and/or right subtrees if the range intersects their respective spaces. Prune the search if the current node’s space does not intersect the query range.

void	print () const
	Public function to print the kd_tree.

size_t	size () const
	Get KD Tree size.

Private Member Functions
void	insert_recursive (Node *&node, std::shared_ptr< std::vector< item > > points, int depth)
	Recursive function to insert a point into the kd_tree.

void	insert_recursive_async (Node &node, std::shared_ptr< std::vector< item > > points, Spices::ThreadPool threadPool, int depth)
	Recursive function to insert a point into the kd_tree async.

bool	search_recursive (Node *node, const item &point, int depth) const
	Recursive function to search for a point in the kd_tree.

void	range_search_recursive (Node *node, const item &point, const item &condition, std::vector< item > &rangePoints, int depth) const
	Recursive function to search for all nearest points in the kd_tree.

void	print_recursive (Node *node, int depth) const
	Recursive function to print the kd_tree.

void	deletenode_recursive (Node *node)
	Delete all node created by this ke_tree.

Private Attributes
Node *	m_Root
	Pointer to the root node of the tree.

std::atomic_size_t	m_Size
	Sizes of this kd tree.

Detailed Description

template<uint32_t K>
class scl::kd_tree< K >

The kd_tree with K dimensions container Class. K the number of dimensions. Every node in the tree is a k-dimensional point. Every non-leaf node generates a splitting hyperplane that divides the space into two parts. Points to the left of the splitting hyperplane are represented by the left subtree of that node and points to the right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: it is perpendicular to the axis corresponding to the depth of the node (modulo k). The tree is balanced when constructed with points that are uniformly distributed.

Definition at line 26 of file KDTree.h.

The documentation for this class was generated from the following file:

SpicesEngine/src/Core/Container/KDTree.h

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description