A k-d tree: a k-dimensional generalization of binary search trees This data structure allows for efficient lookup of points and range queries with an Axis-Aligned Bounding Box (when balanced). More...

#include <KdNode.h>

Inheritance diagram for geopop::KdTree:

Collaboration diagram for geopop::KdTree:

Public Member Functions
	KdTree ()
	Constructor: builds an empty tree. More...

void	Apply (std::function< bool(const P &)> f) const
	Calls a function with each of the points in the tree. More...

void	Apply (std::function< bool(const P &)> f, const AABBox< P > &box) const
	Calls a function with every point contained in `box` More...

bool	Contains (const P &point) const
	Test wether a point is contained in the tree. More...

bool	Empty () const
	Is the tree empty. More...

std::size_t	GetHeight () const
	Get the height of the tree (mostly for testing purposes). More...

void	Insert (P point)
	Insert a new point into the tree, using this often may result in an unbalanced tree. More...

std::vector< P >	Query (const AABBox< P > &box) const
	Get all points in the tree that lie within `box`. More...

std::size_t	Size () const
	Get the size of the tree. More...

Static Public Member Functions
static KdTree	Build (const std::vector< P > &points)
	Build a balanced tree from the given set of points efficiently. More...

Static Private Member Functions
template<std::size_t D>
static std::unique_ptr< kd::Node< P, D > >	Construct (const std::vector< P > &points)

Private Attributes
std::size_t	m_size
	The number of points in the tree. More...

std::unique_ptr< kd::Node< P, 0 > >	m_root
	The root node of the tree. More...

Detailed Description

template<typename P>
class geopop::KdTree

A k-d tree: a k-dimensional generalization of binary search trees This data structure allows for efficient lookup of points and range queries with an Axis-Aligned Bounding Box (when balanced).

The template parameter P should have the following attributes and operations:

A static constexpr std::size_t dim: the number of dimensions of the point type.
A template <std::size_d D> get() const returns the coordinate of the Dth dimension of the point.
A nested template <std::size_t D> struct dimension_type has a member type type with return type for Get<D>.
A default constructor and a copy constructor
The individual dimensions should each have a total order and equality
A method bool InBox(const AABB& box) const indicates if a point falls withing the bounding box (only for range queries)

Definition at line 25 of file KdNode.h.

Constructor & Destructor Documentation

template<typename P >

geopop::KdTree::KdTree ( )

Constructor: builds an empty tree.

Definition at line 35 of file KdTree_def.h.

Member Function Documentation

template<typename P>

KdTree geopop::KdTree::Build ( const std::vector & points )

static

Build a balanced tree from the given set of points efficiently.

Parameters

points The points to insert in the resulting tree.

Returns: A balanced KdTree containing the given points.

Definition at line 40 of file KdTree_def.h.

References geopop::KdTree::m_root, and geopop::KdTree::m_size.

template<typename P>

void geopop::KdTree::Apply ( std::function< bool(const P &)> f ) const

Calls a function with each of the points in the tree.

Parameters

f	A function that will be called with each point, if f returns false, traversal stops.

Definition at line 49 of file KdTree_def.h.

References geopop::kd::BaseNode::BorrowLeft(), geopop::kd::BaseNode::BorrowRight(), geopop::kd::BaseNode::GetPoint(), and geopop::KdTree::m_root.

Referenced by geopop::KdTree::Contains(), and geopop::KdTree::Query().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename P>

void geopop::KdTree< P >::Apply	(	std::function< bool(const P &)>	f,
		const AABBox< P > &	box
	)		const

Calls a function with every point contained in box

Parameters

f	A function that will be called with each point within `box`, if f returns false, traversal stops.
box	The containing Axis-Aligned Bounding Box to search for points

Definition at line 76 of file KdTree_def.h.

References geopop::kd::BaseNode::BorrowSplitChild(), geopop::kd::BaseNode::GetPoint(), geopop::AABBox::lower, geopop::KdTree::m_root, and geopop::AABBox::upper.

Here is the call graph for this function: