btree.h File Reference

Detailed Description

Definition a binary tree to speed up the search for neighouring charts in the atlas.

See Also

Definition in file btree.h.

Data Structures

struct  TBTree
 Binary tree of charts. More...


 Initial number of points in the tree. More...


void InitBTree (unsigned int id, Tchart *mp, Tbox *ambient, unsigned int *topology, TBTree *t)
 Initializes a binary tree of charts. More...
void AddChart2Btree (unsigned int id, Tchart *mp, TBTree *t)
 Adds a chart to the tree. More...
void SearchInBtree (Tchart *mp, unsigned int *nn, unsigned int **n, TBTree *t)
 Search for neighbouring charts. More...
void DeleteBTree (TBTree *t)
 Chart tree destructor. More...

Macro Definition Documentation


Initial number of points in the tree. Enlarged as needed.

Definition at line 29 of file btree.h.

Referenced by InitBTree().

Function Documentation

void InitBTree ( unsigned int  id,
Tchart mp,
Tbox ambient,
unsigned int *  topology,
TBTree t 

Creates a binary tree of charts from the central point of one chart.

idIdentifier of the chart used to initialize the tree.
mpThe chart used to initialize the tree.
ambientThe ambient space.
topologyTopology for each variable/dimension. 1 for Real and 2 for circle. Set to NULL if all variables are real.
tThe tree to create.

Definition at line 19 of file btree.c.

References AddChart2Btree(), GetBoxInterval(), GetBoxNIntervals(), GetChartAmbientDim(), GetChartCenter(), GetChartRadius(), INIT_NUM_POINTS_IN_BTREE, LowerLimit(), TBTree::m, NEW, TBTree::r, TBTree::tp, and UpperLimit().

Referenced by InitAtlasFromPoint(), and LoadAtlas().

void AddChart2Btree ( unsigned int  id,
Tchart mp,
TBTree t 

Adds a new chart to the tree of charts.

idIdentifier of the chart to add to the tree.
mpThe chart to add.
tThe tree where to add the chart.

Definition at line 75 of file btree.c.

References ArrayPi2Pi(), Error(), GetChartCenter(), TBTree::m, MEM_DUP, NEW, and TBTree::tp.

Referenced by DetermineChartNeighbours(), InitBTree(), and LoadAtlas().

void SearchInBtree ( Tchart mp,
unsigned int *  nn,
unsigned int **  n,
TBTree t 

Uses the tree of charts to efficiently detect neighbouring charts to a given chart.

We assume that the charts all have the same domain radius as the original chart (the one used to initialize the tree).

Note that the output of this search is not the set of neighbours but the set of potential neighbours (identifiers of points in tree leaves close to the test point). This is not an issue since the intersection test that typically follows the search for neighbours takes care of actually detecting the true neighbours.

mpThe chart for which we want to get the neighbours.
nnThe number of neighbours returned. This is a return parameter.
nThe identifier of the neighbouring charts found. The space for this array is allocated internally but must be released by the caller.
tThe tree to use for the query.

Definition at line 113 of file btree.c.

References ArrayPi2Pi(), GetChartCenter(), TBTree::m, NEW, TBTree::r, and TBTree::tp.

Referenced by DetermineChartNeighbours().

void DeleteBTree ( TBTree t)

Deletes a tree of charts and releases the allocated memory.

Definition at line 155 of file btree.c.

References TBTree::tp.

Referenced by DeleteAtlas().