Open CASCADE Technology
7.0.0
|
#include <NCollection_UBTree.hxx>
Data Structures | |
class | Selector |
Memory allocation. More... | |
class | TreeNode |
Public Member Functions | |
NCollection_UBTree (const Handle< NCollection_BaseAllocator > &theAllocator=0L) | |
virtual Standard_Boolean | Add (const TheObjType &theObj, const TheBndType &theBnd) |
virtual Standard_Integer | Select (Selector &theSelector) const |
virtual void | Clear (const Handle< NCollection_BaseAllocator > &aNewAlloc=0L) |
Standard_Boolean | IsEmpty () const |
const TreeNode & | Root () const |
virtual | ~NCollection_UBTree () |
const Handle< NCollection_BaseAllocator > & | Allocator () const |
Protected Member Functions | |
TreeNode & | ChangeLastNode () |
Standard_Integer | Select (const TreeNode &theBranch, Selector &theSelector) const |
The algorithm of unbalanced binary tree of overlapped bounding boxes.
Once the tree of boxes of geometric objects is constructed, the algorithm is capable of fast geometric selection of objects. The tree can be easily updated by adding to it a new object with bounding box.
The time of adding to the tree of one object is O(log(N)), where N is the total number of objects, so the time of building a tree of N objects is O(N(log(N)). The search time of one object is O(log(N)).
Defining various classes inheriting NCollection_UBTree::Selector we can perform various kinds of selection over the same b-tree object
The object may be of any type allowing copying. Among the best suitable solutions there can be a pointer to an object, handled object or integer index of object inside some collection. The bounding object may have any dimension and geometry. The minimal interface of TheBndType (besides public empty and copy constructor and operator =) used in UBTree algorithm is as the following:
To select objects you need to define a class derived from UBTree::Selector that should redefine the necessary virtual methods to maintain the selection condition. The object of this class is also used to retrieve selected objects after search.
|
inline |
Constructor.
|
inlinevirtual |
Desctructor.
|
virtual |
Update the tree with a new object and its bounding box.
theObj | added object |
theBnd | bounding box of the object. |
Reimplemented in NCollection_EBTree< TheObjType, TheBndType >.
|
inline |
Recommended to be used only in sub-classes.
|
inlineprotected |
|
inlinevirtual |
Clears the contents of the tree.
aNewAlloc | Optional: a new allocator that will be used when the tree is rebuilt anew. This makes sense if the memory allocator needs re-initialisation (like NCollection_IncAllocator). By default the previous allocator is kept. |
Reimplemented in NCollection_EBTree< TheObjType, TheBndType >.
|
inline |
|
inline |
|
inlinevirtual |
Searches in the tree all objects conforming to the given selector. return Number of objects accepted
|
protected |
Searches in the branch all objects conforming to the given selector.