btree.c File Reference

Detailed Description

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

Right now it offers an interface to the kdtree by Yershova and Lavalle.

See Also

btree.h,Tbtree,Tatlas,atlas.c

Definition in file btree.c.

Functions
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...

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.

Parameters

id	Identifier of the chart used to initialize the tree.
mp	The chart used to initialize the tree.
ambient	The ambient space.
topology	Topology for each variable/dimension. 1 for Real and 2 for circle. Set to NULL if all variables are real.
t	The 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.

Parameters

id	Identifier of the chart to add to the tree.
mp	The chart to add.
t	The 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.

Parameters

mp	The chart for which we want to get the neighbours.
nn	The number of neighbours returned. This is a return parameter.
n	The identifier of the neighbouring charts found. The space for this array is allocated internally but must be released by the caller.
t	The 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().