#include <RTree.h>

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 }

typedef bool(*	t_resultCallback )(DATATYPE, void *)

Public Member Functions
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], t_resultCallback a_resultCallback, void *a_context)

void	RemoveAll ()
	Remove all entries from tree.

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

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

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

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

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

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

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

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

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

Protected Member Functions
Node *	AllocNode ()

void	FreeNode (Node *a_node)

void	InitNode (Node *a_node)

void	InitRect (Rect *a_rect)

bool	InsertRectRec (const Branch &a_branch, Node a_node, Node *a_newNode, int a_level)

bool	InsertRect (const Branch &a_branch, Node **a_root, int a_level)

Rect	NodeCover (Node *a_node)

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

void	DisconnectBranch (Node *a_node, int a_index)

int	PickBranch (const Rect a_rect, Node a_node)

Rect	CombineRect (const Rect a_rectA, const Rect a_rectB)

void	SplitNode (Node a_node, const 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, const 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, t_resultCallback a_resultCallback, 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.

ELEMTYPEREAL	m_unitSphereVolume
	Unit sphere constant for required number of dimensions.

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.

Member Enumeration Documentation

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.

Member Function Documentation

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.

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.

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],
		t_resultCallback	a_resultCallback,
		void *	a_context
	)

Find all within search rectangle

Parameters

a_min	Min of search bounding rect
a_max	Max of search bounding rect
a_searchResult	Search result array. Caller should set grow size. Function will reset, not append to array.
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

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

common_features/RTree/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

Member Function Documentation

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 >