spatium::idx::PointQuadtree Class Reference

Quadtree spatial index for 2D points. More...

#include <Quadtree.h>

Inheritance diagram for spatium::idx::PointQuadtree:

Collaboration diagram for spatium::idx::PointQuadtree:

Public Member Functions
	PointQuadtree (const BoundingBox< double, 2 > &bounds, size_t maxPointCountLeaf=100)
	Constructor. More...
bool	addPoint (const std::array< double, 2 > &point)
	Add a point to the quadtree. More...
BoundingBox< double, 2 >	bounds () const
size_t	maxPointCountLeaf () const
	Get the maximum point count in a leaf node. More...
Public Member Functions inherited from spatium::idx::Tree< std::vector< std::array< double, 2 > > >
	Tree (std::shared_ptr< TreeNode< std::vector< std::array< double, 2 > > >> rootNode=std::make_shared< TreeNode< std::vector< std::array< double, 2 > > >>())
	Constructor. More...
	Tree (const std::vector< std::array< double, 2 > > &rootObject, const std::shared_ptr< TreeNode< std::vector< std::array< double, 2 > > >> &rootNode=std::make_shared< TreeNode< std::vector< std::array< double, 2 > > >>())
	Constructor. More...
std::shared_ptr< TreeNode< std::vector< std::array< double, 2 > > > >	root () const
	Get the root node. More...
TreeIterator< std::vector< std::array< double, 2 > > >	begin ()
	Get iterator pointing to the beginning of the tree (root node). More...
TreeIterator< std::vector< std::array< double, 2 > > >	end ()
	Get iterator pointing to the end of the tree. More...

Static Public Member Functions
static PointQuadtree	buildFromPoints (const std::vector< std::array< double, 2 >> &points, size_t maxPointCountLeaf=100)
	Construct quadtree from points. More...
static size_t	determineChild (const BoundingBox< double, 2 > &boundsParent, const std::array< double, 2 > &point, BoundingBox< double, 2 > &boundsChild)
	Determine index of child (0 - 3) depening on bounding box of parent and positon of a point. Also outputs the bounding box of this child. More...

Protected Attributes
const BoundingBox< double, 2 >	m_boundingBox
const size_t	m_maxPointCountLeaf
Protected Attributes inherited from spatium::idx::Tree< std::vector< std::array< double, 2 > > >
const std::shared_ptr< TreeNode< std::vector< std::array< double, 2 > > > >	m_root

Detailed Description

Quadtree spatial index for 2D points.

Constructor & Destructor Documentation

PointQuadtree()

spatium::idx::PointQuadtree::PointQuadtree ( const BoundingBox< double, 2 > &  bounds, size_t  maxPointCountLeaf = 100  )

inline

Constructor.

Member Function Documentation

addPoint()

bool spatium::idx::PointQuadtree::addPoint ( const std::array< double, 2 > &  point )

inline

Add a point to the quadtree.

This will traverse the tree topdown from root into its children untill the right leaf node is found. The leaf node will be split into 4 when the maximum point count for a leaf node is exceeded.

Parameters

[in]

point

Point

Returns

True if added, false if point is outside bounding box of quadtree.

bounds()

BoundingBox<double,2> spatium::idx::PointQuadtree::bounds ( ) const

inline

buildFromPoints()

static PointQuadtree spatium::idx::PointQuadtree::buildFromPoints ( const std::vector< std::array< double, 2 >> &  points, size_t  maxPointCountLeaf = 100  )

inlinestatic

Construct quadtree from points.

Parameters

[in]	points	Collection of points
[in]	maxPointCountLeaf	Maximum number of points in a leaf node. Node will be split into 4 children when exceeded.

Returns

Quadtree (shared pointer)

determineChild()

static size_t spatium::idx::PointQuadtree::determineChild ( const BoundingBox< double, 2 > &  boundsParent, const std::array< double, 2 > &  point, BoundingBox< double, 2 > &  boundsChild  )

inlinestatic

Determine index of child (0 - 3) depening on bounding box of parent and positon of a point. Also outputs the bounding box of this child.

Parameters

[in]	boundsParent	Bounding box of parent
[in]	point	Point positon (must be within bounding box)
[out]	boundsChild	Bounding box of child

Returns

Child index (0 = topleft, 1 = topright, 2 = bottom right, 3 = bottom left)

maxPointCountLeaf()

size_t spatium::idx::PointQuadtree::maxPointCountLeaf ( ) const

inline

Get the maximum point count in a leaf node.

A node is split when it exceeds this number.

Member Data Documentation

m_boundingBox

const BoundingBox<double,2> spatium::idx::PointQuadtree::m_boundingBox

protected

m_maxPointCountLeaf

const size_t spatium::idx::PointQuadtree::m_maxPointCountLeaf

protected

---

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

• /home/martijn/Development/Projects/SpatiumLib/include/spatium/idx/Quadtree.h