Image Component Library (ICL)
Classes | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
icl::math::QuadTree< Scalar, CAPACITY, SF, ALLOC_CHUNK_SIZE, VECTOR_TYPE > Class Template Reference

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 throw (utils::ICLException)
 returns an approximated nearst neighbour More...
 
Pt nn (const Pt &pIn) const throw (utils::ICLException)
 finds the nearest neighbor to the given node More...
 
const utils::Point32f nn (const utils::Point32f &p) const throw (utils::ICLException)
 convenience wrapper for the Point32f type More...
 
const utils::Point nn (const utils::Point &p) const throw (utils::ICLException)
 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< Ptquery (const Scalar &minX, const Scalar &minY, const Scalar &width, const Scalar &height) const
 returns all contained points within the given rectangle More...
 
std::vector< Ptquery (const utils::Rect &r) const
 convenience wrapper for Rect class More...
 
std::vector< Ptquery (const utils::Rect32f &r) const
 convenience wrapper for Rect32f class More...
 
std::vector< PtqueryAll () 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 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 More...
 

Protected Attributes

Noderoot
 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

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

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

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

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

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)

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

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

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

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

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.

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

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

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
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, 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
throw (utils::ICLException
)
inline

convenience wrapper for the Point32f type

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
throw (utils::ICLException
)
inline

convenience wrapper for the Point32f type

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
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, 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
throw (utils::ICLException
)
inlineprotected

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, 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)

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

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

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

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

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

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

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

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

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: