Image Component Library (ICL)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE > Class Template Reference

Generic QuadTree Implementation. More...

#include <QuadTree.h>

List of all members.

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 FixedColVector< Scalar, 2 > 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
 QuadTree (const utils::Rect32f &bounds)
 convenience constructor wrapper for given Rect32f bounds
 QuadTree (const utils::Rect &bounds)
 convenience constructor wrapper for given Rect32f bounds
 QuadTree (const Scalar &width, const Scalar &height)
 creates a QuadTree for the given 2D Size (minX and minY are set to 0 here)
 QuadTree (const utils::Size32f &size)
 convenience wrapper for given Size32f bounds
 QuadTree (const utils::Size &size)
 convenience wrapper for given Size bounds
 ~QuadTree ()
 destructor
Pt nn_approx (const Pt &p) const throw (utils::ICLException)
 returns an approximated nearst neighbour
Pt nn (const Pt &pIn) const throw (utils::ICLException)
 finds the nearest neighbor to the given node
const utils::Point32f nn (const utils::Point32f &p) const throw (utils::ICLException)
 convenience wrapper for the Point32f type
const utils::Point nn (const utils::Point &p) const throw (utils::ICLException)
 convenience wrapper for the Point32f type
void insert (const Pt &pIn)
 inserts a node into the QuadTree
void insert (const utils::Point32f &p)
 convenience wrapper for the Point32f instances
void insert (const utils::Point &p)
 convenience wrapper for the Point instances
std::vector< Ptquery (const Scalar &minX, const Scalar &minY, const Scalar &width, const Scalar &height) const
 returns all contained points within the given rectangle
std::vector< Ptquery (const utils::Rect &r) const
 convenience wrapper for Rect class
std::vector< Ptquery (const utils::Rect32f &r) const
 convenience wrapper for Rect32f class
std::vector< PtqueryAll () const
 returns all contained points
utils::VisualizationDescription vis () const
 returns a visualization description for QuadTree structure (not for the contained points)
void clear ()
 removes all contained points and nodes
int size () const
 number of elments inserted
void printStructure ()
 prints the quad-tree structure hierachically (for debug purpose)

Protected Member Functions

const Ptnn_approx_internal (const Pt &p, double &currMinDist, const Pt *&currNN) const throw (utils::ICLException)
 internal utility method that is used to find an approximated nearest neighbour

Protected Attributes

Noderoot
 root node pointer
Allocator alloc
 memory allocator for all children except for the root node
int num
 internal counter for the number of contained points

Detailed Description

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

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

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

Constructor & Destructor Documentation

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::QuadTree ( const Scalar &  minX,
const Scalar &  minY,
const Scalar &  width,
const Scalar &  height 
) [inline]

creates a QuadTree for the given 2D rectangle

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::QuadTree ( const utils::Rect32f bounds) [inline]

convenience constructor wrapper for given Rect32f bounds

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::QuadTree ( const utils::Rect bounds) [inline]

convenience constructor wrapper for given Rect32f bounds

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::QuadTree ( const Scalar &  width,
const Scalar &  height 
) [inline]

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

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::QuadTree ( const utils::Size32f size) [inline]

convenience wrapper for given Size32f bounds

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::QuadTree ( const utils::Size size) [inline]

convenience wrapper for given Size bounds

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::~QuadTree ( ) [inline]

destructor

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


Member Function Documentation

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::clear ( ) [inline]

removes all contained points and nodes

The allocator will free all memory except for the first CHUNK

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::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.

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::insert ( const utils::Point32f p) [inline]

convenience wrapper for the Point32f instances

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::insert ( const utils::Point p) [inline]

convenience wrapper for the Point instances

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
Pt icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::nn ( const Pt pIn) const throw (utils::ICLException) [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

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
const utils::Point32f icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::nn ( const utils::Point32f p) const throw (utils::ICLException) [inline]

convenience wrapper for the Point32f type

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
const utils::Point icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::nn ( const utils::Point p) const throw (utils::ICLException) [inline]

convenience wrapper for the Point32f type

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
Pt icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::nn_approx ( const Pt p) const throw (utils::ICLException) [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

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
const Pt& icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::nn_approx_internal ( const Pt p,
double &  currMinDist,
const Pt *&  currNN 
) const throw (utils::ICLException) [inline, protected]

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

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
void icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::printStructure ( ) [inline]

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

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::query ( const Scalar &  minX,
const Scalar &  minY,
const Scalar &  width,
const Scalar &  height 
) const [inline]

returns all contained points within the given rectangle

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::query ( const utils::Rect r) const [inline]

convenience wrapper for Rect class

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::query ( const utils::Rect32f r) const [inline]

convenience wrapper for Rect32f class

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
std::vector<Pt> icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::queryAll ( ) const [inline]

returns all contained points

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
int icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::size ( ) const [inline]

number of elments inserted

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
utils::VisualizationDescription icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::vis ( ) const [inline]

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


Member Data Documentation

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
Allocator icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::alloc [protected]

memory allocator for all children except for the root node

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
int icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::num [protected]

internal counter for the number of contained points

template<class Scalar , int CAPACITY = 4, int SF = 1, int ALLOC_CHUNK_SIZE = 1024>
Node* icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE >::root [protected]

root node pointer


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines