VRS::SpaceTree< NODE, DIM > Class Template Reference
#include <vrs/container/spacetree.h>
Public Types | |
| typedef SpaceTreePath< DIM > | Path |
Public Member Functions | |
| virtual Point< DIM > | findNearMainCellPoint (const Point< DIM > &p) const |
| Returns a point p' near p inside the main cell. | |
| virtual NodePointer | getRoot ()=0 |
| virtual NodePointer | getParent (const NodePointer &node)=0 |
| virtual NodePointer | getChild (const NodePointer &node, ChildNumber childNumber)=0 |
| virtual ChildNumber | getChildNumber (const NodePointer &node) const =0 |
| virtual SpaceTreePath< DIM > | getPath (const NodePointer &node) const |
| virtual NodePointer | getNode (const SpaceTreePath< DIM > &path) |
| virtual SpaceTreePath< DIM > | cropPath (const SpaceTreePath< DIM > &path) const |
| virtual Cell< DIM > | getCell (const NodePointer &node) const |
| virtual Cell< DIM > | getCell (const SpaceTreePath< DIM > &path) const |
| NodePointer | getNeighbor (const NodePointer &node, UINT direction) |
| Iterator< NodePointer > * | getNeighbors (NodePointer node) |
| const TransactionNo & | getTransactionNumber () const |
| VRS_TYPEINFO (SpaceTree, SharedObj) | |
| VRS_SERIALIZABLE_ABSTRACT_CLASS (SpaceTree) | |
| template<typename POINTSET, typename INCLUSIONTEST> | |
| SpaceTreePath< DIM > | findSmallestEnclosingNode (const POINTSET &pointSet, UINT maxLevel, bool mustExist, INCLUSIONTEST test) |
| template<typename POINTSET> | |
| SpaceTreePath< DIM > | findSmallestEnclosingNode (const POINTSET &pointSet, UINT maxLevel=32, bool mustExist=true) |
| Iterator< SpaceTreePath< DIM > > * | emptyIterator () |
| template<typename POINTSET, typename INTERSECTIONTEST> | |
| Iterator< SpaceTreePath< DIM > > * | findIntersectingNodes (const POINTSET &pointSet, UINT level, bool mustExist, INTERSECTIONTEST test) |
| template<typename POINTSET> | |
| Iterator< SpaceTreePath< DIM > > * | findIntersectingNodes (const POINTSET &pointSet, UINT level, bool mustExist=true) |
| template<typename POINTSET, typename INCLUSIONTEST> | |
| Iterator< SpaceTreePath< DIM > > * | findEnclosingNodes (const POINTSET &pointSet, UINT level, bool mustExist, INCLUSIONTEST test) |
| template<typename POINTSET> | |
| Iterator< SpaceTreePath< DIM > > * | findEnclosingNodes (const POINTSET &cell, UINT level, bool mustExist=true) |
Protected Member Functions | |
| SpaceTree () | |
| const NodePointer | getRoot () const |
| const NodePointer | getParent (const NodePointer &node) const |
| const NodePointer | getChild (const NodePointer &node, ChildNumber childNumber) const |
| NodePointer | createNodePointer (NODE *node) |
| NODE * | getPointer (const NodePointer &pointer) |
| const NODE * | getPointer (const NodePointer &pointer) const |
| virtual Cell< DIM > | getSubCell (const NodePointer &node, const Cell< DIM > &cell, ChildNumber childNumber) const |
| void | invalidatePointers () |
Protected Attributes | |
| Cell< DIM > | mainCell_ |
| TransactionNo | m_transactionNo |
Static Protected Attributes | |
| static const ChildNumber | MaxChilds |
| static const ChildNumber | InvalidChildNumber |
Classes | |
| class | DefaultInclusionTest |
| class | DefaultIntersectionTest |
| class | NodePointer |
| struct | STNODEInfo |
Detailed Description
template<typename NODE, UINT DIM>
class VRS::SpaceTree< NODE, DIM >
Abstract base class for SpaceTrees. SpaceTree implements all higher level access like getNeighbor() and spatial search methods, but is independent of a concrete arrangement of nodes in memory or the content of these nodes. All implemented method implementations are based on 4 pure virtual basic methods (see below). Since a NodePointer (even if it is invalid) contains a smart pointer to the SpaceTree that it has been created from, a SpaceTree is not deleted from memory as long as any NodePointer refers to it. So if you want to delete a SpaceTree and you have a NodePointer np still refering to it, you need to delete np or to re-assign np, e.g. bynp = SpaceTree<NODE, DIM>::NodePointer();
The SpaceTree is a n-dimensional generalization of the well-known datastructures quadtree (n=2) and octree (n=3). It provides the following features:
- The dimension is specified by a template parameter.
- Spatial search methods getSmallestEnclosingNode(), getIntersectingNodes() for arbitrary point sets (single point, box, sphere, ...). The type of the point set is specified by a template parameter.
- Neighbor access methods.
- Choice between a dynamic (capability to delete or create nodes) and a static implementation (memory and time efficient array based implementation for complete trees of constant depth) via derivations DynamicSpaceTree and StaticSpaceTree.
- It allows to replace the usual uniform cell subdivision by an own subdivision scheme simply by deriving an own class from DynamicSpaceTree or StaticSpaceTree and overloading the getSubCell method.
- The nodes can contain arbitrary data. The type of this data is specified by a template parameter.
- Safe node access via a node-pointer data structure.
How to use a SpaceTree:
1) Choose a dimension n (normally n will be 2 (QuadTree) or 3 (Octree). In this case use one of the specialized SpaceTrees in quadtree.h and octree.h. 2) Choose the content you want to store. Note, if you choose e.g. Vector as content, each node stores exactly ONE vector, i.e. nodes have no fixed container type. If you want to store multiple vectors in a node choose SO<Array<Vector> > for example. 3) Choose the type of SpaceTree: A StaticSpaceTree is a complete tree of fixed size, that utilizes its static structure to optimize its memory and time efficiency. A DynamicSpaceTree offers the cability to create new nodes and to delete existing nodes. Particularly it need not not to be complete. 4) Given a NodePointer np you get a reference to the content of the corresponding node by typing
np->content
Example: We want to create an Octree, which is able to store multiple vectors in each node. Furthermore we have an iterator "points" of 3D vectors and want to store these vectors in the corresponding nodes of the tree on level 7. The space supported by the tree is given by "mainCell".
Some typedefs for convenience typedef DynamicOctree<SO<Array<Vector> > > MyTree; typedef MyTree::NodePointer NodePointer; typedef MyTree::Path Path;
SO<MyTree> tree(mainCell); for (UINT i=0; i<points->size(); i++) {
const Vector& point = points->get(i);
find the (possibly still not existing) node whose cell contains "point" Path path = tree->findContainingNode(point, 7, false); NodePointer np = tree->getNode(path); if (!np.valid()) { create new node np = tree->createNode(path); np->content = new NonPersistentArray<Vector>; } np->content->append(point); }
Note: Only Quadtrees and Octrees are able to handle VRS vectors, but it would not be useful for the general case. If you do not want to use a specialized derivate, you need to use Point<n> instead of vectors and findEnclosingNode() instead of findContainingNode().
Member Typedef Documentation
| typedef SpaceTreePath<DIM> VRS::SpaceTree< NODE, DIM >::Path |
The original declaration of the following methods are part of a quite unreadable code section that need not to be read to understand how to use a SpaceTree. Therefore their declarations are repeated here: template<typename POINTSET,typename INCLUSIONTEST> SpaceTreePath<DIM> findSmallestEnclosingNode( const POINTSET& pointSet, UINT maxLevel = Path::MaxPathLength(), bool mustExist = true, INCLUSIONTEST test = DefaultInclusionTest<POINTSET>()); Returns the longest path that leads to a node whose cell completely encloses a given point set. If the path length attains "maxLevel", the search is aborted and the path of length maxLevel is returned. Not that the length of a path cannot exceed Path::MaxPathLength(). If "mustExist" is true, only existing nodes are considered. Otherwise the result can be a path leading to a still not existing node, whose cell would enclose the point set. The parameter "test" is a function object that provides an operator() with two parameters pointSet and cell, that returns true if the pointSet is contained in the cell. You can see how to realize the function object on the example of the DefaultIntersectionTest class (see below). If POINTSET provides a method isContainedIn(Cell), the test parameter can be left out. template<typename POINTSET, typename INTERSECTIONTEST> Iterator<SpaceTreePath<DIM> >* findIntersectingNodes( const POINTSET& pointSet, UINT level, bool mustExist = true, INTERSECTIONTEST test = DefaultIntersectionTest<POINTSET>()); Returns an iterator of paths to all nodes on a specified tree level that intersect a given point set. For the "mustExist" parameter see above. The intersection test of a point set and a cell is performed similar to the inclusion test above. The parameter "test" can be left out if POINTSET provides a method intersects(Cell). template<typename POINTSET, typename INCLUSIONTEST> Iterator<SpaceTreePath<DIM> >* findEnclosingNodes( const POINTSET& pointSet, UINT level, bool mustExist, INCLUSIONTEST test) { This method is only useful for derivates of SpaceTree that enable overlapping cells. Otherwise the result is empty or contains exactly one element,
Reimplemented in VRS::DynamicOctree< CONTENT >, VRS::StaticOctree< CONTENT >, VRS::DynamicQuadtree< CONTENT >, VRS::StaticQuadtree< CONTENT >, VRS::DynamicSpaceTree< CONTENT, DIM >, VRS::StaticSpaceTree< CONTENT, DIM >, VRS::DynamicSpaceTree< CONTENT, 3 >, VRS::DynamicSpaceTree< CONTENT, 2 >, VRS::StaticSpaceTree< CONTENT, 3 >, and VRS::StaticSpaceTree< CONTENT, 2 >.
Constructor & Destructor Documentation
| VRS::SpaceTree< NODE, DIM >::SpaceTree | ( | ) | [inline, protected] |
These methods are needed to traverse the tree in a const method
Member Function Documentation
| virtual Point<DIM> VRS::SpaceTree< NODE, DIM >::findNearMainCellPoint | ( | const Point< DIM > & | p | ) | const [virtual] |
Returns a point p' near p inside the main cell.
The method findSmallestEnclosingNode() method will not find a result for points outside the main cell. Using findNearMainCellPoint() first guarantees that a subsequent findSmallestEnclosingNode() obtains a result.
| virtual NodePointer VRS::SpaceTree< NODE, DIM >::getRoot | ( | ) | [pure virtual] |
Each node access is done by an via NodePointers. A NodePointer provides access to a specific node of a specific tree similar to a usual pointer by * and -> operator. Using invalid NodePointers causes an assertion. Invalid pointers are return for example if a requested node does not exist. The NodePointer provides a validity check method valid(). Note: If a node of a tree is deleted, all existing NodePointers pointing to any nodes of the tree become invalid. Basic SpaceTree access methods. If you want to derive a class from SpaceTree, please note: It is assumed that the first three of the methods below return an invalid NodePointer if the requested Node does not exist.
Implemented in VRS::DynamicSpaceTree< CONTENT, DIM >, VRS::StaticSpaceTree< CONTENT, DIM >, VRS::DynamicSpaceTree< CONTENT, 3 >, VRS::DynamicSpaceTree< CONTENT, 2 >, VRS::StaticSpaceTree< CONTENT, 3 >, and VRS::StaticSpaceTree< CONTENT, 2 >.
| virtual NodePointer VRS::SpaceTree< NODE, DIM >::getParent | ( | const NodePointer & | node | ) | [pure virtual] |
| virtual NodePointer VRS::SpaceTree< NODE, DIM >::getChild | ( | const NodePointer & | node, | |
| ChildNumber | childNumber | |||
| ) | [pure virtual] |
| virtual ChildNumber VRS::SpaceTree< NODE, DIM >::getChildNumber | ( | const NodePointer & | node | ) | const [pure virtual] |
Converting between Paths and NodePointers. Each valid NodePointer corresponds to a valid SpaceTreePath, but not vice versa, because a node specified by a path may not exist.
Implemented in VRS::DynamicSpaceTree< CONTENT, DIM >, VRS::StaticSpaceTree< CONTENT, DIM >, VRS::DynamicSpaceTree< CONTENT, 3 >, VRS::DynamicSpaceTree< CONTENT, 2 >, VRS::StaticSpaceTree< CONTENT, 3 >, and VRS::StaticSpaceTree< CONTENT, 2 >.
| virtual SpaceTreePath<DIM> VRS::SpaceTree< NODE, DIM >::getPath | ( | const NodePointer & | node | ) | const [virtual] |
Reimplemented in VRS::StaticSpaceTree< CONTENT, DIM >, VRS::StaticSpaceTree< CONTENT, 3 >, and VRS::StaticSpaceTree< CONTENT, 2 >.
| virtual NodePointer VRS::SpaceTree< NODE, DIM >::getNode | ( | const SpaceTreePath< DIM > & | path | ) | [virtual] |
Reimplemented in VRS::StaticSpaceTree< CONTENT, DIM >, VRS::StaticSpaceTree< CONTENT, 3 >, and VRS::StaticSpaceTree< CONTENT, 2 >.
| virtual SpaceTreePath<DIM> VRS::SpaceTree< NODE, DIM >::cropPath | ( | const SpaceTreePath< DIM > & | path | ) | const [virtual] |
Removes the last n steps from a path, where n is choosen as small as possible with the property that the node represented by the resulting path exists. Note that the resulting path is invalid if the root node does not exist.
| virtual Cell<DIM> VRS::SpaceTree< NODE, DIM >::getCell | ( | const NodePointer & | node | ) | const [virtual] |
| virtual Cell<DIM> VRS::SpaceTree< NODE, DIM >::getCell | ( | const SpaceTreePath< DIM > & | path | ) | const [virtual] |
Neighbor access. See SpaceTreePath interface for a appropriate direction constants and a specification how the direction is determined by the int parameter.
| NodePointer VRS::SpaceTree< NODE, DIM >::getNeighbor | ( | const NodePointer & | node, | |
| UINT | direction | |||
| ) |
| Iterator<NodePointer>* VRS::SpaceTree< NODE, DIM >::getNeighbors | ( | NodePointer | node | ) |
The transaction number ensures safe node access. Each derivate of this class must increase the transaction number by calling invalidatePointers() if any node of the tree is removed. Each NodePointer keeps a transaction number and becomes invalid if the transaction number of the tree is greater than its own. By this means it is ensured that a valid NodePointer never points to a deleted cell.
| const TransactionNo& VRS::SpaceTree< NODE, DIM >::getTransactionNumber | ( | ) | const |
| VRS::SpaceTree< NODE, DIM >::VRS_TYPEINFO | ( | SpaceTree< NODE, DIM > | , | |
| SharedObj | ||||
| ) |
| VRS::SpaceTree< NODE, DIM >::VRS_SERIALIZABLE_ABSTRACT_CLASS | ( | SpaceTree< NODE, DIM > | ) |
| const NodePointer VRS::SpaceTree< NODE, DIM >::getRoot | ( | ) | const [protected] |
| const NodePointer VRS::SpaceTree< NODE, DIM >::getParent | ( | const NodePointer & | node | ) | const [protected] |
| const NodePointer VRS::SpaceTree< NODE, DIM >::getChild | ( | const NodePointer & | node, | |
| ChildNumber | childNumber | |||
| ) | const [protected] |
These methods provide access to NodePointers for derived classes.
| NodePointer VRS::SpaceTree< NODE, DIM >::createNodePointer | ( | NODE * | node | ) | [protected] |
| NODE* VRS::SpaceTree< NODE, DIM >::getPointer | ( | const NodePointer & | pointer | ) | [protected] |
| const NODE* VRS::SpaceTree< NODE, DIM >::getPointer | ( | const NodePointer & | pointer | ) | const [protected] |
| virtual Cell<DIM> VRS::SpaceTree< NODE, DIM >::getSubCell | ( | const NodePointer & | node, | |
| const Cell< DIM > & | cell, | |||
| ChildNumber | childNumber | |||
| ) | const [protected, virtual] |
If you want to use an own cell subdivision scheme instead of the default uniform subdivision, you only need to overload getSubCell(). If you do so, please not the following conventions: a) The method must work also for not yet existing nodes, i.e. node is invalid b) The subCell must be contained in the parent cell.
| void VRS::SpaceTree< NODE, DIM >::invalidatePointers | ( | ) | [protected] |
| SpaceTreePath<DIM> VRS::SpaceTree< NODE, DIM >::findSmallestEnclosingNode | ( | const POINTSET & | pointSet, | |
| UINT | maxLevel, | |||
| bool | mustExist, | |||
| INCLUSIONTEST | test | |||
| ) | [inline] |
| SpaceTreePath<DIM> VRS::SpaceTree< NODE, DIM >::findSmallestEnclosingNode | ( | const POINTSET & | pointSet, | |
| UINT | maxLevel = 32, |
|||
| bool | mustExist = true | |||
| ) | [inline] |
| Iterator<SpaceTreePath<DIM> >* VRS::SpaceTree< NODE, DIM >::emptyIterator | ( | ) | [inline] |
| Iterator<SpaceTreePath<DIM> >* VRS::SpaceTree< NODE, DIM >::findIntersectingNodes | ( | const POINTSET & | pointSet, | |
| UINT | level, | |||
| bool | mustExist, | |||
| INTERSECTIONTEST | test | |||
| ) | [inline] |
| Iterator<SpaceTreePath<DIM> >* VRS::SpaceTree< NODE, DIM >::findIntersectingNodes | ( | const POINTSET & | pointSet, | |
| UINT | level, | |||
| bool | mustExist = true | |||
| ) | [inline] |
| Iterator<SpaceTreePath<DIM> >* VRS::SpaceTree< NODE, DIM >::findEnclosingNodes | ( | const POINTSET & | pointSet, | |
| UINT | level, | |||
| bool | mustExist, | |||
| INCLUSIONTEST | test | |||
| ) | [inline] |
| Iterator<SpaceTreePath<DIM> >* VRS::SpaceTree< NODE, DIM >::findEnclosingNodes | ( | const POINTSET & | cell, | |
| UINT | level, | |||
| bool | mustExist = true | |||
| ) | [inline] |
Member Data Documentation
Cell<DIM> VRS::SpaceTree< NODE, DIM >::mainCell_ [protected] |
const ChildNumber VRS::SpaceTree< NODE, DIM >::MaxChilds [static, protected] |
const ChildNumber VRS::SpaceTree< NODE, DIM >::InvalidChildNumber [static, protected] |
TransactionNo VRS::SpaceTree< NODE, DIM >::m_transactionNo [protected] |
Reimplemented from VRS::SharedObj.
The documentation for this class was generated from the following file: