Headers of the kd-tree implementation. More...

#include "definitions.h"
#include "rectangle.h"

Include dependency graph for cuik-kdtree.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	TKDtree
	A KD-tree. More...

Macros
#define	PLOTKDT 1
	Flag used for debug. More...

#define	KDTPTR(a) ((TKDtree *)(a))
	Void pointer to KDtree pointer. More...

Functions
TKDtree *	InitKDTree (Trectangle ambient, unsigned int topology, unsigned int m, double r, unsigned int n, double *points, unsigned int ids)
	Initializes a kd-tree from a set of points. More...

void	AddPoint2KDtree (double point, unsigned int id, TKDtree *kdt)
	Adds a point to a kd-tree. More...

unsigned int	NearestNeighbour (double point, TKDtree kdt)
	Determines the nearest-neighbour for a point. More...

void	NeighboursInBall (double point, double r, unsigned int n, unsigned int *ids, TKDtree kdt)
	Neighbours in a ball. More...

void	SampleInKDtree (double point, TKDtree kdt)
	Generates a random sample. More...

double	KDtreeSamplingExpansion (TKDtree *kdt)
	Returns the sampling expansion used in the kd-tree. More...

void	PrintKDtree (FILE f, unsigned int indent, TKDtree kdt)
	Prints a kd-tree. More...

void	PlotKDtree (char fname, boolean sphere, TKDtree kdt)
	Plots a kd-tree. More...

void	DeleteKDtree (TKDtree *kdt)
	Deletes a KD-tree. More...

Detailed Description

Headers of the kd-tree implementation.

See Also: TKDtree cuik-kdtree.c

Definition in file cuik-kdtree.h.

Macro Definition Documentation

#define PLOTKDT 1

When set, it generates a file of the kd-tree that can be visualized with geomview.

This only works for kd-trees defined in 3d and it is more useful when the points are defined on a manifold (see POINTS_ON_SPHERE).

Definition at line 30 of file cuik-kdtree.h.

#define KDTPTR ( a ) ((TKDtree *)(a))

Casts a void pointer into a KDtree pointer.

Definition at line 38 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), PrintKDtree(), SampleInKDtree(), SearchInBallKDtree(), and SearchKDtree().

Function Documentation

TKDtree* InitKDTree	(	Trectangle *	ambient,
		unsigned int *	topology,
		unsigned int	m,
		double	r,
		unsigned int	n,
		double **	points,
		unsigned int *	ids
	)

Kd-tree constructor.

Parameters

ambient	The ambient box for the points.
topology	The topology (Real,Circle) of each dimension. Might be NULL if the topology is real for all dimensions.
m	The maximum number of points in the leaves.
r	The expansion factor to use in the sampling.
n	The number of points.
points	The points.
ids	The identifiers of the points.

Returns: The kd-tree.

Definition at line 544 of file cuik-kdtree.c.

References ANGLE_ACCURACY, BuildKDTree(), GetRectangleDim(), GetRectangleLimits(), M_PI, SetRectangleLimits(), and TOPOLOGY_S.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

void AddPoint2KDtree	(	double *	point,
		unsigned int	id,
		TKDtree **	kdt
	)

Adds a point to a kd-tree.

Parameters

point	The point to add to the kd-tree.
id	The identifier associated with the point.
kdt	The kd-tree to update.

Definition at line 582 of file cuik-kdtree.c.

References AddPoint2KDtree(), TKDtree::ambient, TKDtree::boundingBox, BuildKDTree(), CopyRectangle(), DeleteKDtree(), EnlargeRectangleWithLimits(), ExpandRectangle(), TKDtree::height, TKDtree::id, INF, InitRectangleFromPoint(), TKDtree::isLeaf, KDTPTR, TKDtree::left, TKDtree::leftLeaf, TKDtree::m, TKDtree::n, TKDtree::nd, NEW, TKDtree::nextLeaf, TKDtree::p, TKDtree::r, TKDtree::right, TKDtree::rightLeaf, TKDtree::samplingBox, TKDtree::splitDim, TKDtree::splitValue, TKDtree::topology, VectorSquaredDistanceTopologyMin(), and TKDtree::volume.

Referenced by AddPoint2KDtree(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int NearestNeighbour	(	double *	point,
		TKDtree *	kdt
	)

Uses the kd-tree to find the nearest-neighbour of a given point.

Parameters

point	The query point.
kdt	The KD-tree to query.

Returns: The identifier associated with the nearest-neighbour.

Definition at line 714 of file cuik-kdtree.c.

References INF, TKDtree::n, NO_UINT, and SearchKDtree().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

void NeighboursInBall	(	double *	point,
		double	r,
		unsigned int *	n,
		unsigned int **	ids,
		TKDtree *	kdt
	)

Determines all the points in a given ball.

Parameters

point	The center of the query ball.
r	The radius of the query ball.
n	The nuber of output points.
ids	The identifiers for the output points.
kdt	The KD-tree to query.

Definition at line 730 of file cuik-kdtree.c.

References TKDtree::n, NEW, and SearchInBallKDtree().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

void SampleInKDtree	(	double *	point,
		TKDtree *	kdt
	)

Geneates a random sample in the volume covered by the kd-tree expanded by a given factor ('r' given in the kd-tree construction) with uniform distribution.

Parameters

point	The sampled point.
kdt	The kd-tree

See Also: InitKDTree

Definition at line 747 of file cuik-kdtree.c.

References TKDtree::isLeaf, KDTPTR, TKDtree::left, randomDouble(), RandomPointInRectangle(), TKDtree::right, SampleInKDtree(), TKDtree::samplingBox, and TKDtree::volume.

Referenced by SampleInKDtree().

Here is the call graph for this function:

Here is the caller graph for this function:

double KDtreeSamplingExpansion ( TKDtree * kdt )

Returns the sampling expansion used in the kd-tree.

Parameters

kdt	The kd-tree to query.

Returns: The sampling expansion of the kd-tree.

Definition at line 764 of file cuik-kdtree.c.

References TKDtree::r.

void PrintKDtree	(	FILE *	f,
		unsigned int	indent,
		TKDtree *	kdt
	)

Prints a kd-tree. Used for debug.

Parameters

f	The file where to print the kd-tree. Typically stdout or stderr.
indent	Indent level for the first level of the tree. The rest of levels are progressively indented.
kdt	The kd-tree to print.

Definition at line 769 of file cuik-kdtree.c.

References TKDtree::boundingBox, TKDtree::id, TKDtree::isLeaf, KDTPTR, KDTREE_PRINT_INDENT, TKDtree::left, TKDtree::n, TKDtree::nd, TKDtree::p, PrintKDtree(), PrintRectangle(), TKDtree::right, TKDtree::splitDim, and TKDtree::splitValue.