A class used to to perform kd-tree based operations. More...

#include <kdtree2.h>

Inheritance diagram for AMP::kdtree2< NDIM, TYPE >:

[legend]

Classes
struct	data_struct

Public Types
using	Point = std::array< double, NDIM >

Public Member Functions
void	add (const Point &x, const TYPE &data)
	Add a point.

std::array< double, 2 *NDIM >	box () const
	Return the bounding box for the tree.

bool	empty () const
	Return true if the tree is empty.

std::tuple< Point, TYPE >	findNearest (const Point &x) const
	Search the tree for the nearest neighbor point.

std::vector< std::tuple< Point, TYPE > >	findNearest (const Point &x, double dist) const
	Search the tree for the nearest neighbor points.

std::vector< std::tuple< Point, TYPE > >	findNearest (const Point &x, int N) const
	Search the tree for the nearest neighbor points.

std::vector< std::tuple< Point, TYPE > >	findNearestRay (const Point &x, const Point &dir, double dist) const
	Search the tree for the nearest points to a ray.

std::vector< Point >	getPoints () const
	Return the points in the tree.

std::vector< std::pair< Point, TYPE > >	getPointsAndData () const
	Return the points in the tree.

	kdtree2 ()=default

	kdtree2 (const kdtree2 &)=delete

	kdtree2 (const std::vector< Point > &x, const std::vector< TYPE > &data)
	Constructor.

	kdtree2 (kdtree2 &&)=default

kdtree2 &	operator= (const kdtree2 &)=delete

kdtree2 &	operator= (kdtree2 &&)=default

size_t	size () const
	Return the number of entries stored in the tree.

	~kdtree2 ()=default

Private Member Functions
void	checkNearest (const Point &x, size_t N, std::tuple< Point, TYPE > nearest, double dist) const

void	findNearest (const Point &x, double dist2, std::vector< std::tuple< Point, TYPE > > &nearest) const

void	findNearest (const Point &x, size_t N, std::tuple< Point, TYPE > nearest, double dist) const

void	findNearestRay (const Point &x, const Point &dir, const Point &n_inv, double dist2, std::vector< std::tuple< Point, TYPE > > &nearest) const

void	getPoints (std::vector< Point > &x) const

void	getPoints (std::vector< std::pair< Point, TYPE > > &x) const

void	initialize (size_t N, Point x, TYPE data)

bool	intersect (const Point &x, double dist2) const

	kdtree2 (size_t N, Point x, TYPE data)

void	splitData (size_t N, Point x, TYPE data)

Private Attributes
std::unique_ptr< data_struct >	d_data

Point	d_lb = { 0 }

std::unique_ptr< kdtree2 >	d_left

size_t	d_N = 0

std::unique_ptr< kdtree2 >	d_right

double	d_split = 0

uint8_t	d_split_dim = 0

Point	d_ub = { 0 }

Detailed Description

template<uint8_t NDIM, class TYPE>
class AMP::kdtree2< NDIM, TYPE >

A class used to to perform kd-tree based operations.

This class provides routines for creating and search a kd-tree. The kdtree allows for log(N) nearest neighbor search. The memory requirements for this class are O(N) on the number of points. The search performance for small dimension data is O(log(N)). For high dimension data, the number of points should be N >> 2^d where d is the dimension. Otherwise the performance will degrade approaching O(N).

Definition at line 27 of file kdtree2.h.

Member Typedef Documentation

◆ Point

template<uint8_t NDIM, class TYPE >

using AMP::kdtree2< NDIM, TYPE >::Point = std::array<double, NDIM>

Definition at line 30 of file kdtree2.h.

Constructor & Destructor Documentation

◆ kdtree2() [1/5]

template<uint8_t NDIM, class TYPE >

AMP::kdtree2< NDIM, TYPE >::kdtree2	(	const std::vector< Point > &	x,
		const std::vector< TYPE > &	data
	)

Constructor.

This is the default constructor for creating the kdtree

Parameters

[in]	x	The coordinates of each point in the tree
[in]	data	Data to associate with the nodes

◆ kdtree2() [2/5]

template<uint8_t NDIM, class TYPE >

AMP::kdtree2< NDIM, TYPE >::kdtree2 ( )

default

◆ ~kdtree2()

template<uint8_t NDIM, class TYPE >

AMP::kdtree2< NDIM, TYPE >::~kdtree2 ( )

default

◆ kdtree2() [3/5]

template<uint8_t NDIM, class TYPE >

AMP::kdtree2< NDIM, TYPE >::kdtree2 ( const kdtree2< NDIM, TYPE > & )

delete

◆ kdtree2() [4/5]

template<uint8_t NDIM, class TYPE >

AMP::kdtree2< NDIM, TYPE >::kdtree2 ( kdtree2< NDIM, TYPE > && )

default

◆ kdtree2() [5/5]

template<uint8_t NDIM, class TYPE >

AMP::kdtree2< NDIM, TYPE >::kdtree2	(	size_t	N,
		Point *	x,
		TYPE *	data
	)

private

Member Function Documentation

◆ add()

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::add	(	const Point &	x,
		const TYPE &	data
	)

Add a point.

This will add a point to the kdtree. Note that no rebalancing will be performed

Parameters

[in]	x	The coordinates of the point
[in]	data	The data to add

◆ box()

template<uint8_t NDIM, class TYPE >

std::array< double, 2 *NDIM > AMP::kdtree2< NDIM, TYPE >::box ( ) const

Return the bounding box for the tree.

◆ checkNearest()

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::checkNearest	(	const Point &	x,
		size_t	N,
		std::tuple< Point, TYPE > *	nearest,
		double *	dist
	)		const

private

◆ empty()

template<uint8_t NDIM, class TYPE >

bool AMP::kdtree2< NDIM, TYPE >::empty ( ) const

inline

Return true if the tree is empty.

Definition at line 48 of file kdtree2.h.

References AMP::kdtree2< NDIM, TYPE >::d_N.

◆ findNearest() [1/5]

template<uint8_t NDIM, class TYPE >

std::tuple< Point, TYPE > AMP::kdtree2< NDIM, TYPE >::findNearest ( const Point & x ) const

Search the tree for the nearest neighbor point.

This will return the point and data for the nearest neighbor in the tree

Parameters

[in] x The coordinates of the point to search (NDIM)

Returns: Returns a tuple containing the point and the data

◆ findNearest() [2/5]

template<uint8_t NDIM, class TYPE >

std::vector< std::tuple< Point, TYPE > > AMP::kdtree2< NDIM, TYPE >::findNearest	(	const Point &	x,
		double	dist
	)		const

Search the tree for the nearest neighbor points.

This will return the point and data for the all the points within the distance to the point x

Parameters

[in]	x	The coordinates of the point to search (NDIM)
[in]	dist	The distance to the point

Returns: Returns a vector of tuples containing the points and the data

◆ findNearest() [3/5]

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::findNearest	(	const Point &	x,
		double	dist2,
		std::vector< std::tuple< Point, TYPE > > &	nearest
	)		const

private

◆ findNearest() [4/5]

template<uint8_t NDIM, class TYPE >

std::vector< std::tuple< Point, TYPE > > AMP::kdtree2< NDIM, TYPE >::findNearest	(	const Point &	x,
		int	N
	)		const

Search the tree for the nearest neighbor points.

This will return the point and data for the nearest N neighbors in the tree

Parameters

[in]	x	The coordinates of the point to search (NDIM)
[in]	N	The number of points to return

Returns: Returns a vector of tuples containing the points and the data

◆ findNearest() [5/5]

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::findNearest	(	const Point &	x,
		size_t	N,
		std::tuple< Point, TYPE > *	nearest,
		double *	dist
	)		const

private

◆ findNearestRay() [1/2]

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::findNearestRay	(	const Point &	x,
		const Point &	dir,
		const Point &	n_inv,
		double	dist2,
		std::vector< std::tuple< Point, TYPE > > &	nearest
	)		const

private

◆ findNearestRay() [2/2]

template<uint8_t NDIM, class TYPE >

std::vector< std::tuple< Point, TYPE > > AMP::kdtree2< NDIM, TYPE >::findNearestRay	(	const Point &	x,
		const Point &	dir,
		double	dist
	)		const

Search the tree for the nearest points to a ray.

This function will return all points within the given distance to the ray

Parameters

[in]	x	The coordinates of the starting point (NDIM)
[in]	dir	The direction vector (NDIM)
[in]	dist	The distance to search

Returns: Returns a vector of candidates for the nearest points to a ray.

◆ getPoints() [1/3]

template<uint8_t NDIM, class TYPE >

std::vector< Point > AMP::kdtree2< NDIM, TYPE >::getPoints ( ) const

Return the points in the tree.

◆ getPoints() [2/3]

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::getPoints ( std::vector< Point > & x ) const

private

◆ getPoints() [3/3]

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::getPoints ( std::vector< std::pair< Point, TYPE > > & x ) const

private

◆ getPointsAndData()

template<uint8_t NDIM, class TYPE >

std::vector< std::pair< Point, TYPE > > AMP::kdtree2< NDIM, TYPE >::getPointsAndData ( ) const

Return the points in the tree.

◆ initialize()

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::initialize	(	size_t	N,
		Point *	x,
		TYPE *	data
	)

private

◆ intersect()

template<uint8_t NDIM, class TYPE >

bool AMP::kdtree2< NDIM, TYPE >::intersect	(	const Point &	x,
		double	dist2
	)		const

private

◆ operator=() [1/2]

template<uint8_t NDIM, class TYPE >

kdtree2 & AMP::kdtree2< NDIM, TYPE >::operator= ( const kdtree2< NDIM, TYPE > & )

delete

◆ operator=() [2/2]

template<uint8_t NDIM, class TYPE >

kdtree2 & AMP::kdtree2< NDIM, TYPE >::operator= ( kdtree2< NDIM, TYPE > && )

default

◆ size()

template<uint8_t NDIM, class TYPE >

size_t AMP::kdtree2< NDIM, TYPE >::size ( ) const

inline

Return the number of entries stored in the tree.

Definition at line 45 of file kdtree2.h.

References AMP::kdtree2< NDIM, TYPE >::d_N.

◆ splitData()

template<uint8_t NDIM, class TYPE >

void AMP::kdtree2< NDIM, TYPE >::splitData	(	size_t	N,
		Point *	x,
		TYPE *	data
	)

private

Member Data Documentation

◆ d_data

template<uint8_t NDIM, class TYPE >

std::unique_ptr<data_struct> AMP::kdtree2< NDIM, TYPE >::d_data

private

Definition at line 134 of file kdtree2.h.

◆ d_lb

template<uint8_t NDIM, class TYPE >

Point AMP::kdtree2< NDIM, TYPE >::d_lb = { 0 }

private

Definition at line 130 of file kdtree2.h.

◆ d_left

template<uint8_t NDIM, class TYPE >

std::unique_ptr<kdtree2> AMP::kdtree2< NDIM, TYPE >::d_left

private

Definition at line 132 of file kdtree2.h.

◆ d_N

template<uint8_t NDIM, class TYPE >

size_t AMP::kdtree2< NDIM, TYPE >::d_N = 0

private

Definition at line 127 of file kdtree2.h.

Referenced by AMP::kdtree2< NDIM, TYPE >::empty(), and AMP::kdtree2< NDIM, TYPE >::size().

◆ d_right

template<uint8_t NDIM, class TYPE >

std::unique_ptr<kdtree2> AMP::kdtree2< NDIM, TYPE >::d_right

private

Definition at line 133 of file kdtree2.h.

◆ d_split

template<uint8_t NDIM, class TYPE >

double AMP::kdtree2< NDIM, TYPE >::d_split = 0

private

Definition at line 129 of file kdtree2.h.

◆ d_split_dim

template<uint8_t NDIM, class TYPE >

uint8_t AMP::kdtree2< NDIM, TYPE >::d_split_dim = 0

private

Definition at line 128 of file kdtree2.h.

◆ d_ub

template<uint8_t NDIM, class TYPE >

Point AMP::kdtree2< NDIM, TYPE >::d_ub = { 0 }

private

Definition at line 131 of file kdtree2.h.

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

src/utils/kdtree2.h

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Point

Constructor & Destructor Documentation

◆ kdtree2() [1/5]

◆ kdtree2() [2/5]

◆ ~kdtree2()

◆ kdtree2() [3/5]

◆ kdtree2() [4/5]

◆ kdtree2() [5/5]

Member Function Documentation

◆ add()

◆ box()

◆ checkNearest()

◆ empty()

◆ findNearest() [1/5]

◆ findNearest() [2/5]

◆ findNearest() [3/5]

◆ findNearest() [4/5]

◆ findNearest() [5/5]

◆ findNearestRay() [1/2]

◆ findNearestRay() [2/2]

◆ getPoints() [1/3]

◆ getPoints() [2/3]

◆ getPoints() [3/3]

◆ getPointsAndData()

◆ initialize()

◆ intersect()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ size()

◆ splitData()

Member Data Documentation

◆ d_data

◆ d_lb

◆ d_left

◆ d_N

◆ d_right

◆ d_split

◆ d_split_dim

◆ d_ub