3D specific KD tree More...

#include <K3DTree.h>

Public Member Functions
	K3DTree ()

	~K3DTree ()
	Cleans up tree, deallocates nodes. More...

void	build (std::vector< Point3D > pts)

void	buildByRef (std::vector< Point3D > &pts)

void	kill ()
	Clean the tree. More...

const Point3D *	findNearest (const Point3D &, const BoundCube &, float deadDistSqr) const
	Find the nearest point to a given P that lies outsid some dead zone. More...

void	findKNearest (const Point3D &sourcePoint, const BoundCube &treeDomain, unsigned int numNNs, std::vector< const Point3D *> &results, float deadDistSqr=0.0f) const
	Find the nearest N points. More...

void	dump (std::ostream &) const
	Textual output of tree. tabs are used to separate different levels of the tree. More...

unsigned int	nodeCount () const
	Print the number of nodes stored in the tree. More...

Static Public Member Functions
static void	setProgressPtr (unsigned int *ptr)

static void	setAbortFlag (const ATOMIC_BOOL *ptr)

Detailed Description

3D specific KD tree

Constructor & Destructor Documentation

◆ K3DTree()

K3DTree::K3DTree ( )

◆ ~K3DTree()

K3DTree::~K3DTree ( )

Cleans up tree, deallocates nodes.

References kill().

Member Function Documentation

◆ build()

void K3DTree::build ( std::vector< Point3D > pts )

Builds a balanced KD tree from a list of points This call is being passed by copy in order to prevent re-ordering of the points. It may be worth having two calls a pass by ref version where the points get scrambled and this one which preserves input point ordering (due to the copy)

References ASSERT, and kill().

◆ buildByRef()

void K3DTree::buildByRef ( std::vector< Point3D > & pts )

Builds a balanced KD tree from a list of points This uses a pass by ref where the points get scrambled (sorted). Resultant tree should be identical to that generated by build()

References kill(), AxisCompare::setAxis(), K3DNode::setAxis(), K3DNode::setLeft(), K3DNode::setLoc(), and K3DNode::setRight().

Referenced by SpatialAnalysisFilter::setPropFromBinding().

Here is the caller graph for this function:

◆ dump()

void K3DTree::dump ( std::ostream & strm ) const

Textual output of tree. tabs are used to separate different levels of the tree.

The output from this function can be quite large for even modest trees. Recommended for debugging only

References K3DNode::dump().

◆ findKNearest()

void K3DTree::findKNearest	(	const Point3D &	sourcePoint,
		const BoundCube &	treeDomain,
		unsigned int	numNNs,
		std::vector< const Point3D *> &	results,
		float	deadDistSqr = `0.0f`
	)		const

Find the nearest N points.

Finds the nearest N points, that lie outside a dead distance of deadDistSqr. k is the number to find

References findNearest(), and Point3D::sqrDist().

Referenced by generateNNHist(), and SpatialAnalysisFilter::setPropFromBinding().

Here is the caller graph for this function:

◆ findNearest()

const Point3D * K3DTree::findNearest	(	const Point3D &	searchPt,
		const BoundCube &	domainCube,
		float	deadDistSqr
	)		const

Find the nearest point to a given P that lies outsid some dead zone.

deadDistSqr can be used ot disallow exact matching on NN searching simply pass epsilon =std::numeric_limits<float>::epsilon() (#include <limits>) Boundcube is the bounding box around the entire dataset

References ASSERT, K3DNode::getLocRef(), K3DNode::getLocVal(), BoundCube::intersects(), K3DNode::left(), K3DNode::right(), and K3DNode::sqrDist().

Referenced by findKNearest(), generateDistHist(), and SpatialAnalysisFilter::setPropFromBinding().

Here is the caller graph for this function: