itk::PSMPointTree< VDimension > Class Template Reference

#include <itkPSMPointTree.h>

Inheritance diagram for itk::PSMPointTree< VDimension >:

Collaboration diagram for itk::PSMPointTree< VDimension >:

Public Types
typedef PSMPointTree	Self
typedef DataObject	Superclass
typedef SmartPointer< Self >	Pointer
typedef SmartPointer< const Self >	ConstPointer
typedef WeakPointer< const Self >	ConstWeakPointer
typedef PSMPointTreeNode< VDimension >	NodeType
typedef NodeType::Pointer	NodePointerType
typedef PSMPointTreeNode< VDimension >::PointType	PointType
typedef NodeType::PointListType	PointListType
typedef std::vector< typename PointListType::const_iterator >	PointIteratorListType

Public Member Functions
	itkNewMacro (Self)
	itkTypeMacro (PSMPointTree, DataObject)
	itkStaticConstMacro (Dimension, unsigned int, VDimension)
	itkStaticConstMacro (BranchesPerNode, int,(powstruct< 2, VDimension >::c))
	itkGetMacro (Depth, unsigned int)
void	ConstructTree (const PointType &, const PointType &, unsigned int)
PointIteratorListType	FindPointsInRegion (const PointType &, const PointType &) const
unsigned int	FindPointsInRegion (const PointType &, const PointType &, PointIteratorListType &) const
NodePointerType	GetNode (const PointType &)
const NodePointerType	GetNode (const PointType &) const
	itkGetObjectMacro (Root, NodeType)
	itkSetObjectMacro (Root, NodeType)
PointListType::iterator	AddPoint (const PointType &, unsigned int, NodePointerType &)
PointListType::iterator	AddPoint (const PointType &p, unsigned int i)
bool	Overlap (const NodePointerType &, const PointType &, const PointType &) const
bool	RegionContains (const PointType &p, const PointType &lowerbound, const PointType &upperbound) const
void	PrintSelf (std::ostream &os, Indent indent) const

Protected Member Functions
void	BranchNode (NodePointerType &, unsigned int)
void	FindOneNodeInRegion (const NodePointerType &, const PointType &, const PointType &, PointIteratorListType &) const

Detailed Description

template<unsigned int VDimension>
class itk::PSMPointTree< VDimension >

A tree data container, templated over node type, whose nodes are associated with bounding boxes in a rectangular domain, and that has 2^D branches at each node, where D is the dimensionality of the domain. In 2D this is a quad-tree, and in 3D this is an octree, etc. The tree is constructed by specifying a region and a tree depth, then calling ConstructTree(). This class was designed for use as a multidimensional quad/octree binning structure for itkPSMNeighborhood classes.

Definition at line 174 of file itkPSMPointTree.h.

Member Typedef Documentation

template<unsigned int VDimension>

typedef NodeType::Pointer itk::PSMPointTree< VDimension >::NodePointerType

The real node type, which is a actually pointer to what we are calling NodeTypes.

Definition at line 188 of file itkPSMPointTree.h.

template<unsigned int VDimension>

typedef PSMPointTreeNode<VDimension> itk::PSMPointTree< VDimension >::NodeType

Shorthand for the object pointed to by each node.

Definition at line 185 of file itkPSMPointTree.h.

template<unsigned int VDimension>

typedef NodeType::PointListType itk::PSMPointTree< VDimension >::PointListType

Types defined by the NodeType.

Definition at line 194 of file itkPSMPointTree.h.

template<unsigned int VDimension>

typedef PSMPointTreeNode<VDimension>::PointType itk::PSMPointTree< VDimension >::PointType

Point type used by nodes for upper and lower bounds.

Definition at line 191 of file itkPSMPointTree.h.

template<unsigned int VDimension>

typedef PSMPointTree itk::PSMPointTree< VDimension >::Self

Standard class typedefs

Definition at line 178 of file itkPSMPointTree.h.

Member Function Documentation

template<unsigned int VDimension>

PSMPointTree< VDimension >::PointListType::iterator itk::PSMPointTree< VDimension >::AddPoint	(	const PointType &	point,
		unsigned int	idx,
		NodePointerType &	node
	)

Associates a point and, optionally, an index with the appropriate leaf node. This method starts at the root of the tree and uses the Contains method to query branches at each node, following the first branch it finds whose bounding box contains this point. When it reaches a leaf node, the point is added to that node's list, along with the specified index (if any). This method returns an iterator pointing to the new list element (e.g., for quick deletion or reference of the point) and, optionally, will set a given smart pointer to point to the leaf node. If the specified point is not contained within the domain, then this method will throw an exception.

Definition at line 121 of file itkPSMPointTree.hxx.

    {
      NodePointerType it = this->m_Root;

      if ( ! it->Contains(point))
      {
        itkExceptionMacro("Point " << point << " is not contained within tree domain " << it->GetLowerBound() << " - " << it->GetUpperBound());
      }

      while (! it->IsLeaf() )
      {
        for (unsigned int i = 0; i < BranchesPerNode; i++)
        {
          if (it->GetBranch(i)->Contains(point))
          {
            it = it->GetBranch(i);
            break;
          }
        }
      }
      node = it;
      return it->InsertElement( PSMPointIndexPair<VDimension>(point, idx) );
    }

template<unsigned int VDimension>

void itk::PSMPointTree< VDimension >::BranchNode ( NodePointerType &  parent, unsigned int  level  )

protected

Add the appropriate number of empty child nodes to a given node. The second parameter is the level in the tree.

Definition at line 162 of file itkPSMPointTree.hxx.

    {
      // Called from a leaf node.
      if (level > m_Depth) return;

      PointType midpoint, upper, lower;
      int thresh[VDimension];
      for (unsigned int dim = 0; dim < VDimension; dim++)
      {
        thresh[dim] = 1;
        midpoint[dim] = ( parent->GetLowerBound()[dim] + parent->GetUpperBound()[dim] ) /  2.0;
      }

      for (unsigned int b = 0; b <  BranchesPerNode; b++)
      {
        for (unsigned int dim = 0; dim <  VDimension; dim++)
        {
          // toggle use low/high lower and upper bounds
          if ( b % ( static_cast<unsigned int>(pow(2.0, (int)dim)) ) == 0 )
          {        thresh[dim] = 1 - thresh[dim];        }

          if (  thresh[dim] == 0 )
          {
            lower[dim] = parent->GetLowerBound()[dim];
            upper[dim] = midpoint[dim];
          }
          else
          {
            lower[dim] = midpoint[dim];
            upper[dim] = parent->GetUpperBound()[dim];
          }
        }

        NodePointerType newNode = NodeType::New();
        newNode->SetLowerBound(lower);
        newNode->SetUpperBound(upper);

        parent->SetBranch(b, newNode);

        this->BranchNode(newNode, level+1);
      }
    }

template<unsigned int VDimension>

void itk::PSMPointTree< VDimension >::ConstructTree	(	const PointType &	lowerbound,
		const PointType &	upperbound,
		unsigned int	depth
	)

Construct the tree to the specified depth. The bounding box of the root node is specified with the lower bound and upper bound points respectively.

Definition at line 148 of file itkPSMPointTree.hxx.

    {
      m_Depth = depth;

      NodePointerType n = NodeType::New();
      n->SetLowerBound(lowerbound);
      n->SetUpperBound(upperbound);

      this->SetRoot(n);
      this->BranchNode(n, 1);
    }

template<unsigned int VDimension>

void itk::PSMPointTree< VDimension >::FindOneNodeInRegion ( const NodePointerType &  it, const PointType &  lowerbound, const PointType &  upperbound, PointIteratorListType &  pointlist  ) const

protected

Find one of the nodes that overlaps the specified region and appends all of its points to the specified list. The method is used by FindPointsInRegion and is called recursively.

Definition at line 90 of file itkPSMPointTree.hxx.

    {
      // If this node is a leaf node, then add to the list if there is overlap.
      if (it ->IsLeaf())
      {
        if ( this->Overlap(it, lowerbound, upperbound) )
        {
          // Add all node's points to the list that are within the given region.
          for (typename PointListType::const_iterator pit = it->GetList().begin();
              pit != it->GetList().end(); pit++)
          {
            if (this->RegionContains(pit->Point, lowerbound, upperbound) )
            {
              pointlist.push_back(pit);
            }
          }
        }
      }
      else   // Otherwise, call this method on each branch.
      {
        for (unsigned int i = 0; i < BranchesPerNode; i++)
        {
          this->FindOneNodeInRegion(it->GetBranch(i), lowerbound, upperbound, pointlist);
        }
      }
    }

template<unsigned int VDimension>

PSMPointTree< VDimension >::PointIteratorListType itk::PSMPointTree< VDimension >::FindPointsInRegion	(	const PointType &	lowerbound,
		const PointType &	upperbound
	)		const

Return a list of PointListType iterators (effectively pointers to points, see PSMPointTreeNode) to points and their associated indicies that are stored in this tree and are contained within the specified bounding box region. The bounding box is specified with two points, in this order: a lower bound followed by an upper bound.

Definition at line 69 of file itkPSMPointTree.hxx.

    {
      PointIteratorListType pointlist;
      NodePointerType it = this->m_Root;

      // If no overlap with the root node exists, then return an empty list...
      if ( this->Overlap(it, lowerbound, upperbound) && ! it->IsLeaf() )
      {
        // otherwise, descend into the child nodes and compile the list.
        for (unsigned int i = 0; i < BranchesPerNode; i++)
        {
          this->FindOneNodeInRegion(it->GetBranch(i), lowerbound, upperbound, pointlist);
        }
      }

      return pointlist;
    }

template<unsigned int VDimension>

NodePointerType itk::PSMPointTree< VDimension >::GetNode

(

const PointType &

)

Return the node associated with the domain region that contains the given point.

template<unsigned int VDimension>

itk::PSMPointTree< VDimension >::itkGetMacro	(	Depth	,
		unsigned	int
	)

Set/Get the depth of the tree. This is the number of levels in the tree.

template<unsigned int VDimension>

itk::PSMPointTree< VDimension >::itkGetObjectMacro	(	Root	,
		NodeType
	)

Set/Get the root node of the tree.

template<unsigned int VDimension>

itk::PSMPointTree< VDimension >::itkNewMacro

(

Self

)

Method for creation through the object factory.

template<unsigned int VDimension>

itk::PSMPointTree< VDimension >::itkStaticConstMacro	(	Dimension	,
		unsigned	int,
		VDimension
	)

Dimensionality of the domain.

template<unsigned int VDimension>

itk::PSMPointTree< VDimension >::itkStaticConstMacro	(	BranchesPerNode	,
		int	,
		(powstruct< 2, VDimension >::c)
	)

Number of children per node.

template<unsigned int VDimension>

itk::PSMPointTree< VDimension >::itkTypeMacro	(	PSMPointTree< VDimension >	,
		DataObject
	)

Run-time type information (and related methods).

template<unsigned int VDimension>

bool itk::PSMPointTree< VDimension >::Overlap	(	const NodePointerType &	node,
		const PointType &	lowerbound,
		const PointType &	upperbound
	)		const

Returns true if the specified node region overlaps the given region and false otherwise.

Definition at line 49 of file itkPSMPointTree.hxx.

    {
      // Check for overlap in all dimensions.  If any one dimension has no overlap,
      // these two regions do not overlap.
      for (unsigned int i = 0; i < Dimension; i++)
      {
        // Does this region contain either node endpoint or does the node region
        // contain both of this region's endpoints?
        if (!  ((node->GetLowerBound()[i] >= lowerbound[i] && node->GetLowerBound()[i] <= upperbound[i])
              || (node->GetUpperBound()[i] >= lowerbound[i] && node->GetUpperBound()[i] <= upperbound[i])
              || (node->GetLowerBound()[i] <= lowerbound[i] && node->GetUpperBound()[i] >= upperbound[i] ) ))
          return false;
      }
      return true;
    }

---

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

• C:/Users/Brig/Documents/ShapeWorksStudio/src/ParticleShapeworks/include/itkPSMPointTree.h
• C:/Users/Brig/Documents/ShapeWorksStudio/src/ParticleShapeworks/include/itkPSMPointTree.hxx