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

YBinBounds	m_yBinBounds
	bins range on r

int	m_level
	Level of node in the tree.

This *	m_parent
	Pointer to the parent node.

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

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

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_level(level)
      , m_parent(level > 0 ? parent : nullptr)
      , 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 132 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 118 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 103 of file QuadTreeNode.h.

      {
        m_items.clear();
      }

◆ getChildren()

Children & getChildren ( )

inline

Returns the children structure of this node.

Definition at line 109 of file QuadTreeNode.h.

      {
        return m_children;
      }

◆ getItems()

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

inline

Get items from node.

Definition at line 91 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 126 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 97 of file QuadTreeNode.h.

      {
        return m_items.size();
      }

◆ getParent()

This * getParent ( ) const

inline

Return pointer to the parent of the node.

Definition at line 144 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 168 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 174 of file QuadTreeNode.h.

      {
        return m_xBinBounds[2 * iBin];
      }

◆ getXMax()

AX getXMax ( ) const

inline

Get maximal "Theta" value of the node.

Definition at line 162 of file QuadTreeNode.h.

      {
        return m_xBinBounds.back();
      }

◆ getXMin()

AX getXMin ( ) const

inline

Get minimal "Theta" value of the node.

Definition at line 156 of file QuadTreeNode.h.

      {
        return m_xBinBounds.front();
      }

◆ getXNbins()

constexpr int getXNbins ( ) const

inlineconstexpr

Get number of bins in "Theta" direction.

Definition at line 150 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 180 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 204 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 209 of file QuadTreeNode.h.

      {
        return m_yBinBounds[2 * iBin];
      }

◆ getYMax()

AY getYMax ( ) const

inline

Get maximal "r" value of the node.

Definition at line 198 of file QuadTreeNode.h.

      {
        return m_yBinBounds.back();
      }

◆ getYMin()

AY getYMin ( ) const

inline

Get minimal "r" value of the node.

Definition at line 192 of file QuadTreeNode.h.

      {
        return m_yBinBounds.front();
      }

◆ getYNbins()

constexpr int getYNbins ( ) const

inlineconstexpr

Get number of bins in "r" direction.

Definition at line 186 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 215 of file QuadTreeNode.h.

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

◆ insertItem()

void insertItem ( AItem * item )

inline

Insert item into node.

Definition at line 79 of file QuadTreeNode.h.

      {
        m_items.push_back(item);
      }

◆ reserveItems()

void reserveItems ( int nItems )

inline

Reserve memory for holding items.

Definition at line 85 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 138 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 237 of file QuadTreeNode.h.

◆ m_filled

bool m_filled

private

Is the node has been filled with items.

Definition at line 240 of file QuadTreeNode.h.

◆ m_items

std::vector<AItem*> m_items

private

Vector of items which belongs to the node.

Definition at line 234 of file QuadTreeNode.h.

◆ m_level

int m_level

private

Level of node in the tree.

Definition at line 228 of file QuadTreeNode.h.

◆ m_parent

This* m_parent

private

Pointer to the parent node.

Definition at line 231 of file QuadTreeNode.h.

◆ m_xBinBounds

XBinBounds m_xBinBounds

private

bins range on theta

Definition at line 222 of file QuadTreeNode.h.

◆ m_yBinBounds

YBinBounds m_yBinBounds

private

bins range on r

Definition at line 225 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