NCollection_UBTree< TheObjType, TheBndType > Class Template Reference

#include <NCollection_UBTree.hxx>

Inheritance diagram for NCollection_UBTree< TheObjType, TheBndType >:

Data Structures
class	Selector
	Memory allocation. More...
class	TreeNode

Public Member Functions
	NCollection_UBTree ()
	NCollection_UBTree (const occ::handle< NCollection_BaseAllocator > &theAllocator)
	NCollection_UBTree (NCollection_UBTree &&theOther) noexcept
NCollection_UBTree &	operator= (NCollection_UBTree &&theOther) noexcept
virtual bool	Add (const TheObjType &theObj, const TheBndType &theBnd)
virtual int	Select (Selector &theSelector) const
virtual void	Clear (const occ::handle< NCollection_BaseAllocator > &aNewAlloc=nullptr)
bool	IsEmpty () const noexcept
const TreeNode &	Root () const noexcept
virtual	~NCollection_UBTree ()
const occ::handle< NCollection_BaseAllocator > &	Allocator () const noexcept

Protected Member Functions
TreeNode &	ChangeLastNode () noexcept
int	Select (const TreeNode &theBranch, Selector &theSelector) const

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);
  // Updates me with other bounding
 
  inline bool       IsOut (const MyBndType& other) const;
  // Classifies other bounding relatively me
 
  inline double          SquareExtent() const;
  // Computes the squared maximal linear extent of me.
  // (For box it is the squared diagonal of box)
};

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

NCollection_UBTree() [1/3]

template<class TheObjType , class TheBndType >

NCollection_UBTree< TheObjType, TheBndType >::NCollection_UBTree ( )

inline

Empty constructor.

NCollection_UBTree() [2/3]

template<class TheObjType , class TheBndType >

NCollection_UBTree< TheObjType, TheBndType >::NCollection_UBTree ( const occ::handle< NCollection_BaseAllocator > & theAllocator )

inlineexplicit

Constructor.

NCollection_UBTree() [3/3]

template<class TheObjType , class TheBndType >

NCollection_UBTree< TheObjType, TheBndType >::NCollection_UBTree ( NCollection_UBTree< TheObjType, TheBndType > && theOther )

inlinenoexcept

~NCollection_UBTree()

template<class TheObjType , class TheBndType >

virtual NCollection_UBTree< TheObjType, TheBndType >::~NCollection_UBTree ( )

inlinevirtual

Destructor.

Member Function Documentation

Add()

template<class TheObjType , class TheBndType >

bool NCollection_UBTree< TheObjType, TheBndType >::Add ( const TheObjType & theObj, const TheBndType & theBnd )

virtual

Update the tree with a new object and its bounding box.

Parameters

theObj	added object
theBnd	bounding box of the object.

Returns

always True

Reimplemented in NCollection_EBTree< TheObjType, TheBndType >.

Allocator()

template<class TheObjType , class TheBndType >

const occ::handle< NCollection_BaseAllocator > & NCollection_UBTree< TheObjType, TheBndType >::Allocator ( ) const

inlinenoexcept

Recommended to be used only in sub-classes.

Returns

Allocator object used in this instance of UBTree.

ChangeLastNode()

template<class TheObjType , class TheBndType >

TreeNode & NCollection_UBTree< TheObjType, TheBndType >::ChangeLastNode ( )

inlineprotectednoexcept

Returns

the last added node

Clear()

template<class TheObjType , class TheBndType >

virtual void NCollection_UBTree< TheObjType, TheBndType >::Clear ( const occ::handle< NCollection_BaseAllocator > & aNewAlloc = nullptr )

inlinevirtual

Clears the contents of the tree.

Parameters

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 >.

IsEmpty()

template<class TheObjType , class TheBndType >

bool NCollection_UBTree< TheObjType, TheBndType >::IsEmpty ( ) const

inlinenoexcept

operator=()

template<class TheObjType , class TheBndType >

NCollection_UBTree & NCollection_UBTree< TheObjType, TheBndType >::operator= ( NCollection_UBTree< TheObjType, TheBndType > && theOther )

inlinenoexcept

Root()

template<class TheObjType , class TheBndType >

const TreeNode & NCollection_UBTree< TheObjType, TheBndType >::Root ( ) const

inlinenoexcept

Returns

the root node of the tree

Select() [1/2]

template<class TheObjType , class TheBndType >

int NCollection_UBTree< TheObjType, TheBndType >::Select ( const TreeNode & theBranch, Selector & theSelector ) const

protected

Searches in the branch all objects conforming to the given selector.

Returns

the number of objects accepted

Select() [2/2]

template<class TheObjType , class TheBndType >

virtual int NCollection_UBTree< TheObjType, TheBndType >::Select ( Selector & theSelector ) const

inlinevirtual

Searches in the tree all objects conforming to the given selector.

Returns

Number of objects accepted

---

The documentation for this class was generated from the following file:

• NCollection_UBTree.hxx