Horizon
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | List of all members
RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES > Class Template Reference

Implementation of RTree, a multidimensional bounding rectangle tree. More...

#include <rtree.h>

Classes

struct  Branch
 May be data or may be another subtree The parents level determines this. More...
 
class  Iterator
 Iterator is not remove safe. More...
 
struct  ListNode
 A link list of nodes for reinsertion after a delete operation. More...
 
struct  NNNode
 Data structure used for Nearest Neighbor search implementation. 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...
 
struct  Statistics
 

Public Types

enum  { MAXNODES = TMAXNODES , MINNODES = TMINNODES }
 
using iterator = Iterator
 
using const_iterator = const Iterator
 

Public Member Functions

void Insert (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
 Insert entry.
 
bool Remove (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
 Remove entry.
 
int Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], std::function< bool(const DATATYPE &)> a_callback) const
 Find all within search rectangle.
 
int Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], std::function< bool(const DATATYPE &)> a_callback, bool &aFinished) const
 Find all within search rectangle.
 
template<class VISITOR >
int Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], VISITOR &a_visitor) const
 
Statistics CalcStats ()
 Calculate Statistics.
 
void RemoveAll ()
 Remove all entries from tree.
 
int Count () const
 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) const
 Load tree contents from stream.
 
bool Save (const char *a_fileName)
 Save tree contents to file.
 
bool Save (RTFileStream &a_stream) const
 Save tree contents to stream.
 
std::vector< std::pair< ELEMTYPE, DATATYPE > > NearestNeighbors (const ELEMTYPE aPoint[NUMDIMS], std::function< bool(const std::size_t aNumResults, const ELEMTYPE aMinDist)> aTerminate, std::function< bool(const DATATYPE aElement)> aFilter, std::function< ELEMTYPE(const ELEMTYPE a_point[NUMDIMS], const DATATYPE a_data)> aSquaredDist) const
 Gets an ordered vector of the nearest data elements to a specified point.
 
iterator begin (const Rect &aRect) const
 
iterator begin () const
 
iterator end () const
 
iterator end (const Rect &aRect) const
 

Protected Member Functions

NodeAllocNode () const
 
void FreeNode (Node *a_node) const
 
void InitNode (Node *a_node) const
 
void InitRect (Rect *a_rect) const
 
bool InsertRectRec (const Rect *a_rect, const DATATYPE &a_id, Node *a_node, Node **a_newNode, int a_level) const
 
bool InsertRect (const Rect *a_rect, const DATATYPE &a_id, Node **a_root, int a_level) const
 
Rect NodeCover (Node *a_node) const
 
bool AddBranch (const Branch *a_branch, Node *a_node, Node **a_newNode) const
 
void DisconnectBranch (Node *a_node, int a_index) const
 
int PickBranch (const Rect *a_rect, Node *a_node) const
 
Rect CombineRect (const Rect *a_rectA, const Rect *a_rectB) const
 
void SplitNode (Node *a_node, const Branch *a_branch, Node **a_newNode) const
 
ELEMTYPEREAL RectSphericalVolume (const Rect *a_rect) const
 
ELEMTYPEREAL RectVolume (const Rect *a_rect) const
 
ELEMTYPEREAL CalcRectVolume (const Rect *a_rect) const
 
void GetBranches (Node *a_node, const Branch *a_branch, PartitionVars *a_parVars) const
 
void ChoosePartition (PartitionVars *a_parVars, int a_minFill) const
 
void LoadNodes (Node *a_nodeA, Node *a_nodeB, PartitionVars *a_parVars) const
 
void InitParVars (PartitionVars *a_parVars, int a_maxRects, int a_minFill) const
 
void PickSeeds (PartitionVars *a_parVars) const
 
void Classify (int a_index, int a_group, PartitionVars *a_parVars) const
 
bool RemoveRect (const Rect *a_rect, const DATATYPE &a_id, Node **a_root) const
 
bool RemoveRectRec (const Rect *a_rect, const DATATYPE &a_id, Node *a_node, ListNode **a_listNode) const
 
ListNodeAllocListNode () const
 
void FreeListNode (ListNode *a_listNode) const
 
void ReInsert (Node *a_node, ListNode **a_listNode) const
 
ELEMTYPE MinDist (const ELEMTYPE a_point[NUMDIMS], const Rect &a_rect) const
 
bool Search (const Node *a_node, const Rect *a_rect, int &a_foundCount, std::function< bool(const DATATYPE &)> a_callback) const
 
template<class VISITOR >
bool Search (const Node *a_node, const Rect *a_rect, VISITOR &a_visitor, int &a_foundCount) const
 
void RemoveAllRec (Node *a_node) const
 
void Reset () const
 
void CountRec (const Node *a_node, int &a_count) const
 
bool SaveRec (const Node *a_node, RTFileStream &a_stream) const
 
bool LoadRec (const Node *a_node, RTFileStream &a_stream) const
 

Static Protected Member Functions

static bool Overlap (const Rect *a_rectA, const Rect *a_rectB)
 

Protected Attributes

Nodem_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

◆ 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.

Member Function Documentation

◆ 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_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.

◆ NearestNeighbors()

template<class DATATYPE , class ELEMTYPE , int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
std::vector< std::pair< ELEMTYPE, DATATYPE > > RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::NearestNeighbors ( const ELEMTYPE  aPoint[NUMDIMS],
std::function< bool(const std::size_t aNumResults, const ELEMTYPE aMinDist)>  aTerminate,
std::function< bool(const DATATYPE aElement)>  aFilter,
std::function< ELEMTYPE(const ELEMTYPE a_point[NUMDIMS], const DATATYPE a_data)>  aSquaredDist 
) const

Gets an ordered vector of the nearest data elements to a specified point.

Parameters
aPointcoordinate to measure against
aTerminateCallback routine to check when we have gathered sufficient elements
aFilterCallback routine to remove specific elements from the query results
aSquaredDistCallback routine to measure the distance from the point to the data element
Returns
vector of matching elements and their distance to the point

◆ Remove()

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 >::Remove ( const ELEMTYPE  a_min[NUMDIMS],
const ELEMTYPE  a_max[NUMDIMS],
const DATATYPE &  a_dataId 
)

Remove entry.

Parameters
a_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.
Returns
1 if record not found, 0 if success.

◆ 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],
std::function< bool(const DATATYPE &)>  a_callback 
) const

Find all within search rectangle.

Parameters
a_minMin of search bounding rect
a_maxMax of search bounding rect
a_callbackCallback function to return result. Callback should return 'true' to continue searching
Returns
Returns the number of entries found

◆ Search() [2/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],
std::function< bool(const DATATYPE &)>  a_callback,
bool &  aFinished 
) const

Find all within search rectangle.

Parameters
a_minMin of search bounding rect
a_maxMax of search bounding rect
a_callbackCallback function to return result. Callback should return 'true' to continue searching
aFinishedThis is set to true if the search completed and false if it was interupted
Returns
Returns the number of entries found

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