3D specific KD tree More...

#include <K3DTree-approx.h>

Public Member Functions
	K3DTreeApprox ()

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

void	build (const std::vector< Point3D > &pts)
	Builds a balanced KD tree from a list of points. More...

void	buildByRef (std::vector< Point3D > &pts)
	Builds a balanced KD tree from a list of points. More...

void	kill ()
	Destroy the tree contents. 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...

Detailed Description

3D specific KD tree

Definition at line 98 of file K3DTree-approx.h.

Constructor & Destructor Documentation

◆ K3DTreeApprox()

AtomProbe::K3DTreeApprox::K3DTreeApprox ( )

Definition at line 103 of file K3DTree-approx.cpp.

◆ ~K3DTreeApprox()

AtomProbe::K3DTreeApprox::~K3DTreeApprox ( )

Cleans up tree, deallocates nodes.

Definition at line 109 of file K3DTree-approx.cpp.

References kill().

Here is the call graph for this function:

Member Function Documentation

◆ build()

void AtomProbe::K3DTreeApprox::build ( const std::vector< Point3D > & pts )

Builds a balanced KD tree from a list of points.

This call is const, and copies in order to prevent re-ordering of the points. If rordering points is unimportant, use buildByRef

Definition at line 127 of file K3DTree-approx.cpp.

References kill().

Referenced by findKNearest(), and testInexactKDTree().

Here is the call graph for this function:

◆ buildByRef()

void AtomProbe::K3DTreeApprox::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()

Definition at line 149 of file K3DTree-approx.cpp.

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

Here is the call graph for this function:

◆ dump()

void AtomProbe::K3DTreeApprox::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

Definition at line 206 of file K3DTree-approx.cpp.

References AtomProbe::K3DNodeApprox::dump().

Here is the call graph for this function:

◆ findKNearest()

void AtomProbe::K3DTreeApprox::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

Definition at line 447 of file K3DTree-approx.cpp.

References build(), findNearest(), AtomProbe::Point3D::sqrDist(), and TEST.

Here is the call graph for this function:

◆ findNearest()

const Point3D * AtomProbe::K3DTreeApprox::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

Definition at line 213 of file K3DTree-approx.cpp.

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

Referenced by findKNearest(), and testInexactKDTree().

Here is the call graph for this function: