Library of Assembled Shared Sources
lass::spat::QuadTree< ObjectType, ObjectTraits, SplitHeuristics > Class Template Reference

A spatial container for generic objects. More...

#include <quad_tree_helper.h>

Inheritance diagram for lass::spat::QuadTree< ObjectType, ObjectTraits, SplitHeuristics >:
Collaboration diagram for lass::spat::QuadTree< ObjectType, ObjectTraits, SplitHeuristics >:

Public Member Functions

 QuadTree (const TAabb &aabb, const TSplitHeuristics &heuristics=TSplitHeuristics(defaultMaxObjectsPerLeaf, defaultMaxDepth))
 empty quadtree with fixed bounding box
 
 QuadTree (const TAabb &aabb, TObjectIterator end, const TSplitHeuristics &heuristics=TSplitHeuristics(defaultMaxObjectsPerLeaf, defaultMaxDepth))
 empty quadtree with fixed bounding box and end iterator.
 
 QuadTree (TObjectIterator first, TObjectIterator last, const TSplitHeuristics &heuristics=TSplitHeuristics(defaultMaxObjectsPerLeaf, defaultMaxDepth))
 quadtree from objects, with computed bounding box
 
 QuadTree (TSelf &&other) noexcept
 move constructor
 
TSelfoperator= (TSelf &&other) noexcept
 move constructor
 
bool contains (const TPoint &p, const TInfo *info=0) const
 return true if any of the objects contains point.
 
template<typename OutputIterator>
OutputIterator find (const TPoint &p, OutputIterator result, const TInfo *info=0) const
 find objects containing point and write them to the output iterator.
 
template<typename OutputIterator>
OutputIterator find (const TAabb &box, OutputIterator result, const TInfo *info=0) const
 
template<typename OutputIterator>
OutputIterator find (const TRay &ray, TParam minT, TParam maxT, OutputIterator result, const TInfo *info=0) const
 
void add (TObjectIterator object)
 contains.
 
size_t depth () const
 depth.
 

Detailed Description

template<typename ObjectType, typename ObjectTraits = DefaultObjectTraits<ObjectType>, typename SplitHeuristics = DefaultSplitHeuristics>
class lass::spat::QuadTree< ObjectType, ObjectTraits, SplitHeuristics >

A spatial container for generic objects.

The object needs a traits class which contains the necessary functions to perform the quad tree management for the particular ObjectType. The traits class needs as a basis the following interface: static TAabb aabb(const TSimplePolygon3D& iP); static bool contains( const TSimplePolygon3D& iP, const TPoint& point) The above functions are only examples. The dimensionality of the primitives must match but can be of any order. So the quad tree can be used to classify in 2 and 3 dimensions. In three dimensions the more common name is OctTree.

Higher level divisions can in theory be supported but the dimensional specific part must be reimplemented. Altough this is only 2 functions and could be written generally this is not yet available.

a Quad tree for general objects

Author
Tom De Muer [TDM]

Definition at line 85 of file quad_tree.h.

Member Function Documentation

◆ contains()

template<typename O, typename OT, typename SH>
bool lass::spat::QuadTree< O, OT, SH >::contains ( const TPoint & p,
const TInfo * info = 0 ) const

return true if any of the objects contains point.

Required : static bool ObjectTypeTraits::contains( const Object& object, const TPoint& point, const TInfo* info );

Definition at line 244 of file quad_tree.inl.

◆ find() [1/3]

template<typename O, typename OT, typename SH>
template<typename OutputIterator>
OutputIterator lass::spat::QuadTree< O, OT, SH >::find ( const TPoint & p,
OutputIterator result,
const TInfo * info = 0 ) const

find objects containing point and write them to the output iterator.

Required : static bool ObjectTypeTraits::contains( const Object& object, const TPoint& point, const TInfo* info );

Definition at line 277 of file quad_tree.inl.

◆ find() [2/3]

template<typename O, typename OT, typename SH>
template<typename OutputIterator>
OutputIterator lass::spat::QuadTree< O, OT, SH >::find ( const TAabb & box,
OutputIterator result,
const TInfo * info = 0 ) const
Warning
As this algorithm visits multiple leaf nodes, it may find duplicate objects. This algorithm doesn't care. But if you do, you can use insert_iterators to a set.

Definition at line 313 of file quad_tree.inl.

◆ find() [3/3]

template<typename O, typename OT, typename SH>
template<typename OutputIterator>
OutputIterator lass::spat::QuadTree< O, OT, SH >::find ( const TRay & ray,
TParam tMin,
TParam tMax,
OutputIterator result,
const TInfo * info = 0 ) const
Warning
As this algorithm visits multiple leaf nodes, it may find duplicate objects. This algorithm doesn't care. But if you do, you can use insert_iterators to a set.

Definition at line 330 of file quad_tree.inl.

◆ add()

template<typename O, typename OT, typename SH>
void lass::spat::QuadTree< O, OT, SH >::add ( TObjectIterator object)

contains.

Returns the number of object that returned sFront on all the lines provided in the iFrustum vector and adds them to the vector oObjects. An example of use is frustum culling.

Required : static bool ObjectTypeTraits::contains( const Object& object, const TPoint& point );

Definition at line 218 of file quad_tree.inl.

◆ depth()

template<typename O, typename OT, typename SH>
size_t lass::spat::QuadTree< O, OT, SH >::depth ( ) const

depth.

Returns the depth of the tree

Definition at line 440 of file quad_tree.inl.


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