Generic QuadTree Implementation. More...

#include <QuadTree.h>

Classes
struct	AABB
	internally used axis-aligned bounding box More...

struct	Allocator
	Inernally used block allocator. More...

struct	Node
	Internally used node structure. More...

Public Types
typedef VECTOR_TYPE	Pt

Public Member Functions
	QuadTree (const Scalar &minX, const Scalar &minY, const Scalar &width, const Scalar &height)
	creates a QuadTree for the given 2D rectangle More...

	QuadTree (const utils::Rect32f &bounds)
	convenience constructor wrapper for given Rect32f bounds More...

	QuadTree (const utils::Rect &bounds)
	convenience constructor wrapper for given Rect32f bounds More...

	QuadTree (const Scalar &width, const Scalar &height)
	creates a QuadTree for the given 2D Size (minX and minY are set to 0 here) More...

	QuadTree (const utils::Size32f &size)
	convenience wrapper for given Size32f bounds More...

	QuadTree (const utils::Size &size)
	convenience wrapper for given Size bounds More...

	~QuadTree ()
	destructor More...

Pt	nn_approx (const Pt &p) const
	returns an approximated nearst neighbour More...

Pt	nn (const Pt &pIn) const
	finds the nearest neighbor to the given node More...

const utils::Point32f	nn (const utils::Point32f &p) const
	convenience wrapper for the Point32f type More...

const utils::Point	nn (const utils::Point &p) const
	convenience wrapper for the Point32f type More...

void	insert (const Pt &pIn)
	inserts a node into the QuadTree More...

void	insert (const utils::Point32f &p)
	convenience wrapper for the Point32f instances More...

void	insert (const utils::Point &p)
	convenience wrapper for the Point instances More...

std::vector< Pt >	query (const Scalar &minX, const Scalar &minY, const Scalar &width, const Scalar &height) const
	returns all contained points within the given rectangle More...

std::vector< Pt >	query (const utils::Rect &r) const
	convenience wrapper for Rect class More...

std::vector< Pt >	query (const utils::Rect32f &r) const
	convenience wrapper for Rect32f class More...

std::vector< Pt >	queryAll () const
	returns all contained points More...

utils::VisualizationDescription	vis () const
	returns a visualization description for QuadTree structure (not for the contained points) More...

void	clear ()
	removes all contained points and nodes More...

int	size () const
	number of elments inserted More...

void	printStructure ()
	prints the quad-tree structure hierachically (for debug purpose) More...

Protected Member Functions
const Pt &	nn_approx_internal (const Pt &p, double &currMinDist, const Pt *&currNN) const
	internal utility method that is used to find an approximated nearest neighbour More...

Protected Attributes
Node *	root
	root node pointer More...

Allocator	alloc
	memory allocator for all children except for the root node More...

int	num
	internal counter for the number of contained points More...

Detailed Description

template<class Scalar, int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>
class icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >

Generic QuadTree Implementation.

The implementation follows the pseudo code from Wikipedia. However, we added some performance related implementation enhancements.

Template Parameters

Scalar the internal data type, which must be either float or double CAPACITY the node capacity. This defines the number of Points, that are stored in each node. Due to an internal optimization, best performace in terms insertion and nearest-neighbor search is given for CAPACITIES in the range of 32 to 128 entries. SF the internal data scale factor. This can be used to reach a higher exact integer resolution when splitting regions. The scale factor should usually be a power of two. In our benchmarks, it turned out, that using a non-1 scalefactor does not affect the speed of the quadtree's methods. We recommend to use a scalefactor of 32, which ensures at least 5 quad-tree levels can be split perfectly, while still allowing a data range of [-67M,67M] (2^(31-5)). ALLOC_CHUNK_SIZE This parameters does actually not alter the performance very much. It defines the size of memory blocks allocated by the internal block allocator

Performance

As far as we can say, the implementation is quite fast. For now, we will only provide a few examples; a full evaluation will be given soon.

System: 2.4GHz Core2Duo, Ubuntu 12.04 32Bit, 4 GB Ram, Optimized build (-O4 -march=native)

Experiment base line:

QuadTree<float,32,1,1024> with VGA bounds, containing 100K points uniformly distributed. for integers an upscaling factor of 32 is used: QuadTree<int,32,32,1024> with VGA bounds, containing 100K points uniformly distributed. Using no scale factor (SF = 1) does not lead to faster processing!

Tasks are:

insertion nearest neighbor search of 1000 random points approximate nearest neighbor search of 1000 random points query a huge region: Rect(100,100,500,350), containing 57% of all points

Experiment 1 (Base line results)

(numbers in round braces refer to the integer quadtree performance)

In particular the nearest neighbour search, that is dominated by comparing nodes and distances runs about 3 time faster for integers.

insertion: 5.8ms (5.4ms) nn-search: 3.6ms (1.2ms) approx. nn: 0.19ms (0.15ms) query: 1.7ms (1.7ms)

Experiment 2 (Using smaller Nodes of CAPACITY 4)

Smaller nodes implicate more structure and a deeper node hierarchy. This makes all parts significantly slower. In particular the nn-search is affecter. Here, the list of points in each node can be compared without using the square-root function, which is very time consuming.

The nearest neighbor search performance for integer processing is still about two times faster

insertion: 9.6ms (9.6ms) nn-search: 1.7ms (0.9ms) approx. nn: 0.16ms (0.12ms) query: 2.3ms (2.3ms)

Experiment 2b (Using larger Nodes of CAPACITY 128)

Here, again, we can see that larger nodes speed up the insertion part, while the nn-search optimization is already saturated here.

insertion: 4.5ms (4.6ms) nn-search: 6.5ms (2.5ms) approx nn: 0.31ms (0.31ms) query: 1.73ms (1.72ms)

Experiment 3 (Using 10K Points only)

With less points, the whole system gets significantly faster. In particular insertion and query is more then 10-times as fast which can be explained by better caching properties. The nearest neighbour search has a logarithmic complexity and is sped up least.

insertion: 0.4ms (0.34ms) nn-search: 2.4ms (1.07ms) approx. nn: 0.16ms (0.287ms) query: 0.16ms (0.17ms)

Experiment 4 (Using 1000K Points)

Obviously, we face caching issues here: While 10K and even 100K points could easily be cached, the whole structure cannot be cached with 1000K points. Therefore, insertion gets significantly slower. The logarithmic complexity of the nn-search stays valid and make this part not become that much slower. The approximate nn-search is not affected so strongly because it majorly depends on the node capacity.

insertion: 130ms (123ms) nn-search: 8ms (1.5ms) approx. nn: 0.33ms (0.18ms) query: 26ms (27ms)

Experiment 5 (Using 1000K Points, but with Node CAPACITY 128)

Here, the insertion time gets smaller, because less nodes have to be created. On the other hand, the nn-search takes slightly longer

insertion: 87ms (85ms) nn-search: 9.8ms (3ms) approx. nn: 0.3ms (0.23ms) query: 23ms (24ms)

Experiment 6 (Using 1000K Points, but with Node CAPACITY 1024)

Same effect as before, but much stronger. The approximate nn-search becomes alot slower, because all CAPACITY points in the best matching cell must be checked. However, the approximate results are usually more accurate here

insertion: 55ms (54ms) nn-search: 41ms (17ms) approx. nn: 2.7ms (2.7ms) query: 22.8ms (22.8ms)

Member Typedef Documentation

◆ Pt

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

typedef VECTOR_TYPE icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::Pt

Constructor & Destructor Documentation

◆ QuadTree() [1/6]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::QuadTree	(	const Scalar &	minX,
		const Scalar &	minY,
		const Scalar &	width,
		const Scalar &	height
	)

inline

creates a QuadTree for the given 2D rectangle

◆ QuadTree() [2/6]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::QuadTree ( const utils::Rect32f & bounds )

inline

convenience constructor wrapper for given Rect32f bounds

◆ QuadTree() [3/6]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::QuadTree ( const utils::Rect & bounds )

inline

convenience constructor wrapper for given Rect32f bounds

◆ QuadTree() [4/6]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::QuadTree	(	const Scalar &	width,
		const Scalar &	height
	)

inline

creates a QuadTree for the given 2D Size (minX and minY are set to 0 here)

◆ QuadTree() [5/6]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::QuadTree ( const utils::Size32f & size )

inline

convenience wrapper for given Size32f bounds

◆ QuadTree() [6/6]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::QuadTree ( const utils::Size & size )

inline

convenience wrapper for given Size bounds

◆ ~QuadTree()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::~QuadTree ( )

inline

destructor

Deletes the root node only, all other nodes are deleted by the allocator

Member Function Documentation

◆ clear()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::clear ( )

inline

removes all contained points and nodes

The allocator will free all memory except for the first CHUNK

◆ insert() [1/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::insert ( const Pt & pIn )

inline

inserts a node into the QuadTree

This method is also implemented in an iterative fashion for performance issues. 'insert' automatically uses the internal allocator if new nodes are needed.

◆ insert() [2/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::insert ( const utils::Point32f & p )

inline

convenience wrapper for the Point32f instances

◆ insert() [3/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::insert ( const utils::Point & p )

inline

convenience wrapper for the Point instances

◆ nn() [1/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

Pt icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::nn ( const Pt & pIn ) const

inline

finds the nearest neighbor to the given node

The implementation of this method explicitly avoids recursion by using a run-time stack. This leads to a 4x speed factor in comparison to the recursive implementaiton of this function.

As an extra accelleration, the method initializes it's frist nearest neighbor guess using the nn_approx method, which gives an approximate speed up of factor two to four.

As a 2nd accelleration heuristic, all CAPACITY nodes' distances are are first calculated and compared in a squared version, which can be computed without an expensive square-root operation. However, once the closest point within a single node is found, its real euclidian minimum distance is computed and stored for further bounding box checks.

If no neighbour could be found, an exception is thown. This should actually only happen when nn is called on an empty QuadTree

◆ nn() [2/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

const utils::Point32f icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::nn ( const utils::Point32f & p ) const

inline

convenience wrapper for the Point32f type

◆ nn() [3/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

const utils::Point icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::nn ( const utils::Point & p ) const

inline

convenience wrapper for the Point32f type

◆ nn_approx()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

Pt icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::nn_approx ( const Pt & p ) const

inline

returns an approximated nearst neighbour

While the real nearst neighbour must not neccessarily be in the cell that would theoretically contain p, The approximated one is always assumed to be in that bottom layer cell. If, by chance, the optimal leaf node does not contain any points (because it was just created as empty leaf), the leaf's parent node, which must actually contain CAPACITY points, is used instead. The approximate nearest neighbour search can easily be 5 times as fast as the real nearest neighbor search. The result quality depends on the number of contained points, and on the QuadTree's template parameters

◆ nn_approx_internal()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

const Pt& icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::nn_approx_internal	(	const Pt &	p,
		double &	currMinDist,
		const Pt *&	currNN
	)		const

inlineprotected

internal utility method that is used to find an approximated nearest neighbour

◆ printStructure()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::printStructure ( )

inline

prints the quad-tree structure hierachically (for debug purpose)

◆ query() [1/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::query	(	const Scalar &	minX,
		const Scalar &	minY,
		const Scalar &	width,
		const Scalar &	height
	)		const

inline

returns all contained points within the given rectangle

◆ query() [2/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::query ( const utils::Rect & r ) const

inline

convenience wrapper for Rect class

◆ query() [3/3]

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::query ( const utils::Rect32f & r ) const

inline

convenience wrapper for Rect32f class

◆ queryAll()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::queryAll ( ) const

inline

returns all contained points

◆ size()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

int icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::size ( ) const

inline

number of elments inserted

◆ vis()

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

utils::VisualizationDescription icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::vis ( ) const

inline

returns a visualization description for QuadTree structure (not for the contained points)

Member Data Documentation

◆ alloc

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

Allocator icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::alloc

protected

memory allocator for all children except for the root node

◆ num

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

int icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::num

protected

internal counter for the number of contained points

◆ root

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>

Node* icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >::root

protected

root node pointer

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

/Users/alneuman/vm/icl/ICLMath/src/ICLMath/QuadTree.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class Scalar, int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>> class icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >

Template Parameters

Performance

Experiment 1 (Base line results)

Experiment 2 (Using smaller Nodes of CAPACITY 4)

Experiment 2b (Using larger Nodes of CAPACITY 128)

Experiment 3 (Using 10K Points only)

Experiment 4 (Using 1000K Points)

Experiment 5 (Using 1000K Points, but with Node CAPACITY 128)

Experiment 6 (Using 1000K Points, but with Node CAPACITY 1024)

Member Typedef Documentation

◆ Pt

Constructor & Destructor Documentation

◆ QuadTree() [1/6]

◆ QuadTree() [2/6]

◆ QuadTree() [3/6]

◆ QuadTree() [4/6]

◆ QuadTree() [5/6]

◆ QuadTree() [6/6]

◆ ~QuadTree()

Member Function Documentation

◆ clear()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ nn() [1/3]

◆ nn() [2/3]

◆ nn() [3/3]

◆ nn_approx()

◆ nn_approx_internal()

◆ printStructure()

◆ query() [1/3]

◆ query() [2/3]

◆ query() [3/3]

◆ queryAll()

◆ size()

◆ vis()

Member Data Documentation

◆ alloc

◆ num

◆ root

template<class Scalar, int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024, class VECTOR_TYPE = FixedColVector<Scalar,2>>
class icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE >