Quadtree search. More...

#include <QuadTree.hh>

Public Member Functions
	QuadTree (const double x0, const double y0, const double hx, const double hy)
	Constructor.

	~QuadTree ()
	Destructor.

void	InsertMeshNode (const double x, const double y, const int index)
	Insert a mesh node (a vertex/point) to the tree.

void	InsertMeshElement (const double bb[4], const int index)
	Insert a mesh element with given bounding box and index to the tree.

const std::vector< int > &	GetElementsInBlock (const double x, const double y) const
	Get all elements linked to a block corresponding to the given point.

Detailed Description

Quadtree search.

Definition at line 12 of file QuadTree.hh.

Constructor & Destructor Documentation

◆ QuadTree()

Garfield::QuadTree::QuadTree	(	const double	x0,
		const double	y0,
		const double	hx,
		const double	hy )

Constructor.

Definition at line 8 of file QuadTree.cc.

    : m_x0(x0), m_y0(y0), m_hx(hx), m_hy(hy) {
  m_xmin = x0 - hx;
  m_ymin = y0 - hy;
  m_xmax = x0 + hx;
  m_ymax = y0 + hy;
 
  // Initially, there are no children.
  for (size_t i = 0; i < 4; ++i) children[i] = nullptr;
}

Referenced by InsertMeshNode().

◆ ~QuadTree()

Garfield::QuadTree::~QuadTree ( )

Destructor.

Definition at line 20 of file QuadTree.cc.

                    {
  for (size_t i = 0; i < 4; ++i) delete children[i];
}

Member Function Documentation

◆ GetElementsInBlock()

const std::vector< int > & Garfield::QuadTree::GetElementsInBlock	(	const double	x,
		const double	y ) const

Get all elements linked to a block corresponding to the given point.

Definition at line 94 of file QuadTree.cc.

                                                                           {
  const auto node = GetBlockFromPoint(x, y);
  return node ? node->elements : emptyBlock;
}

◆ InsertMeshElement()

void Garfield::QuadTree::InsertMeshElement	(	const double	bb[4],
		const int	index )

Insert a mesh element with given bounding box and index to the tree.

Definition at line 81 of file QuadTree.cc.

                                                                    {
  if (IsLeafNode()) {
    // Add the element to the list of this quadrant.
    elements.push_back(index);
    return;
  } 
  // Check which children overlap with the element's bounding box.
  for (int i = 0; i < 4; ++i) {
    if (!children[i]->DoesBoxOverlap(bb)) continue;
    children[i]->InsertMeshElement(bb, index);
  }
}

◆ InsertMeshNode()

void Garfield::QuadTree::InsertMeshNode	(	const double	x,
		const double	y,
		const int	index )

Insert a mesh node (a vertex/point) to the tree.

Definition at line 43 of file QuadTree.cc.

                                                                             {
  // Check if it is a leaf node.
  if (!IsLeafNode()) {
    // We are at an interior node. 
    // Insert recursively into appropriate child quadrant.
    int quad = GetQuadrant(x, y);
    children[quad]->InsertMeshNode(x, y, index);
    return;
  }
  
  // Add the new point if the block is not full.
  if (nodes.size() < BlockCapacity) {
    nodes.push_back(std::make_tuple(x, y, index));
    return;
  } 
  // Block is full, so we need to partition it.
  // Split the current node and create new empty trees for each child.
  for (int i = 0; i < 4; ++i) {
    // Compute new bounding box for this child.
    const double xi = m_x0 + m_hx * (i & 2 ? 0.5 : -0.5);
    const double yi = m_y0 + m_hy * (i & 1 ? 0.5 : -0.5);
    children[i] = new QuadTree(xi, yi, 0.5 * m_hx, 0.5 * m_hy);
  }
 
  // Move the mesh nodes from the partitioned node (now marked as interior) to
  // its children.
  while (!nodes.empty()) {
    auto node = nodes.back();
    nodes.pop_back();
    const double xn = std::get<0>(node);
    const double yn = std::get<1>(node);
    const int quad = GetQuadrant(xn, yn);
    children[quad]->InsertMeshNode(xn, yn, std::get<2>(node));
  }
  // Insert the new point in the appropriate octant.
  children[GetQuadrant(x, y)]->InsertMeshNode(x, y, index);
}

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

Public Member Functions