organizes vertices in a binary-tree structure. Only for static use! More...

#include <kd_tree_static.h>

Classes
class	Node

Public Types
typedef std::vector< Vertex * >	VertexVec

Public Member Functions
void	clear ()

template<class TVrtIterator >
bool	create_from_grid (Grid &grid, TVrtIterator vrtsBegin, TVrtIterator vrtsEnd, Grid::VertexAttachmentAccessor< TPositionAttachment > aaPos, int maxTreeDepth, int splitThreshold, KDSplitDimension splitDimension=KDSD_LARGEST)

template<class TVrtIterator >
bool	create_from_grid (Grid &grid, TVrtIterator vrtsBegin, TVrtIterator vrtsEnd, TPositionAttachment &aPos, int maxTreeDepth, int splitThreshold, KDSplitDimension splitDimension=KDSD_LARGEST)

void	get_leafs (std::vector< Node * > &vLeafsOut)

bool	get_neighbourhood (std::vector< Vertex * > &vrtsOut, typename TPositionAttachment::ValueType &pos, int numClosest)

bool	get_points_in_box (std::vector< Vertex * > &vrtsOut, const TVector &boxMin, const TVector &boxMax)

Node *	get_root ()

	KDTreeStatic ()

Protected Member Functions
template<class TVertexIterator >
bool	create_barycentric (TVertexIterator vrts_begin, TVertexIterator vrts_end, int numVertices, Node *pNode, int actDimension, int maxTreeDepth)

template<class TVertexIterator >
int	get_largest_dimension (TVertexIterator vrts_begin, TVertexIterator vrts_end)

void	get_leafs_recursive (std::vector< Node * > &vLeafsOut, Node *pNode)

template<class TVertexIterator >
int	get_next_split_dimension (int actSplitDimension, TVertexIterator vrts_begin, TVertexIterator vrts_end)

bool	get_points_in_box (std::vector< Vertex * > &vrtsOut, Node *pNode, const TVector &boxMin, const TVector &boxMax)

void	neighbourhood (KDVertexDistanceList &vrtsOut, Node *pNode, TVector &pos, int numClosest)

Protected Attributes
Grid::VertexAttachmentAccessor< TPositionAttachment >	m_aaPos

int	m_iSplitThreshold

float	m_maxDistSQ

int	m_numNeighboursFound

Node	m_parentNode

Grid *	m_pGrid

KDSplitDimension	m_splitDimension

Detailed Description

template<class TPositionAttachment, int numDimensions = 3, class TVector = vector3>
class ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >

organizes vertices in a binary-tree structure. Only for static use!

A kd-tree allows you to find vertices close to a given position in O(log(n)).

This kd-tree should be only used for static geometry. If you intend to add or delete vertices after creation, KDTreeStatic is not suited for your needs.

This class should be replaced by a dynamic kd-tree, which is capable of dynamic auto-balancing.

Member Typedef Documentation

◆ VertexVec

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

typedef std::vector<Vertex*> ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::VertexVec

Constructor & Destructor Documentation

◆ KDTreeStatic()

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::KDTreeStatic ( )

inline

Member Function Documentation

◆ clear()

template<class TPositionAttachment , int numDimensions, class TVector >

void ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::clear

◆ create_barycentric()

template<class TPositionAttachment , int numDimensions, class TVector >

template<class TVertexIterator >

bool ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::create_barycentric	(	TVertexIterator	vrts_begin,
		TVertexIterator	vrts_end,
		int	numVertices,
		Node *	pNode,
		int	actDimension,
		int	maxTreeDepth
	)

protected

References ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_fSplitValue, ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_iSplitDimension, ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_pChild, and ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_pvVertices.

◆ create_from_grid() [1/2]

template<class TPositionAttachment , int numDimensions, class TVector >

template<class TVrtIterator >

bool ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::create_from_grid	(	Grid &	grid,
		TVrtIterator	vrtsBegin,
		TVrtIterator	vrtsEnd,
		Grid::VertexAttachmentAccessor< TPositionAttachment >	aaPos,
		int	maxTreeDepth,
		int	splitThreshold,
		KDSplitDimension	splitDimension = `KDSD_LARGEST`
	)

References ug::Grid::num_vertices().

◆ create_from_grid() [2/2]

template<class TPositionAttachment , int numDimensions, class TVector >

template<class TVrtIterator >

bool ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::create_from_grid	(	Grid &	grid,
		TVrtIterator	vrtsBegin,
		TVrtIterator	vrtsEnd,
		TPositionAttachment &	aPos,
		int	maxTreeDepth,
		int	splitThreshold,
		KDSplitDimension	splitDimension = `KDSD_LARGEST`
	)

Referenced by ug::RemoveDoubles().

◆ get_largest_dimension()

template<class TPositionAttachment , int numDimensions, class TVector >

template<class TVertexIterator >

int ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_largest_dimension	(	TVertexIterator	vrts_begin,
		TVertexIterator	vrts_end
	)

protected

◆ get_leafs()

template<class TPositionAttachment , int numDimensions, class TVector >

void ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_leafs ( std::vector< Node * > & vLeafsOut )

◆ get_leafs_recursive()

template<class TPositionAttachment , int numDimensions, class TVector >

void ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_leafs_recursive	(	std::vector< Node * > &	vLeafsOut,
		Node *	pNode
	)

protected

References ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_pChild.

◆ get_neighbourhood()

template<class TPositionAttachment , int numDimensions, class TVector >

bool ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_neighbourhood	(	std::vector< Vertex * > &	vrtsOut,
		typename TPositionAttachment::ValueType &	pos,
		int	numClosest
	)

Referenced by ug::RemoveDoubles().

◆ get_next_split_dimension()

template<class TPositionAttachment , int numDimensions, class TVector >

template<class TVertexIterator >

int ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_next_split_dimension	(	int	actSplitDimension,
		TVertexIterator	vrts_begin,
		TVertexIterator	vrts_end
	)

protected

References ug::KDSD_CIRCULAR, and ug::KDSD_LARGEST.

◆ get_points_in_box() [1/2]

template<class TPositionAttachment , int numDimensions, class TVector >

bool ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_points_in_box	(	std::vector< Vertex * > &	vrtsOut,
		const TVector &	boxMin,
		const TVector &	boxMax
	)

◆ get_points_in_box() [2/2]

template<class TPositionAttachment , int numDimensions, class TVector >

bool ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_points_in_box	(	std::vector< Vertex * > &	vrtsOut,
		Node *	pNode,
		const TVector &	boxMin,
		const TVector &	boxMax
	)

protected

References ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_fSplitValue, ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_iSplitDimension, ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_pChild, and ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_pvVertices.

◆ get_root()

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

Node* ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_root ( )

inline

References ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_parentNode.

◆ neighbourhood()

template<class TPositionAttachment , int numDimensions, class TVector >

void ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::neighbourhood	(	KDVertexDistanceList &	vrtsOut,
		Node *	pNode,
		TVector &	pos,
		int	numClosest
	)

protected

References ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_fSplitValue, ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_iSplitDimension, ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_pChild, and ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::Node::m_pvVertices.

Member Data Documentation

◆ m_aaPos

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

Grid::VertexAttachmentAccessor<TPositionAttachment> ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_aaPos

protected

◆ m_iSplitThreshold

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

int ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_iSplitThreshold

protected

◆ m_maxDistSQ

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

float ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_maxDistSQ

protected

◆ m_numNeighboursFound

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

int ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_numNeighboursFound

protected

◆ m_parentNode

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

Node ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_parentNode

protected

Referenced by ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::get_root().

◆ m_pGrid

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

Grid* ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_pGrid

protected

◆ m_splitDimension

template<class TPositionAttachment , int numDimensions = 3, class TVector = vector3>

KDSplitDimension ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >::m_splitDimension

protected

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

ugbase/lib_grid/algorithms/trees/kd_tree_static.h
ugbase/lib_grid/algorithms/trees/kd_tree_static_impl.hpp

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class TPositionAttachment, int numDimensions = 3, class TVector = vector3> class ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >

Member Typedef Documentation

◆ VertexVec

Constructor & Destructor Documentation

◆ KDTreeStatic()

Member Function Documentation

◆ clear()

◆ create_barycentric()

◆ create_from_grid() [1/2]

◆ create_from_grid() [2/2]

◆ get_largest_dimension()

◆ get_leafs()

◆ get_leafs_recursive()

◆ get_neighbourhood()

◆ get_next_split_dimension()

◆ get_points_in_box() [1/2]

◆ get_points_in_box() [2/2]

◆ get_root()

◆ neighbourhood()

Member Data Documentation

◆ m_aaPos

◆ m_iSplitThreshold

◆ m_maxDistSQ

◆ m_numNeighboursFound

◆ m_parentNode

◆ m_pGrid

◆ m_splitDimension

template<class TPositionAttachment, int numDimensions = 3, class TVector = vector3>
class ug::KDTreeStatic< TPositionAttachment, numDimensions, TVector >