library of assembled shared sources

 http://lass.cocamware.com

lass::spat::QuadTree< ObjectType, ObjectTraits > Class Template Reference

A spatial container for generic objects. More...

#include <quad_tree.h>

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

Inheritance graph
[legend]
Collaboration diagram for lass::spat::QuadTree< ObjectType, ObjectTraits >:

Collaboration graph
[legend]

Data Structures

class  Neighbour
struct  QuadNode

Public Types

enum  { dimension = TObjectTraits::dimension }
typedef QuadTree< ObjectType,
ObjectTraits > 		TSelf
typedef ObjectType TObjectType
typedef ObjectTraits TObjectTraits
typedef
TObjectTraits::TObjectIterator 		TObjectIterator
typedef
TObjectTraits::TObjectReference 		TObjectReference
typedef TObjectTraits::TAabb TAabb
typedef TObjectTraits::TRay TRay
typedef TObjectTraits::TPoint TPoint
typedef TObjectTraits::TVector TVector
typedef TObjectTraits::TValue TValue
typedef TObjectTraits::TParam TParam
typedef TObjectTraits::TReference TReference
typedef
TObjectTraits::TConstReference 		TConstReference
typedef TObjectTraits::TInfo TInfo

Public Member Functions

 QuadTree (size_t maxSize=100, size_t maxLevel=10)
 constructor that computes bounding box automatically from objects
 QuadTree (TObjectIterator first, TObjectIterator last, size_t maxSize=10, size_t maxLevel=10)
 constructor that computes bounding box automatically from objects
 ~QuadTree ()
 constructor.
void reset ()
void reset (TObjectIterator first, TObjectIterator last)
const 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.
const TObjectIterator intersect (const TRay &ray, TReference t, TParam tMin=0, const TInfo *info=0) const
const bool intersects (const TRay &ray, TParam tMin=0, TParam maxT=std::numeric_limits< TValue >::infinity(), const TInfo *info=0) const
const Neighbour nearestNeighbour (const TPoint &point, const TInfo *info=0) const
template<typename RandomIterator >
RandomIterator rangeSearch (const TPoint &center, TParam maxRadius, size_t maxCount, RandomIterator first, const TInfo *info=0) const
void add (TObjectIterator object)
 contains.
size_t objectCount () const
const TAabb & aabb () const
const size_t depth () const
 depth.
const TValue averageDepth () const
void swap (QuadTree &other)
const TObjectIterator end () const
template<typename RandomAccessIterator >
RandomAccessIterator rangeSearch (const TPoint &target, TParam maxRadius, size_t maxCount, RandomAccessIterator first, const TInfo *info) const

Private Types

enum  { subNodeCount = 1 << dimension }
typedef std::vector
< TObjectIterator > 		TObjectIterators

Private Member Functions

const TObjectIterator doIntersect (const QuadNode *node, const TRay &ray, TReference t, TParam tMin, const TInfo *info, const TVector &tNear, const TVector &tFar, size_t flipMask) const
 Reference: J.
const bool doIntersects (const QuadNode *node, const TRay &ray, TParam tMin, TParam tMax, const TInfo *info, const TVector &tNear, const TVector &tFar, size_t flipMask) const
void doNearestNeighbour (const QuadNode *node, const TPoint &point, const TInfo *info, Neighbour &best) const
template<typename RandomIterator >
RandomIterator doRangeSearch (const QuadNode *node, const TPoint &target, TReference squaredRadius, size_t maxCount, RandomIterator first, RandomIterator last, const TInfo *info) const
const TValue minComponent (const TVector &v) const
const TValue maxComponent (const TVector &v) const
const V middle (const V &a, const V &b) const
const TVector subtract (const TPoint &a, const TPoint &b) const
const size_t entryNode (const TVector &tNear, const TVector &tMiddle) const
const size_t nextNode (size_t i, const TVector &tFar) const
const size_t findSubNode (const TPoint &center, const TPoint &point) const
const size_t forcePositiveDirection (const TPoint &center, TPoint &support, TVector &direction) const
void nearAndFar (const TPoint &min, const TPoint &max, const TPoint &support, const TVector &reciprocalDirection, TVector &tNear, TVector &tFar) const
void childNearAndFar (TVector &tNear, TVector &tFar, const TVector &tMiddle, size_t iChild) const

Static Private Member Functions

static void buildSubNodes (QuadNodeType *parentNode)

Private Attributes

TAabb aabb_
QuadNode * root_
TObjectIterator end_
size_t maxSize_
size_t maxLevel_

Detailed Description

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

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 81 of file quad_tree.h.

Member Typedef Documentation

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef QuadTree<ObjectType, ObjectTraits> lass::spat::QuadTree< ObjectType, ObjectTraits >::TSelf

Definition at line 85 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef ObjectType lass::spat::QuadTree< ObjectType, ObjectTraits >::TObjectType

Definition at line 86 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef ObjectTraits lass::spat::QuadTree< ObjectType, ObjectTraits >::TObjectTraits

Reimplemented from lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >.

Definition at line 87 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TObjectIterator lass::spat::QuadTree< ObjectType, ObjectTraits >::TObjectIterator

Definition at line 89 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TObjectReference lass::spat::QuadTree< ObjectType, ObjectTraits >::TObjectReference

Definition at line 90 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TAabb lass::spat::QuadTree< ObjectType, ObjectTraits >::TAabb

Definition at line 91 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TRay lass::spat::QuadTree< ObjectType, ObjectTraits >::TRay

Definition at line 92 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TPoint lass::spat::QuadTree< ObjectType, ObjectTraits >::TPoint

Reimplemented from lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >.

Definition at line 93 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TVector lass::spat::QuadTree< ObjectType, ObjectTraits >::TVector

Reimplemented from lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >.

Definition at line 94 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TValue lass::spat::QuadTree< ObjectType, ObjectTraits >::TValue

Reimplemented from lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >.

Definition at line 95 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TParam lass::spat::QuadTree< ObjectType, ObjectTraits >::TParam

Definition at line 96 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TReference lass::spat::QuadTree< ObjectType, ObjectTraits >::TReference

Definition at line 97 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TConstReference lass::spat::QuadTree< ObjectType, ObjectTraits >::TConstReference

Definition at line 98 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef TObjectTraits::TInfo lass::spat::QuadTree< ObjectType, ObjectTraits >::TInfo

Definition at line 99 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
typedef std::vector<TObjectIterator> lass::spat::QuadTree< ObjectType, ObjectTraits >::TObjectIterators [private]

Definition at line 197 of file quad_tree.h.

Member Enumeration Documentation

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
anonymous enum

Enumerator:
dimension 

Definition at line 101 of file quad_tree.h.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
anonymous enum [private]

Enumerator:
subNodeCount 

Definition at line 196 of file quad_tree.h.

Constructor & Destructor Documentation

template<typename O , typename OT >
lass::spat::QuadTree< O, OT >::QuadTree ( size_t  maxSize = 100,
size_t  maxLevel = 10 
) [inline]

constructor that computes bounding box automatically from objects

Definition at line 79 of file quad_tree.inl.

template<typename O , typename OT >
lass::spat::QuadTree< O, OT >::QuadTree ( TObjectIterator  first,
TObjectIterator  last,
size_t  maxSize = 10,
size_t  maxLevel = 10 
) [inline]

constructor that computes bounding box automatically from objects

Definition at line 123 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_, lass::spat::QuadTree< ObjectType, ObjectTraits >::dimension, and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
lass::spat::QuadTree< O, OT >::~QuadTree (  )  [inline]

constructor.

Parameters:
center the center of the spatial tree
extents the extents of the spatial tree in each direction, thus the total width of the tree is twice the extents constructor.
box the bounding box of the spatial tree

Definition at line 89 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

Member Function Documentation

template<typename O , typename OT >
void lass::spat::QuadTree< O, OT >::reset (  )  [inline]

Definition at line 155 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::swap().

template<typename O , typename OT >
void lass::spat::QuadTree< O, OT >::reset ( TObjectIterator  first,
TObjectIterator  last 
) [inline]

Definition at line 164 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::swap().

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

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 185 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::center, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::data, lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::findSubNode(), LASS_ASSERT, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_INIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_OBJECT, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::leaf, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::node, and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

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

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 216 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::center, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::data, lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::findSubNode(), LASS_ASSERT, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_INIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_OBJECT, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::leaf, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::node, and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
const QuadTree< O, OT >::TObjectIterator lass::spat::QuadTree< O, OT >::intersect ( const TRay &  ray,
TReference  t,
TParam  tMin = 0,
const TInfo *  info = 0 
) const [inline]

Definition at line 247 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_, lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersect(), lass::spat::QuadTree< ObjectType, ObjectTraits >::end_, lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::forcePositiveDirection(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::maxComponent(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::middle(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::minComponent(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::nearAndFar(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
const bool lass::spat::QuadTree< O, OT >::intersects ( const TRay &  ray,
TParam  tMin = 0,
TParam  maxT = std::numeric_limits<TValue>::infinity(),
const TInfo *  info = 0 
) const [inline]

Definition at line 278 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_, lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::forcePositiveDirection(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::maxComponent(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::middle(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::minComponent(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::nearAndFar(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
const QuadTree< O, OT >::Neighbour lass::spat::QuadTree< O, OT >::nearestNeighbour ( const TPoint &  point,
const TInfo *  info = 0 
) const [inline]

Definition at line 311 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::doNearestNeighbour(), lass::spat::QuadTree< ObjectType, ObjectTraits >::end_, and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
template<typename RandomIterator >
RandomIterator lass::spat::QuadTree< ObjectType, ObjectTraits >::rangeSearch ( const TPoint &  center,
TParam  maxRadius,
size_t  maxCount,
RandomIterator  first,
const TInfo *  info = 0 
) const [inline]

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

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 173 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::add(), LASS_THROW, lass::spat::QuadTree< ObjectType, ObjectTraits >::maxLevel_, lass::spat::QuadTree< ObjectType, ObjectTraits >::maxSize_, and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
size_t lass::spat::QuadTree< O, OT >::objectCount (  )  const [inline]

Definition at line 341 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::objectCount(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
const QuadTree< O, OT >::TAabb & lass::spat::QuadTree< O, OT >::aabb (  )  const [inline]

Definition at line 350 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_.

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

depth.

Returns the depth of the tree

Definition at line 358 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::depth(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
const QuadTree< O, OT >::TValue lass::spat::QuadTree< O, OT >::averageDepth (  )  const [inline]

Definition at line 368 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::averageDepth(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

template<typename O , typename OT >
void lass::spat::QuadTree< O, OT >::swap ( QuadTree< ObjectType, ObjectTraits > &  other  )  [inline]

Definition at line 376 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_, lass::spat::QuadTree< ObjectType, ObjectTraits >::end_, lass::spat::QuadTree< ObjectType, ObjectTraits >::maxLevel_, lass::spat::QuadTree< ObjectType, ObjectTraits >::maxSize_, and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::reset().

template<typename O , typename OT >
const QuadTree< O, OT >::TObjectIterator lass::spat::QuadTree< O, OT >::end (  )  const [inline]

Definition at line 389 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::end_.

template<typename O , typename OT >
const QuadTree< O, OT >::TObjectIterator lass::spat::QuadTree< O, OT >::doIntersect ( const QuadNode *  node,
const TRay &  ray,
TReference  t,
TParam  tMin,
const TInfo *  info,
const TVector &  tNear,
const TVector &  tFar,
size_t  flipMask 
) const [inline, private]

Reference: J.

Revelles, C. Urena, and M. Lastra. An efficient parametric algorithm for octree traversal. In Eighth International Conference in Central Europe on Computer Graphics, Visualization and Interactive Digital Media (WSCG 2000), pages 212–-219, Plzen, Czech Republic, 2000.

Definition at line 406 of file quad_tree.inl.

References lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::childNearAndFar(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::data, lass::spat::QuadTree< ObjectType, ObjectTraits >::end_, lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::entryNode(), LASS_ASSERT, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_INIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_OBJECT, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::leaf, lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::middle(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::minComponent(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::nextNode(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::node, and lass::spat::QuadTree< ObjectType, ObjectTraits >::subNodeCount.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect().

template<typename O , typename OT >
const bool lass::spat::QuadTree< O, OT >::doIntersects ( const QuadNode *  node,
const TRay &  ray,
TParam  tMin,
TParam  tMax,
const TInfo *  info,
const TVector &  tNear,
const TVector &  tFar,
size_t  flipMask 
) const [inline, private]

Definition at line 491 of file quad_tree.inl.

References lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::childNearAndFar(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::data, lass::spat::QuadTree< ObjectType, ObjectTraits >::end_, lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::entryNode(), LASS_ASSERT, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_INIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_OBJECT, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::leaf, lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::maxComponent(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::middle(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::minComponent(), lass::spat::impl::QuadTreeHelper< ObjectTraits, ObjectTraits::dimension >::nextNode(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::node, and lass::spat::QuadTree< ObjectType, ObjectTraits >::subNodeCount.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects().

template<typename O , typename OT >
void lass::spat::QuadTree< O, OT >::doNearestNeighbour ( const QuadNode *  node,
const TPoint &  point,
const TInfo *  info,
Neighbour &  best 
) const [inline, private]

Definition at line 543 of file quad_tree.inl.

References lass::num::abs(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::center, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::data, lass::spat::QuadTree< ObjectType, ObjectTraits >::dimension, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::extents, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_INIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_OBJECT, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::leaf, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::node, lass::spat::QuadTree< ObjectType, ObjectTraits >::Neighbour::squaredDistance(), lass::prim::squaredDistance(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::subNodeCount.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::nearestNeighbour().

template<typename O , typename OT >
template<typename RandomIterator >
RandomIterator lass::spat::QuadTree< O, OT >::doRangeSearch ( const QuadNode *  node,
const TPoint &  target,
TReference  squaredRadius,
size_t  maxCount,
RandomIterator  first,
RandomIterator  last,
const TInfo *  info 
) const [inline, private]

Definition at line 605 of file quad_tree.inl.

References lass::num::abs(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::center, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::data, lass::spat::QuadTree< ObjectType, ObjectTraits >::dimension, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::extents, LASS_ASSERT, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_INIT_NODE, LASS_SPAT_OBJECT_TREES_DIAGNOSTICS_VISIT_OBJECT, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::leaf, lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::node, and lass::spat::QuadTree< ObjectType, ObjectTraits >::subNodeCount.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::rangeSearch().

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
template<typename RandomAccessIterator >
RandomAccessIterator lass::spat::QuadTree< ObjectType, ObjectTraits >::rangeSearch ( const TPoint &  target,
TParam  maxRadius,
size_t  maxCount,
RandomAccessIterator  first,
const TInfo *  info 
) const [inline]

Definition at line 326 of file quad_tree.inl.

References lass::spat::QuadTree< ObjectType, ObjectTraits >::doRangeSearch(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::root_.

const TValue lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::minComponent ( const TVector &  v  )  const [inline, protected, inherited]

Definition at line 86 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersect(), lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects().

const TValue lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::maxComponent ( const TVector &  v  )  const [inline, protected, inherited]

Definition at line 96 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects().

const V lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::middle ( const V &  a,
const V &  b 
) const [inline, protected, inherited]

Definition at line 107 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersect(), lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects().

const TVector lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::subtract ( const TPoint &  a,
const TPoint &  b 
) const [inline, protected, inherited]

Definition at line 117 of file quad_tree_helper.h.

const size_t lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::entryNode ( const TVector &  tNear,
const TVector &  tMiddle 
) const [inline, protected, inherited]

Definition at line 127 of file quad_tree_helper.h.

References lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::maxComponent().

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects().

const size_t lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::nextNode ( size_t  i,
const TVector &  tFar 
) const [inline, protected, inherited]

Definition at line 138 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects().

const size_t lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::findSubNode ( const TPoint &  center,
const TPoint &  point 
) const [inline, protected, inherited]

Definition at line 158 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::contains(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::find().

const size_t lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::forcePositiveDirection ( const TPoint &  center,
TPoint &  support,
TVector &  direction 
) const [inline, protected, inherited]

Definition at line 168 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects().

void lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::nearAndFar ( const TPoint &  min,
const TPoint &  max,
const TPoint &  support,
const TVector &  reciprocalDirection,
TVector &  tNear,
TVector &  tFar 
) const [inline, protected, inherited]

Definition at line 185 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects().

void lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::childNearAndFar ( TVector &  tNear,
TVector &  tFar,
const TVector &  tMiddle,
size_t  iChild 
) const [inline, protected, inherited]

Definition at line 197 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersect(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects().

static void lass::spat::impl::QuadTreeHelper< ObjectTraits, dimension >::buildSubNodes ( QuadNodeType *  parentNode  )  [inline, static, protected, inherited]

Definition at line 213 of file quad_tree_helper.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadNode::decompose().

Field Documentation

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
TAabb lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb_ [private]

Definition at line 230 of file quad_tree.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::aabb(), lass::spat::QuadTree< ObjectType, ObjectTraits >::add(), lass::spat::QuadTree< ObjectType, ObjectTraits >::contains(), lass::spat::QuadTree< ObjectType, ObjectTraits >::find(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadTree(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::swap().

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
QuadNode* lass::spat::QuadTree< ObjectType, ObjectTraits >::root_ [private]

Definition at line 231 of file quad_tree.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::add(), lass::spat::QuadTree< ObjectType, ObjectTraits >::averageDepth(), lass::spat::QuadTree< ObjectType, ObjectTraits >::contains(), lass::spat::QuadTree< ObjectType, ObjectTraits >::depth(), lass::spat::QuadTree< ObjectType, ObjectTraits >::find(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersects(), lass::spat::QuadTree< ObjectType, ObjectTraits >::nearestNeighbour(), lass::spat::QuadTree< ObjectType, ObjectTraits >::objectCount(), lass::spat::QuadTree< ObjectType, ObjectTraits >::QuadTree(), lass::spat::QuadTree< ObjectType, ObjectTraits >::rangeSearch(), lass::spat::QuadTree< ObjectType, ObjectTraits >::swap(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::~QuadTree().

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
TObjectIterator lass::spat::QuadTree< ObjectType, ObjectTraits >::end_ [private]

Definition at line 232 of file quad_tree.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersect(), lass::spat::QuadTree< ObjectType, ObjectTraits >::doIntersects(), lass::spat::QuadTree< ObjectType, ObjectTraits >::end(), lass::spat::QuadTree< ObjectType, ObjectTraits >::intersect(), lass::spat::QuadTree< ObjectType, ObjectTraits >::nearestNeighbour(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::swap().

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
size_t lass::spat::QuadTree< ObjectType, ObjectTraits >::maxSize_ [private]

Definition at line 233 of file quad_tree.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::add(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::swap().

template<class ObjectType , class ObjectTraits = DefaultObjectTraits<ObjectType>>
size_t lass::spat::QuadTree< ObjectType, ObjectTraits >::maxLevel_ [private]

Definition at line 234 of file quad_tree.h.

Referenced by lass::spat::QuadTree< ObjectType, ObjectTraits >::add(), and lass::spat::QuadTree< ObjectType, ObjectTraits >::swap().

The documentation for this class was generated from the following files:
Generated on Mon Nov 10 14:22:15 2008 for Library of Assembled Shared Sources by doxygen 1.5.7.1
 SourceForge.net Logo