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 >:


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: