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

template<typename AX, typename AY, class AItem>

using Children = std::vector<This>

Type of the child node structure for this node.

Definition at line 48 of file QuadTreeNode.h.

◆ This

template<typename AX, typename AY, class AItem>

using This = QuadTreeNode<AX, AY, AItem>

Type of this class.

Definition at line 33 of file QuadTreeNode.h.

◆ XBinBounds

template<typename AX, typename AY, class AItem>

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

template<typename AX, typename AY, class AItem>

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

template<typename AX, typename AY, class AItem>

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

template<typename AX, typename AY, class AItem>

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()

template<typename AX, typename AY, class AItem>

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 56 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()

template<typename AX, typename AY, class AItem>

bool checkFilled ( ) const

inline

Check whether node has been processed, i.e.

children nodes has been filled

Definition at line 130 of file QuadTreeNode.h.

      {
        return m_filled;
      }

◆ clearChildren()

template<typename AX, typename AY, class AItem>

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 116 of file QuadTreeNode.h.

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

◆ clearItems()

template<typename AX, typename AY, class AItem>

void clearItems ( )

inline

Clear items which the node holds.

Definition at line 101 of file QuadTreeNode.h.

      {
        m_items.clear();
      }

◆ getChildren()

template<typename AX, typename AY, class AItem>

Children & getChildren ( )

inline

Returns the children structure of this node.

Definition at line 107 of file QuadTreeNode.h.

      {
        return m_children;
      }

◆ getItems()

template<typename AX, typename AY, class AItem>

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

inline

Get items from node.

Definition at line 89 of file QuadTreeNode.h.

      {
        return m_items;
      }

◆ getLevel()

template<typename AX, typename AY, class AItem>

int getLevel ( ) const

inline

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

Definition at line 124 of file QuadTreeNode.h.

      {
        return m_level;
      }

◆ getNItems()

template<typename AX, typename AY, class AItem>

int getNItems ( ) const

inline

Check if the node passes threshold on number of hits.

Definition at line 95 of file QuadTreeNode.h.

      {
        return m_items.size();
      }

◆ getParent()

template<typename AX, typename AY, class AItem>

This * getParent ( ) const

inline

Return pointer to the parent of the node.

Definition at line 142 of file QuadTreeNode.h.

      {
        return m_parent;
      }

◆ getXBinWidth()

template<typename AX, typename AY, class AItem>

AX getXBinWidth ( int iBin )

inline

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

Definition at line 166 of file QuadTreeNode.h.

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

◆ getXLowerBound()

template<typename AX, typename AY, class AItem>

AX getXLowerBound ( int iBin ) const

inline

Get lower "Theta" value of given bin.

Definition at line 172 of file QuadTreeNode.h.

      {
        return m_xBinBounds[2 * iBin];
      }

◆ getXMax()

template<typename AX, typename AY, class AItem>

AX getXMax ( ) const

inline

Get maximal "Theta" value of the node.

Definition at line 160 of file QuadTreeNode.h.

      {
        return m_xBinBounds.back();
      }

◆ getXMin()

template<typename AX, typename AY, class AItem>

AX getXMin ( ) const

inline

Get minimal "Theta" value of the node.

Definition at line 154 of file QuadTreeNode.h.

      {
        return m_xBinBounds.front();
      }

◆ getXNbins()

template<typename AX, typename AY, class AItem>

int getXNbins ( ) const

inlineconstexpr

Get number of bins in "Theta" direction.

Definition at line 148 of file QuadTreeNode.h.

      {
        return m_xBinBounds.size() / 2;
      }

◆ getXUpperBound()

template<typename AX, typename AY, class AItem>

AX getXUpperBound ( int iBin ) const

inline

Get upper "Theta" value of given bin.

Definition at line 178 of file QuadTreeNode.h.

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

◆ getYBinWidth()

template<typename AX, typename AY, class AItem>

AY getYBinWidth ( int iBin )

inline

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

Definition at line 202 of file QuadTreeNode.h.

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

◆ getYLowerBound()

template<typename AX, typename AY, class AItem>

AY getYLowerBound ( int iBin ) const

inline

Get lower "r" value of given bin.

Definition at line 207 of file QuadTreeNode.h.

      {
        return m_yBinBounds[2 * iBin];
      }

◆ getYMax()

template<typename AX, typename AY, class AItem>

AY getYMax ( ) const

inline

Get maximal "r" value of the node.

Definition at line 196 of file QuadTreeNode.h.

      {
        return m_yBinBounds.back();
      }

◆ getYMin()

template<typename AX, typename AY, class AItem>

AY getYMin ( ) const

inline

Get minimal "r" value of the node.

Definition at line 190 of file QuadTreeNode.h.

      {
        return m_yBinBounds.front();
      }

◆ getYNbins()

template<typename AX, typename AY, class AItem>

int getYNbins ( ) const

inlineconstexpr

Get number of bins in "r" direction.

Definition at line 184 of file QuadTreeNode.h.

      {
        return m_yBinBounds.size() / 2;
      }

◆ getYUpperBound()

template<typename AX, typename AY, class AItem>

AY getYUpperBound ( int iBin ) const

inline

Get upper "r" value of given bin.

Definition at line 213 of file QuadTreeNode.h.

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

◆ insertItem()

template<typename AX, typename AY, class AItem>

void insertItem ( AItem * item )

inline

Insert item into node.

Definition at line 77 of file QuadTreeNode.h.

      {
        m_items.push_back(item);
      }

◆ reserveItems()

template<typename AX, typename AY, class AItem>

void reserveItems ( int nItems )

inline

Reserve memory for holding items.

Definition at line 83 of file QuadTreeNode.h.

      {
        m_items.reserve(nItems);
      }

◆ setFilled()

template<typename AX, typename AY, class AItem>

void setFilled ( )

inline

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

Definition at line 136 of file QuadTreeNode.h.

      {
        m_filled = true;
      }

Member Data Documentation

◆ m_children

template<typename AX, typename AY, class AItem>

std::vector<This> m_children

private

Pointers to the children nodes.

Definition at line 226 of file QuadTreeNode.h.

◆ m_filled

template<typename AX, typename AY, class AItem>

bool m_filled

private

Is the node has been filled with items.

Definition at line 238 of file QuadTreeNode.h.

◆ m_items

template<typename AX, typename AY, class AItem>

std::vector<AItem*> m_items

private

Vector of items which belongs to the node.

Definition at line 223 of file QuadTreeNode.h.

◆ m_level

template<typename AX, typename AY, class AItem>

int m_level

private

Level of node in the tree.

Definition at line 235 of file QuadTreeNode.h.

◆ m_parent

template<typename AX, typename AY, class AItem>

This* m_parent

private

Pointer to the parent node.

Definition at line 232 of file QuadTreeNode.h.

◆ m_xBinBounds

template<typename AX, typename AY, class AItem>

XBinBounds m_xBinBounds

private

bins range on theta

Definition at line 220 of file QuadTreeNode.h.

◆ m_yBinBounds

template<typename AX, typename AY, class AItem>

YBinBounds m_yBinBounds

private

bins range on r

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