libgenua
Basic Geometry, Numerical Algorithms and Interfaces
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Groups Pages
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
NDPointTree< ND, FloatType > Class Template Reference

Detailed Description

template<int ND, class FloatType>
class NDPointTree< ND, FloatType >

Balanced binary tree for N-dimensional points.

NDPointTree is a generalization of BSearchTree which makes use of an implicitely represented balanced binary tree to eliminate a large number of small memory allocations. Furthermore, the comparatively costly tree construction operation is parallelized in ImplicitTree::sort().

Algorithmically, NDPointTree is a bounding-volume hierarchy (BVH) using simple axis-aligned bounding boxes as bounding volumes. Nodes are split along the median using the longest axis of a bounding box.

See Also
ImplicitTree, DopBase

#include <ndpointtree.h>

Collaboration diagram for NDPointTree< ND, FloatType >:
[legend]

Classes

class  Divider
 Division and comparison along coordinate axes. More...
 

Public Member Functions

 NDPointTree ()
 construct empty tree
 
uint allocate (uint np, const NDPoint *pts, bool share, uint mincount=4)
 allocate storage
 
uint allocate (const PointList< ND, FloatType > &pts, bool share, uint mincount=8)
 convenience interface
 
void clear ()
 clear storage
 
void sort ()
 sort entire tree
 
uint npoints () const
 number of indexed points
 
uint minPointCount () const
 access minimum number of points in node
 
const NDPointpoint (uint k) const
 access point
 
DopTypedop (uint k)
 access bounding volume for node k
 
const DopTypedop (uint k) const
 access bounding volume for node k
 
uint nearest (const NDPoint &p) const
 find point nearest to p using iterative procedure
 
bool find (const NDPoint &pt, FloatType r, Indices &fnd) const
 find point indices within radius of pt
 
uint repldup (FloatType threshold, Indices &repl, Indices &keep) const
 compute replacement map for de-duplication
 
float megabyte (bool shared) const
 determine memory footprint
 

Private Member Functions

void nearestRecursive (const NDPoint &p, uint inode, uint &inear, FloatType &mindst) const
 find point nearest to p in node inode, recursively
 
uint nearestIterative (const NDPoint &p) const
 find point nearest to p using iterative procedure
 
uint findIterative (const NDPoint &p) const
 find point nearest to p using iterative procedure
 

Private Attributes

NDPointArray points
 optionally shared point list
 
ImplicitTree itree
 binary tree
 
std::vector< DopTypebvol
 bounding volumes
 

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