 libgenua Basic Geometry, Numerical Algorithms and Interfaces
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.

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: