Class which holds quadtree structure. More...

#include <QuadTreeNode.h>

Public Types
using	This = QuadTreeNode< AX, AY, AItem >
	Type of this class.

using	XSpan = std::array< AX, 2 >
	Type for a span in the X direction that is covered by the tree.

using	YSpan = std::array< AY, 2 >
	Type for a span in the Y direction that is covered by the tree.

using	XBinBounds = std::array< AX, 4 >
	Type to store the minimum and maximum of the two bins in X direction.

using	YBinBounds = std::array< AY, 4 >
	Type to store the minimum and maximum of the two bins in Y direction.

using	Children = std::vector< This >
	Type of the child node structure for this node.

Public Member Functions
	QuadTreeNode (XSpan xSpan, YSpan ySpan, int level, This *parent)
	Constructor setting up the potential division points.

void	insertItem (AItem *item)
	Insert item into node.

void	reserveItems (int nItems)
	Reserve memory for holding items.

std::vector< AItem * > &	getItems ()
	Get items from node.

int	getNItems () const
	Check if the node passes threshold on number of hits.

void	clearItems ()
	Clear items which the node holds.

Children &	getChildren ()
	Returns the children structure of this node.

void	clearChildren ()
	Clear items which the node holds and destroy all children below this node.

int	getLevel () const
	Returns level of the node in tree (i.e., how much ancestors the node has)

bool	checkFilled () const
	Check whether node has been processed, i.e.

void	setFilled ()
	Set status of node to "filled" (children nodes has been filled)

This *	getParent () const
	Return pointer to the parent of the node.

constexpr int	getXNbins () const
	Get number of bins in "Theta" direction.

AX	getXMin () const
	Get minimal "Theta" value of the node.

AX	getXMax () const
	Get maximal "Theta" value of the node.

AX	getXBinWidth (int iBin)
	Getter for the width of the iBin bin in "Theta" direction.

AX	getXLowerBound (int iBin) const
	Get lower "Theta" value of given bin.

AX	getXUpperBound (int iBin) const
	Get upper "Theta" value of given bin.

constexpr int	getYNbins () const
	Get number of bins in "r" direction.

AY	getYMin () const
	Get minimal "r" value of the node.

AY	getYMax () const
	Get maximal "r" value of the node.

AY	getYBinWidth (int iBin)
	Getter for the width of the iBin bin in "r" direction.

AY	getYLowerBound (int iBin) const
	Get lower "r" value of given bin.

AY	getYUpperBound (int iBin) const
	Get upper "r" value of given bin.

Private Attributes
XBinBounds	m_xBinBounds
	bins range on theta

std::vector< AItem * >	m_items
	Vector of items which belongs to the node.

std::vector< This >	m_children
	Pointers to the children nodes.

YBinBounds	m_yBinBounds
	bins range on r

This *	m_parent
	Pointer to the parent node.

int	m_level
	Level of node in the tree.

bool	m_filled
	Is the node has been filled with items.

Detailed Description

template<typename AX, typename AY, class AItem>
class Belle2::TrackFindingCDC::QuadTreeNode< AX, AY, AItem >

Class which holds quadtree structure.

Template Parameters

AX	type of the X-axis variable
AY	type of the Y-axis variable
AItem	type of the objects which are filled into QuadTree

Definition at line 29 of file QuadTreeNode.h.

Member Typedef Documentation

◆ Children

using Children = std::vector<This>

Type of the child node structure for this node.

Definition at line 48 of file QuadTreeNode.h.

◆ This

using This = QuadTreeNode<AX, AY, AItem>

Type of this class.

Definition at line 33 of file QuadTreeNode.h.

◆ XBinBounds

using XBinBounds = std::array<AX, 4>

Type to store the minimum and maximum of the two bins in X direction.

Definition at line 42 of file QuadTreeNode.h.

◆ XSpan

using XSpan = std::array<AX, 2>

Type for a span in the X direction that is covered by the tree.

Definition at line 36 of file QuadTreeNode.h.

◆ YBinBounds

using YBinBounds = std::array<AY, 4>

Type to store the minimum and maximum of the two bins in Y direction.

Definition at line 45 of file QuadTreeNode.h.

◆ YSpan

using YSpan = std::array<AY, 2>

Type for a span in the Y direction that is covered by the tree.

Definition at line 39 of file QuadTreeNode.h.

Constructor & Destructor Documentation

◆ QuadTreeNode()

QuadTreeNode	(	XSpan	xSpan,
		YSpan	ySpan,
		int	level,
		This *	parent
	)

inline

Constructor setting up the potential division points.

Cppcheck may warn to pass the spans by reference here, however this would come at performance penalty.

Definition at line 57 of file QuadTreeNode.h.

        : m_xBinBounds {
        xSpan[0],
        xSpan[0] + (xSpan[1] - xSpan[0]) / 2,
        xSpan[1] - (xSpan[1] - xSpan[0]) / 2,
        xSpan[1]
      }
      , m_yBinBounds({
        ySpan[0],
        ySpan[0] + (ySpan[1] - ySpan[0]) / 2,
        ySpan[1] - (ySpan[1] - ySpan[0]) / 2,
        ySpan[1]
      })
      , m_parent(level > 0 ? parent : nullptr)
      , m_level(level)
      , m_filled(false)
      {
        B2ASSERT("QuadTree datastructure only supports levels < 255", level < 255);
      }

Member Function Documentation

◆ checkFilled()

bool checkFilled ( ) const

inline

Check whether node has been processed, i.e.

children nodes has been filled

Definition at line 131 of file QuadTreeNode.h.

      {
        return m_filled;
      }

◆ clearChildren()

void clearChildren ( )

inline

Clear items which the node holds and destroy all children below this node.

This method must only be called on the root node, for fast QuadTree reusage

Definition at line 117 of file QuadTreeNode.h.

      {
        // automatically removes all lower level objects
        m_children.clear();
        m_filled = false;
      }

◆ clearItems()

void clearItems ( )

inline

Clear items which the node holds.

Definition at line 102 of file QuadTreeNode.h.

      {
        m_items.clear();
      }

◆ getChildren()

Children & getChildren ( )

inline

Returns the children structure of this node.

Definition at line 108 of file QuadTreeNode.h.

      {
        return m_children;
      }

◆ getItems()

std::vector< AItem * > & getItems ( )

inline

Get items from node.

Definition at line 90 of file QuadTreeNode.h.

      {
        return m_items;
      }

◆ getLevel()

int getLevel ( ) const

inline

Returns level of the node in tree (i.e., how much ancestors the node has)

Definition at line 125 of file QuadTreeNode.h.

      {
        return m_level;
      }

◆ getNItems()

int getNItems ( ) const

inline

Check if the node passes threshold on number of hits.

Definition at line 96 of file QuadTreeNode.h.

      {
        return m_items.size();
      }

◆ getParent()

This * getParent ( ) const

inline

Return pointer to the parent of the node.

Definition at line 143 of file QuadTreeNode.h.

      {
        return m_parent;
      }

◆ getXBinWidth()

AX getXBinWidth ( int iBin )

inline

Getter for the width of the iBin bin in "Theta" direction.

Definition at line 167 of file QuadTreeNode.h.

      {
        return std::abs(getXUpperBound(iBin) - getXLowerBound(iBin));
      }

◆ getXLowerBound()

AX getXLowerBound ( int iBin ) const

inline

Get lower "Theta" value of given bin.

Definition at line 173 of file QuadTreeNode.h.

      {
        return m_xBinBounds[2 * iBin];
      }

◆ getXMax()

AX getXMax ( ) const

inline

Get maximal "Theta" value of the node.

Definition at line 161 of file QuadTreeNode.h.

      {
        return m_xBinBounds.back();
      }

◆ getXMin()

AX getXMin ( ) const

inline

Get minimal "Theta" value of the node.

Definition at line 155 of file QuadTreeNode.h.

      {
        return m_xBinBounds.front();
      }

◆ getXNbins()

constexpr int getXNbins ( ) const

inlineconstexpr

Get number of bins in "Theta" direction.

Definition at line 149 of file QuadTreeNode.h.

      {
        return m_xBinBounds.size() / 2;
      }

◆ getXUpperBound()

AX getXUpperBound ( int iBin ) const

inline

Get upper "Theta" value of given bin.

Definition at line 179 of file QuadTreeNode.h.

      {
        return m_xBinBounds[2 * iBin + 1];
      }

◆ getYBinWidth()

AY getYBinWidth ( int iBin )

inline

Getter for the width of the iBin bin in "r" direction.

Definition at line 203 of file QuadTreeNode.h.

      {
        return std::abs(getYUpperBound(iBin) - getYLowerBound(iBin));
      }

◆ getYLowerBound()

AY getYLowerBound ( int iBin ) const

inline

Get lower "r" value of given bin.

Definition at line 208 of file QuadTreeNode.h.

      {
        return m_yBinBounds[2 * iBin];
      }

◆ getYMax()

AY getYMax ( ) const

inline

Get maximal "r" value of the node.

Definition at line 197 of file QuadTreeNode.h.

      {
        return m_yBinBounds.back();
      }

◆ getYMin()

AY getYMin ( ) const

inline

Get minimal "r" value of the node.

Definition at line 191 of file QuadTreeNode.h.

      {
        return m_yBinBounds.front();
      }

◆ getYNbins()

constexpr int getYNbins ( ) const

inlineconstexpr

Get number of bins in "r" direction.

Definition at line 185 of file QuadTreeNode.h.

      {
        return m_yBinBounds.size() / 2;
      }

◆ getYUpperBound()

AY getYUpperBound ( int iBin ) const

inline

Get upper "r" value of given bin.

Definition at line 214 of file QuadTreeNode.h.

      {
        return m_yBinBounds[2 * iBin + 1];
      }

◆ insertItem()

void insertItem ( AItem * item )

inline

Insert item into node.

Definition at line 78 of file QuadTreeNode.h.

      {
        m_items.push_back(item);
      }

◆ reserveItems()

void reserveItems ( int nItems )

inline

Reserve memory for holding items.

Definition at line 84 of file QuadTreeNode.h.

      {
        m_items.reserve(nItems);
      }

◆ setFilled()

void setFilled ( )

inline

Set status of node to "filled" (children nodes has been filled)

Definition at line 137 of file QuadTreeNode.h.

      {
        m_filled = true;
      }

Member Data Documentation

◆ m_children

std::vector<This> m_children

private

Pointers to the children nodes.

Definition at line 227 of file QuadTreeNode.h.

◆ m_filled

bool m_filled

private

Is the node has been filled with items.

Definition at line 239 of file QuadTreeNode.h.

◆ m_items

std::vector<AItem*> m_items

private

Vector of items which belongs to the node.

Definition at line 224 of file QuadTreeNode.h.

◆ m_level

int m_level

private

Level of node in the tree.

Definition at line 236 of file QuadTreeNode.h.

◆ m_parent

This* m_parent

private

Pointer to the parent node.

Definition at line 233 of file QuadTreeNode.h.

◆ m_xBinBounds

XBinBounds m_xBinBounds

private

bins range on theta

Definition at line 221 of file QuadTreeNode.h.

◆ m_yBinBounds

YBinBounds m_yBinBounds

private

bins range on r

Definition at line 230 of file QuadTreeNode.h.

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

tracking/trackFindingCDC/legendre/quadtree/include/QuadTreeNode.h

Public Types

Public Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Children

◆ This

◆ XBinBounds

◆ XSpan

◆ YBinBounds

◆ YSpan

Constructor & Destructor Documentation

◆ QuadTreeNode()

Member Function Documentation

◆ checkFilled()

◆ clearChildren()

◆ clearItems()

◆ getChildren()

◆ getItems()

◆ getLevel()

◆ getNItems()

◆ getParent()

◆ getXBinWidth()

◆ getXLowerBound()

◆ getXMax()

◆ getXMin()

◆ getXNbins()

◆ getXUpperBound()

◆ getYBinWidth()

◆ getYLowerBound()

◆ getYMax()

◆ getYMin()

◆ getYNbins()

◆ getYUpperBound()

◆ insertItem()

◆ reserveItems()

◆ setFilled()

Member Data Documentation

◆ m_children

◆ m_filled

◆ m_items

◆ m_level

◆ m_parent

◆ m_xBinBounds

◆ m_yBinBounds