NCollection_UBTree< TheObjType, TheBndType > Class Template Reference
#include <NCollection_UBTree.hxx>
Inheritance diagram for NCollection_UBTree< TheObjType, TheBndType >:
[legend]
Detailed Description
template<class TheObjType, class TheBndType>
class NCollection_UBTree< TheObjType, TheBndType >
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:
class MyBndType
{
public:
inline void Add (const MyBndType& other);
inline Standard_Boolean IsOut (const MyBndType& other) const;
inline Standard_Real SquareExtent() const;
};
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.
Constructor & Destructor Documentation
Member Function Documentation
template<class TheObjType, class TheBndType> |
Standard_Boolean NCollection_UBTree< TheObjType, TheBndType >::Add |
( |
const TheObjType & |
theObj, |
|
|
const TheBndType & |
theBnd |
|
) |
[virtual] |
|
template<class TheObjType, class TheBndType> |
TreeNode& NCollection_UBTree< TheObjType, TheBndType >::ChangeLastNode |
( |
|
) |
[inline, protected] |
|
|
- Returns:
- the last added node
|
|
Recommended to be used only in sub-classes. - Returns:
- Allocator object used in this instance of UBTree.
|
template<class TheObjType, class TheBndType> |
const TreeNode& NCollection_UBTree< TheObjType, TheBndType >::Root |
( |
|
) |
const [inline] |
|
|
- Returns:
- the root node of the tree
|
|
Searches in the branch all objects conforming to the given selector. - Returns:
- the number of objects accepted
|
|
Searches in the tree all objects conforming to the given selector. return Number of objects accepted |
Field Documentation
The documentation for this class was generated from the following file:
Generated on Mon Aug 25 13:13:02 2008 for OpenCASCADE by
1.4.1