AMP::kdtree Class Reference

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

#include <kdtree.h>

Public Member Functions
void	add (const double *x)
	Add a point.
std::vector< double >	box () const
	Function to return the bounding box for the tree.
AMP::Mesh::MeshPoint< double >	find_nearest (const AMP::Mesh::MeshPoint< double > &p) const
	Search the tree for the nearest neighbor point.
size_t	find_nearest (const double *x, double *dist=nullptr, double *pos=nullptr) const
	Search the tree for the nearest neighbor point.
void	find_nearest (int N, const double *x, size_t *index, double *dist=nullptr, double *pos=nullptr) const
	Search the tree for the nearest neighbor point.
size_t	find_nearest2d (const double x, const double y) const
	Search the tree for the nearest neighbor point.
size_t	find_nearest3d (const double x, const double y, const double z) const
	Search the tree for the nearest neighbor point.
	kdtree ()
	kdtree (const kdtree &)=delete
	Copy constructor.
	kdtree (const std::vector< AMP::Mesh::MeshPoint< double > > &x)
	Default constructor.
	kdtree (int ndim, size_t N, const double *const *x)
	Default constructor.
	kdtree (kdtree &&)
	Move constructor.
kdtree &	operator= (const kdtree &)=delete
	Assignment operator.
kdtree &	operator= (kdtree &&)
	Move operator.
	~kdtree ()
	Destructor.

Static Public Member Functions
static std::shared_ptr< kdtree >	create2d (size_t N, const double *x, const double *y)
	Constructor for 2d.
static std::shared_ptr< kdtree >	create3d (size_t N, const double *x, const double *y, const double *z)
	Constructor for 3d.

Private Member Functions
size_t	find_nearest2 (const double *x, double &dist, double *pos) const

Private Attributes
uint8_t	d_dim
size_t	d_N
void *	d_tree

Detailed Description

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 32 of file kdtree.h.

Constructor & Destructor Documentation

kdtree() [1/5]

AMP::kdtree::kdtree ( )

inline

Definition at line 36 of file kdtree.h.

kdtree() [2/5]

AMP::kdtree::kdtree	(	int	ndim,
		size_t	N,
		const double *const *	x
	)

Default constructor.

This is the default constructor for creating the kdtree

Parameters

[in]	ndim	The number of physical dimensions
[in]	N	The number of points in the tree
[in]	x	The coordinates of each point in the tree (x[ndim][N])

kdtree() [3/5]

AMP::kdtree::kdtree

(

const std::vector< AMP::Mesh::MeshPoint< double > > &

x

)

Default constructor.

This an alternative constructor for creating the kdtree

Parameters

[in]

x

The coordinates of each point in the tree

~kdtree()

AMP::kdtree::~kdtree

(

)

Destructor.

kdtree() [4/5]

AMP::kdtree::kdtree ( const kdtree &  )

delete

Copy constructor.

kdtree() [5/5]

AMP::kdtree::kdtree

(

kdtree &&

)

Move constructor.

Member Function Documentation

add()

void AMP::kdtree::add

(

const double *

x

)

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

box()

std::vector< double > AMP::kdtree::box

(

)

const

Function to return the bounding box for the tree.

create2d()

static std::shared_ptr< kdtree > AMP::kdtree::create2d ( size_t  N, const double *  x, const double *  y  )

static

Constructor for 2d.

This will create a kdtree in 2d space

Parameters

[in]	N	The number of points in the tree
[in]	x	The x coordinates of each point
[in]	y	The x coordinates of each point

create3d()

static std::shared_ptr< kdtree > AMP::kdtree::create3d ( size_t  N, const double *  x, const double *  y, const double *  z  )

static

Constructor for 3d.

This will create a kdtree in 3d space

Parameters

[in]	N	The number of points in the tree
[in]	x	The x coordinates of each point
[in]	y	The y coordinates of each point
[in]	z	The z coordinates of each point

find_nearest() [1/3]

AMP::Mesh::MeshPoint< double > AMP::kdtree::find_nearest

(

const AMP::Mesh::MeshPoint< double > &

p

)

const

Search the tree for the nearest neighbor point.

This will return the index of the nearest neighbor in the tree

Parameters

[in]

p

The point to search

Returns

The nearest point

find_nearest() [2/3]

size_t AMP::kdtree::find_nearest	(	const double *	x,
		double *	dist = nullptr,
		double *	pos = nullptr
	)		const

Search the tree for the nearest neighbor point.

This will return the index of the nearest neighbor in the tree

Parameters

[in]	x	The coordinates of the point to search (NDIM)
[out]	dist	Optional output array for the distance to the nearest neighbor (1)
[out]	pos	Optional output array for the position of the nearest neighbor (NDIM)

find_nearest() [3/3]

void AMP::kdtree::find_nearest	(	int	N,
		const double *	x,
		size_t *	index,
		double *	dist = nullptr,
		double *	pos = nullptr
	)		const

Search the tree for the nearest neighbor point.

This will return the index of the nearest neighbor in the tree for each point

Parameters

[in]	N	The number of points we want to search
[in]	x	The coordinates of the points to search ( NDIM x N )
[out]	index	The index of the nearest neighbors (N)
[out]	dist	Optional output array for the distance to the nearest neighbor (N)
[out]	pos	Optional output array for the position of the nearest neighbor (NDIMxN)

find_nearest2()

size_t AMP::kdtree::find_nearest2 ( const double *  x, double &  dist, double *  pos  ) const

private

find_nearest2d()

size_t AMP::kdtree::find_nearest2d	(	const double	x,
		const double	y
	)		const

Search the tree for the nearest neighbor point.

This will return the index of the nearest neighbor in the tree

Parameters

[in]	x	The x coordinate of the search point
[in]	y	The y coordinate of the search point

find_nearest3d()

size_t AMP::kdtree::find_nearest3d	(	const double	x,
		const double	y,
		const double	z
	)		const

Search the tree for the nearest neighbor point.

This will return the index of the nearest neighbor in the tree

Parameters

[in]	x	The x coordinate of the search point
[in]	y	The y coordinate of the search point
[in]	z	The z coordinate of the search point

operator=() [1/2]

kdtree & AMP::kdtree::operator= ( const kdtree &  )

delete

Assignment operator.

operator=() [2/2]

kdtree & AMP::kdtree::operator=

(

kdtree &&

)

Move operator.

Member Data Documentation

d_dim

uint8_t AMP::kdtree::d_dim

private

Definition at line 154 of file kdtree.h.

d_N

size_t AMP::kdtree::d_N

private

Definition at line 155 of file kdtree.h.

d_tree

void* AMP::kdtree::d_tree

private

Definition at line 156 of file kdtree.h.

---

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

• src/utils/kdtree.h