VRS::DynamicQuadtree< CONTENT > Class Template Reference
#include <vrs/container/quadtree.h>
Public Types | |
| typedef SpaceTreePath< 2 > | Path |
| typedef DynamicSpaceTree < CONTENT, 2 >::NodePointer | NodePointer |
Public Member Functions | |
| DynamicQuadtree (const Vector &p1, const Vector &p2, const Vector &xAxis=Vector(1, 0, 0), const Vector &yAxis=Vector(0, 1, 0)) | |
| SpaceTreePath< 2 > | findContainingNode (const Vector &point, UINT level, bool mustExist=true) |
| Iterator< SpaceTreePath< 2 > > * | findBoundsIntersectingNodes (const Bounds &bounds, UINT level, bool mustExist=true) |
| SpaceTreePath< 2 > | findSmallestBoundsEnclosingNode (const Bounds &bounds, UINT maxLevel=16, bool mustExist=true) |
| virtual QuadtreeCell | getQuadtreeCell (const Path &path) |
| virtual QuadtreeCell | getQuadtreeCell (const NodePointer &np) |
| const Matrix & | getTransform () |
| const Matrix & | getInverseTransform () |
Detailed Description
template<typename CONTENT>
class VRS::DynamicQuadtree< CONTENT >
DynamicQuadtree and StaticQuadtree are 2-dimensional specializations of DynamicSpaceTree and StaticSpaceTree that are extended by constructors and methods that accept VRS Vector and Bounds.They allow to specify a quadtree on an arbitrary plane P in 3d space. By default P is the (x,y)-plane.
See below for further explanation of the plane handling and spacetree.h for further information about SpaceTree.
Member Typedef Documentation
| typedef SpaceTreePath<2> VRS::DynamicQuadtree< CONTENT >::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 from VRS::DynamicSpaceTree< CONTENT, 2 >.
| typedef DynamicSpaceTree<CONTENT, 2>::NodePointer VRS::DynamicQuadtree< CONTENT >::NodePointer |
Reimplemented from VRS::DynamicSpaceTree< CONTENT, 2 >.
Constructor & Destructor Documentation
| VRS::DynamicQuadtree< CONTENT >::DynamicQuadtree | ( | const Vector & | p1, | |
| const Vector & | p2, | |||
| const Vector & | xAxis = Vector(1, 0, 0), |
|||
| const Vector & | yAxis = Vector(0, 1, 0) | |||
| ) |
The (optional) two coordinate axes define a plane. The area supported by the quadtree is specified by two corner points p1, p2. xAxis and yAxis define a plane containing the origin and a 2D coordinate system for this plane. Similar to the up vector in camera specifications the yAxis is made orthogonal to the xAxis. The portion of p1, p2 that is orthogonal to the plane defined by xAxis and yAxis is ignored.
The plane specified by xAxis and yAxis is referred to as P in the following.
Member Function Documentation
| SpaceTreePath<2> VRS::DynamicQuadtree< CONTENT >::findContainingNode | ( | const Vector & | point, | |
| UINT | level, | |||
| bool | mustExist = true | |||
| ) |
Return the path to the node containing a given point. The portion of "point" that is orthogonal to P is ignored.
| Iterator<SpaceTreePath<2> >* VRS::DynamicQuadtree< CONTENT >::findBoundsIntersectingNodes | ( | const Bounds & | bounds, | |
| UINT | level, | |||
| bool | mustExist = true | |||
| ) |
Returns pathes to all nodes that intersect the projection B of "bounds" on P. Note that by default (i.e. if P is the xy-plane) B is simply the quad {(lower,left), (upper,right)}, that you get by ignoring the z-coordinates of the points defining bounds.
| SpaceTreePath<2> VRS::DynamicQuadtree< CONTENT >::findSmallestBoundsEnclosingNode | ( | const Bounds & | bounds, | |
| UINT | maxLevel = 16, |
|||
| bool | mustExist = true | |||
| ) |
Returns the path of the smallest node (i.e. the one on the highest tree level) that contains the projection of "bounds" onto P. The following is important only if you want a) to use spatial search methods of the base class for own shapes, and therefore to implement own intersection tests and inclusion tests AND b) to choose another plane for P than the xy-plane.
Internally the QuadTree is always defined on the xy-plane, but the spatial search methods rotate the given point/bounds according to the specified plane. So your intersection test and inclusion test also need to rotate a given shape using the matrix obtained by getTransform() before performing the intersection test.
| virtual QuadtreeCell VRS::DynamicQuadtree< CONTENT >::getQuadtreeCell | ( | const Path & | path | ) | [virtual] |
| virtual QuadtreeCell VRS::DynamicQuadtree< CONTENT >::getQuadtreeCell | ( | const NodePointer & | np | ) | [virtual] |
| const Matrix& VRS::DynamicQuadtree< CONTENT >::getTransform | ( | ) |
| const Matrix& VRS::DynamicQuadtree< CONTENT >::getInverseTransform | ( | ) |
The documentation for this class was generated from the following file: