#include <rtree.h>

Collaboration diagram for RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >:

[legend]

Classes
struct	Branch

class	Iterator
	Iterator is not remove safe. More...

struct	ListNode
	A link list of nodes for reinsertion after a delete operation. More...

struct	Node
	Node for each branch level. More...

struct	PartitionVars
	Variables for finding a split partition. More...

struct	Rect
	Minimal bounding rectangle (n-dimensional) More...

Public Types
enum	{ MAXNODES = TMAXNODES, MINNODES = TMINNODES }

Public Member Functions
	RTree ()

virtual	~RTree ()

void	Insert (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)

void	Remove (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)

int	Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool a_resultCallback(DATATYPE a_data, void a_context), void a_context)

void	RemoveAll ()
	Remove all entries from tree. More...

int	Count ()
	Count the data elements in this container. This is slow as no internal counter is maintained. More...

bool	Load (const char *a_fileName)
	Load tree contents from file. More...

bool	Load (RTFileStream &a_stream)
	Load tree contents from stream. More...

bool	Save (const char *a_fileName)
	Save tree contents to file. More...

bool	Save (RTFileStream &a_stream)
	Save tree contents to stream. More...

void	GetFirst (Iterator &a_it)
	Get 'first' for iteration. More...

void	GetNext (Iterator &a_it)
	Get Next for iteration. More...

void	GetNext2 (Iterator &a_it)

bool	IsNull (Iterator &a_it)
	Is iterator NULL, or at end? More...

DATATYPE &	GetAt (Iterator &a_it)
	Get object at iterator position. More...

Protected Member Functions
Node *	AllocNode ()

void	FreeNode (Node *a_node)

void	InitNode (Node *a_node)

void	InitRect (Rect *a_rect)

bool	InsertRectRec (Rect a_rect, const DATATYPE &a_id, Node a_node, Node **a_newNode, int a_level)

bool	InsertRect (Rect a_rect, const DATATYPE &a_id, Node *a_root, int a_level)

Rect	NodeCover (Node *a_node)

bool	AddBranch (Branch a_branch, Node a_node, Node **a_newNode)

void	DisconnectBranch (Node *a_node, int a_index)

int	PickBranch (Rect a_rect, Node a_node)

Rect	CombineRect (Rect a_rectA, Rect a_rectB)

void	SplitNode (Node a_node, Branch a_branch, Node **a_newNode)

ELEMTYPEREAL	RectSphericalVolume (Rect *a_rect)

ELEMTYPEREAL	RectVolume (Rect *a_rect)

ELEMTYPEREAL	CalcRectVolume (Rect *a_rect)

void	GetBranches (Node a_node, Branch a_branch, PartitionVars *a_parVars)

void	ChoosePartition (PartitionVars *a_parVars, int a_minFill)

void	LoadNodes (Node a_nodeA, Node a_nodeB, PartitionVars *a_parVars)

void	InitParVars (PartitionVars *a_parVars, int a_maxRects, int a_minFill)

void	PickSeeds (PartitionVars *a_parVars)

void	Classify (int a_index, int a_group, PartitionVars *a_parVars)

bool	RemoveRect (Rect a_rect, const DATATYPE &a_id, Node *a_root)

bool	RemoveRectRec (Rect a_rect, const DATATYPE &a_id, Node a_node, ListNode **a_listNode)

ListNode *	AllocListNode ()

void	FreeListNode (ListNode *a_listNode)

bool	Overlap (Rect a_rectA, Rect a_rectB)

void	ReInsert (Node a_node, ListNode *a_listNode)

bool	Search (Node a_node, Rect a_rect, int &a_foundCount, bool a_resultCallback(DATATYPE a_data, void a_context), void a_context)

void	RemoveAllRec (Node *a_node)

void	Reset ()

void	CountRec (Node *a_node, int &a_count)

bool	SaveRec (Node *a_node, RTFileStream &a_stream)

bool	LoadRec (Node *a_node, RTFileStream &a_stream)

Protected Attributes
Node *	m_root
	Root of tree. More...

ELEMTYPEREAL	m_unitSphereVolume
	Unit sphere constant for required number of dimensions. More...

Detailed Description

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
class RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >

Implementation of RTree, a multidimensional bounding rectangle tree. Example usage: For a 3-dimensional tree use RTree<Object*, float, 3> myTree;

This modified, templated C++ version by Greg Douglas at Auran (http://www.auran.com)

DATATYPE Referenced data, should be int, void*, obj* etc. no larger than sizeof<void*> and simple type ELEMTYPE Type of element such as int or float NUMDIMS Number of dimensions such as 2 or 3 ELEMTYPEREAL Type of element that allows fractional and large values such as float or double, for use in volume calcs

NOTES: Inserting and removing data requires the knowledge of its constant Minimal Bounding Rectangle. This version uses new/delete for nodes, I recommend using a fixed size allocator for efficiency. Instead of using a callback function for returned results, I recommend and efficient pre-sized, grow-only memory array similar to MFC CArray or STL Vector for returning search query result.

Definition at line 99 of file rtree.h.

Member Enumeration Documentation

◆ anonymous enum

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

anonymous enum

Enumerator
MAXNODES	Max elements in node.
MINNODES	Min elements in node.

Definition at line 109 of file rtree.h.

Constructor & Destructor Documentation

◆ RTree()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RTree ( )

◆ ~RTree()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

virtual RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::~RTree ( )

virtual

Member Function Documentation

◆ AddBranch()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AddBranch	(	Branch *	a_branch,
		Node *	a_node,
		Node **	a_newNode
	)

protected

◆ AllocListNode()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

ListNode* RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocListNode ( )

protected

◆ AllocNode()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

Node* RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::AllocNode ( )

protected

◆ CalcRectVolume()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CalcRectVolume ( Rect * a_rect )

protected

◆ ChoosePartition()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ChoosePartition	(	PartitionVars *	a_parVars,
		int	a_minFill
	)

protected

◆ Classify()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Classify	(	int	a_index,
		int	a_group,
		PartitionVars *	a_parVars
	)

protected

◆ CombineRect()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

Rect RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CombineRect	(	Rect *	a_rectA,
		Rect *	a_rectB
	)

protected

◆ Count()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

int RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Count ( )

Count the data elements in this container. This is slow as no internal counter is maintained.

Referenced by MVertexRTree::size().

Here is the caller graph for this function:

◆ CountRec()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::CountRec	(	Node *	a_node,
		int &	a_count
	)

protected

◆ DisconnectBranch()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::DisconnectBranch	(	Node *	a_node,
		int	a_index
	)

protected

◆ FreeListNode()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeListNode ( ListNode * a_listNode )

protected

◆ FreeNode()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::FreeNode ( Node * a_node )

protected

◆ GetAt()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

DATATYPE& RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetAt ( Iterator & a_it )

inline

Get object at iterator position.

Definition at line 369 of file rtree.h.

◆ GetBranches()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetBranches	(	Node *	a_node,
		Branch *	a_branch,
		PartitionVars *	a_parVars
	)

protected

◆ GetFirst()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetFirst ( Iterator & a_it )

inline

Get 'first' for iteration.

Definition at line 339 of file rtree.h.

◆ GetNext()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetNext ( Iterator & a_it )

inline

Get Next for iteration.

Definition at line 362 of file rtree.h.

◆ GetNext2()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::GetNext2 ( Iterator & a_it )

inline

Definition at line 363 of file rtree.h.

◆ InitNode()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitNode ( Node * a_node )

protected

◆ InitParVars()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitParVars	(	PartitionVars *	a_parVars,
		int	a_maxRects,
		int	a_minFill
	)

protected

◆ InitRect()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InitRect ( Rect * a_rect )

protected

◆ Insert()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Insert	(	const ELEMTYPE	a_min[NUMDIMS],
		const ELEMTYPE	a_max[NUMDIMS],
		const DATATYPE &	a_dataId
	)

Insert entry

Parameters

a_min	Min of bounding rect
a_max	Max of bounding rect
a_dataId	Positive Id of data. Maybe zero, but negative numbers not allowed.

Referenced by discreteFace::_createGeometryFromSTL(), filterOverlappingElements(), and MVertexRTree::insert().

Here is the caller graph for this function:

◆ InsertRect()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InsertRect	(	Rect *	a_rect,
		const DATATYPE &	a_id,
		Node **	a_root,
		int	a_level
	)

protected

◆ InsertRectRec()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::InsertRectRec	(	Rect *	a_rect,
		const DATATYPE &	a_id,
		Node *	a_node,
		Node **	a_newNode,
		int	a_level
	)

protected

◆ IsNull()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::IsNull ( Iterator & a_it )

inline

Is iterator NULL, or at end?

Definition at line 366 of file rtree.h.

◆ Load() [1/2]

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Load ( const char * a_fileName )

Load tree contents from file.

◆ Load() [2/2]

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Load ( RTFileStream & a_stream )

Load tree contents from stream.

◆ LoadNodes()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::LoadNodes	(	Node *	a_nodeA,
		Node *	a_nodeB,
		PartitionVars *	a_parVars
	)

protected

◆ LoadRec()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::LoadRec	(	Node *	a_node,
		RTFileStream &	a_stream
	)

protected

◆ NodeCover()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

Rect RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NodeCover ( Node * a_node )

protected

◆ Overlap()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Overlap	(	Rect *	a_rectA,
		Rect *	a_rectB
	)

protected

◆ PickBranch()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

int RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickBranch	(	Rect *	a_rect,
		Node *	a_node
	)

protected

◆ PickSeeds()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::PickSeeds ( PartitionVars * a_parVars )

protected

◆ RectSphericalVolume()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectSphericalVolume ( Rect * a_rect )

protected

◆ RectVolume()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RectVolume ( Rect * a_rect )

protected

◆ ReInsert()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::ReInsert	(	Node *	a_node,
		ListNode **	a_listNode
	)

protected

◆ Remove()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Remove	(	const ELEMTYPE	a_min[NUMDIMS],
		const ELEMTYPE	a_max[NUMDIMS],
		const DATATYPE &	a_dataId
	)

Remove entry

Parameters

a_min	Min of bounding rect
a_max	Max of bounding rect
a_dataId	Positive Id of data. Maybe zero, but negative numbers not allowed.

◆ RemoveAll()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAll ( )

Remove all entries from tree.

Referenced by MVertexRTree::~MVertexRTree().

Here is the caller graph for this function:

◆ RemoveAllRec()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveAllRec ( Node * a_node )

protected

◆ RemoveRect()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRect	(	Rect *	a_rect,
		const DATATYPE &	a_id,
		Node **	a_root
	)

protected

◆ RemoveRectRec()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::RemoveRectRec	(	Rect *	a_rect,
		const DATATYPE &	a_id,
		Node *	a_node,
		ListNode **	a_listNode
	)

protected

◆ Reset()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Reset ( )

protected

◆ Save() [1/2]

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Save ( const char * a_fileName )

Save tree contents to file.

◆ Save() [2/2]

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Save ( RTFileStream & a_stream )

Save tree contents to stream.

◆ SaveRec()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::SaveRec	(	Node *	a_node,
		RTFileStream &	a_stream
	)

protected

◆ Search() [1/2]

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

int RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search	(	const ELEMTYPE	a_min[NUMDIMS],
		const ELEMTYPE	a_max[NUMDIMS],
		bool	a_resultCallbackDATATYPE a_data, void *a_context,
		void *	a_context
	)

Find all within search rectangle

Parameters

a_min	Min of search bounding rect
a_max	Max of search bounding rect
a_resultCallback	Callback function to return result. Callback should return 'true' to continue searching
a_context	User context to pass as parameter to a_resultCallback

Returns: Returns the number of entries found

Referenced by discreteFace::closestPoint(), filterOverlappingElements(), MVertexRTree::find(), and MVertexRTree::insert().

Here is the caller graph for this function:

◆ Search() [2/2]

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Search	(	Node *	a_node,
		Rect *	a_rect,
		int &	a_foundCount,
		bool	a_resultCallbackDATATYPE a_data, void *a_context,
		void *	a_context
	)

protected

◆ SplitNode()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::SplitNode	(	Node *	a_node,
		Branch *	a_branch,
		Node **	a_newNode
	)

protected

Member Data Documentation

◆ m_root

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

Node* RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_root

protected

Root of tree.

Definition at line 465 of file rtree.h.

Referenced by RTree< MVertex *, double, 3, double >::GetFirst().

◆ m_unitSphereVolume

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

ELEMTYPEREAL RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::m_unitSphereVolume

protected

Unit sphere constant for required number of dimensions.

Definition at line 466 of file rtree.h.

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

src/common/rtree.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2> class RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ RTree()

◆ ~RTree()

Member Function Documentation

◆ AddBranch()

◆ AllocListNode()

◆ AllocNode()

◆ CalcRectVolume()

◆ ChoosePartition()

◆ Classify()

◆ CombineRect()

◆ Count()

◆ CountRec()

◆ DisconnectBranch()

◆ FreeListNode()

◆ FreeNode()

◆ GetAt()

◆ GetBranches()

◆ GetFirst()

◆ GetNext()

◆ GetNext2()

◆ InitNode()

◆ InitParVars()

◆ InitRect()

◆ Insert()

◆ InsertRect()

◆ InsertRectRec()

◆ IsNull()

◆ Load() [1/2]

◆ Load() [2/2]

◆ LoadNodes()

◆ LoadRec()

◆ NodeCover()

◆ Overlap()

◆ PickBranch()

◆ PickSeeds()

◆ RectSphericalVolume()

◆ RectVolume()

◆ ReInsert()

◆ Remove()

◆ RemoveAll()

◆ RemoveAllRec()

◆ RemoveRect()

◆ RemoveRectRec()

◆ Reset()

◆ Save() [1/2]

◆ Save() [2/2]

◆ SaveRec()

◆ Search() [1/2]

◆ Search() [2/2]

◆ SplitNode()

Member Data Documentation

◆ m_root

◆ m_unitSphereVolume

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
class RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >