btree.h File Reference

Introduction

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

See also

Tbtree,btree.c,Tatlas,atlas.c

Definition in file btree.h.

Data Structures
struct	TBTree
	Binary tree of charts. More...

Macros
#define	INIT_NUM_POINTS_IN_BTREE   1000
	Initial number of points in the tree. More...
#define	W_BTREE   0
	Weighted distances. More...

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...
boolean	PointInBTree (double eps, double *p, TBTree *t)
	Point in a 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

INIT_NUM_POINTS_IN_BTREE

#define INIT_NUM_POINTS_IN_BTREE   1000

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

Definition at line 30 of file btree.h.

W_BTREE

#define W_BTREE   0

If set, the distances in the tree use weights so that all dimensions have the same relevance. In general this should be 0. Do not confuse this with the nearest-neighbours used in planning.

Definition at line 38 of file btree.h.

Function Documentation

InitBTree()

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(), Error(), GetBoxInterval(), GetBoxNIntervals(), GetChartAmbientDim(), GetChartCenter(), GetChartRadius(), GetDistanceWeightsFromBox(), INIT_NUM_POINTS_IN_BTREE, LowerLimit(), TBTree::m, MaxVector(), NEW, TBTree::r, TBTree::tp, and UpperLimit().

Referenced by InitAtlasFromPoint(), and LoadAtlas().

AddChart2Btree()

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 110 of file btree.c.

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

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

PointInBTree()

boolean PointInBTree	(	double	eps,
		double *	p,
		TBTree *	t
	)

Determines if we already have a point in the tree.

Parameters

eps	Precision to use in the comparision between points. In debug mode, the cuik-kdtree library uses a hard-coded threshold of 1e-6. So this is a good value for this threshold.
p	The query point.
t	The tree.

Returns

The index of the nearest chart.

Definition at line 148 of file btree.c.

Referenced by HaveChartAtPoint().

SearchInBtree()

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 177 of file btree.c.

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

Referenced by DetermineChartNeighbours().

DeleteBTree()

void DeleteBTree

(

TBTree *

t

)

Deletes a tree of charts and releases the allocated memory.

Definition at line 219 of file btree.c.

References TBTree::tp.

Referenced by DeleteAtlas().