|
void | Insert (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId) |
| Insert entry. More...
|
|
bool | Remove (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId) |
| Remove entry. More...
|
|
int | Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool a_resultCallback(DATATYPE a_data, void *a_context), void *a_context) |
| Find all within search rectangle. More...
|
|
template<class VISITOR > |
int | Search (const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], VISITOR &a_visitor) |
|
Statistics | CalcStats () |
| Calculate Statistics.
|
|
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.
|
|
DATATYPE | NearestNeighbor (const ELEMTYPE a_point[NUMDIMS]) |
| Find the nearest neighbor of a specific point. More...
|
|
DATATYPE | NearestNeighbor (const ELEMTYPE a_point[NUMDIMS], ELEMTYPE a_squareDistanceCallback(const ELEMTYPE a_point[NUMDIMS], DATATYPE a_data), ELEMTYPE *a_squareDistance) |
| Find the nearest neighbor of a specific point. More...
|
|
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.
|
|
|
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) |
|
ELEMTYPE | MinDist (const ELEMTYPE a_point[NUMDIMS], Rect *a_rect) |
|
void | InsertNNListSorted (std::vector< NNNode * > *nodeList, NNNode *newNode) |
|
bool | Search (Node *a_node, Rect *a_rect, int &a_foundCount, bool a_resultCallback(DATATYPE a_data, void *a_context), void *a_context) |
|
template<class VISITOR > |
bool | Search (Node *a_node, Rect *a_rect, VISITOR &a_visitor, int &a_foundCount) |
|
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) |
|
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.
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 >::NearestNeighbor |
( |
const ELEMTYPE |
a_point[NUMDIMS] | ) |
|
Find the nearest neighbor of a specific point.
It uses the MINDIST method, simplifying the one from "R-Trees: Theory and Applications" by Yannis Manolopoulos et al. The bounding rectangle is used to calculate the distance to the DATATYPE.
- Parameters
-
a_point | point to start the search |
- Returns
- Returns the DATATYPE located closest to a_point, 0 if the tree is empty.
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 >::NearestNeighbor |
( |
const ELEMTYPE |
a_point[NUMDIMS], |
|
|
ELEMTYPE |
a_squareDistanceCallbackconst ELEMTYPE a_point[NUMDIMS], DATATYPE a_data, |
|
|
ELEMTYPE * |
a_squareDistance |
|
) |
| |
Find the nearest neighbor of a specific point.
It uses the MINDIST method, simplifying the one from "R-Trees: Theory and Applications" by Yannis Manolopoulos et al. It receives a callback function to calculate the distance to a DATATYPE object, instead of using the bounding rectangle.
- Parameters
-
a_point | point to start the search |
a_squareDistanceCallback | function that performs the square distance calculation for the selected DATATYPE. |
a_squareDistance | Pointer in which the square distance to the nearest neighbour will be returned. |
- Returns
- Returns the DATATYPE located closest to a_point, 0 if the tree is empty.