cuik-kdtree.h File Reference

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

#include "definitions.h"
#include <stdlib.h>
#include <math.h>
#include "definitions.h"
#include <stdio.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...
Defines
#define	KDTPTR(a) ((TKDtree *)(a))
	Void pointer to KDtree pointer.
Functions
TKDtree *	InitKDTree (Trectangle ambient, unsigned int m, double r, unsigned int n, double points, unsigned int ids)
	Initializes a kd-tree from a set of points.
void	AddPoint2KDtree (unsigned int topology, double point, unsigned int id, TKDtree **kdt)
	Adds a point to a kd-tree.
unsigned int	NearestNeighbour (unsigned int topology, double point, TKDtree *kdt)
	Determines the nearest-neighbour for a point.
void	NeighboursInBall (unsigned int topology, double point, double r, unsigned int n, unsigned int ids, TKDtree kdt)
	Neighbours in a ball.
void	SampleInKDtree (double point, TKDtree kdt)
	Generates a random sample.
void	DeleteKDtree (TKDtree *kdt)
	Deletes a KD-tree.

Detailed Description

Headers of the kd-tree implementation.

See also:: TKDtree cuik-kdtree.c

Definition in file cuik-kdtree.h.

Define Documentation

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

Casts a void pointer into a KDtree pointer.

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

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

Function Documentation

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

Kd-tree constructor.

Parameters:

	ambient	The ambient box for the points.
	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 418 of file cuik-kdtree.c.

References BuildKDTree().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Adds a point to a kd-tree.

Parameters:

	topology	Topology (Real,Circle) of each dimension. Might be NULL if the topology is real for all dimensions.
	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 427 of file cuik-kdtree.c.

References AddPoint2KDtree(), TKDtree::ambient, TKDtree::boundingBox, BuildKDTree(), DeleteKDtree(), EnlargeRectangleWithLimits(), ExpandRectangle(), TKDtree::height, TKDtree::id, 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::samplingArea, TKDtree::splitDim, TKDtree::splitValue, 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	(	unsigned int *	topology,
		double *	point,
		TKDtree *	kdt
	)

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

Parameters:

	topology	Topology (Real,Circle) of each dimension.
	point	The query point.
	kdt	The KD-tree to query.

Returns:: The identifier associated with the nearest-neighbour.

Definition at line 539 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	(	unsigned int *	topology,
		double *	point,
		double	r,
		unsigned int *	n,
		unsigned int **	ids,
		TKDtree *	kdt
	)

Determines all the points in a given ball.

Parameters:

	topology	Topology (Real,Circle) of each dimension.
	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 555 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: