kdtree.c File Reference

KD-tree - Definition. More...

#include "kdtree.h"
#include "generic.h"
#include "random.h"
#include "mathop.h"
#include <stdlib.h>
#include "heap-def.h"

Functions
static vl_uindex	vl_kdtree_node_new (VlKDTree *tree, vl_uindex parentIndex)
	Allocate a new node from the tree pool.
int	vl_kdtree_compare_index_entries (void const *a, void const *b)
	Compare KDTree index entries for sorting.
static void	vl_kdtree_build_recursively (VlKDForest *forest, VlKDTree *tree, vl_uindex nodeIndex, vl_uindex dataBegin, vl_uindex dataEnd, unsigned int depth)
	Build KDTree recursively.
VlKDForest *	vl_kdforest_new (vl_type dataType, vl_size dimension, vl_size numTrees)
	Create new KDForest object.
void	vl_kdforest_delete (VlKDForest *self)
	Delete KDForest object.
void	vl_kdforest_build (VlKDForest *self, vl_size numData, void const *data)
	Build KDTree from data.
int	vl_kdforest_query_recursively (VlKDForest *self, VlKDTree *tree, vl_uindex nodeIndex, VlKDForestNeighbor *neighbors, vl_size numNeighbors, vl_size *numAddedNeighbors, double dist, void const *query)
static void	vl_kdtree_calc_bounds_recursively (VlKDTree *tree, vl_uindex nodeIndex, double *searchBounds)
	Compute tree bounds recursively.
vl_size	vl_kdforest_query (VlKDForest *self, VlKDForestNeighbor *neighbors, vl_size numNeighbors, void const *query)
	Query operation.

---

Detailed Description

Author:

Andrea Vedaldi

---

Function Documentation

void vl_kdforest_build	(	VlKDForest *	self,
		vl_size	numData,
		void const *	data
	)

Parameters:

self	KDTree object
numData	number of data points.
data	pointer to the data.

The function builds the KDTree by processing the data data. For efficiency, KDTree does not copy the data, but retains a pointer to it. Therefore the data must survive (and not change) until the KDTree is deleted.

void vl_kdforest_delete

(

VlKDForest *

self

)

Parameters:

self	KDForest object to delete

See also:

vl_kdforest_new

VlKDForest* vl_kdforest_new	(	vl_type	dataType,
		vl_size	dimension,
		vl_size	numTrees
	)

Parameters:

dataType	type of data (VL_TYPE_FLOAT or VL_TYPE_DOUBLE)
dimension	data dimensionality.
numTrees	number of trees in the forest.

Returns:

new KDForest.

vl_size vl_kdforest_query	(	VlKDForest *	self,
		VlKDForestNeighbor *	neighbors,
		vl_size	numNeighbors,
		void const *	query
	)

Parameters:

self	KDTree object instance.
neighbors	list of nearest neighbors found (output).
numNeighbors	number of nearest neighbors to find.
query	query point.

Returns:

number of tree leaves visited.

A neighbor is represented by an instance of the structure VlKDForestNeighbor. Each entry contains the index of the neighbor (this is an index into the KDTree data) and its distance to the query point. Neighbors are sorted by increasing distance.

int vl_kdforest_query_recursively	(	VlKDForest *	self,
		VlKDTree *	tree,
		vl_uindex	nodeIndex,
		VlKDForestNeighbor *	neighbors,
		vl_size	numNeighbors,
		vl_size *	numAddedNeighbors,
		double	dist,
		void const *	query
	)

static void vl_kdtree_build_recursively	(	VlKDForest *	forest,
		VlKDTree *	tree,
		vl_uindex	nodeIndex,
		vl_uindex	dataBegin,
		vl_uindex	dataEnd,
		unsigned int	depth
	)		[static]

Parameters:

forest	forest to which the tree belongs.
tree	tree being built.
nodeIndex	node to process.
dataBegin	begin of data for this node.
dataEnd	end of data for this node.
depth	depth of this node.

static void vl_kdtree_calc_bounds_recursively	(	VlKDTree *	tree,
		vl_uindex	nodeIndex,
		double *	searchBounds
	)		[static]

Parameters:

tree	KDTree object instance.
nodeIndex	node index to start from.
searchBounds	2 x numDimension array of bounds.

int vl_kdtree_compare_index_entries	(	void const *	a,
		void const *	b
	)		[inline]

static vl_uindex vl_kdtree_node_new	(	VlKDTree *	tree,
		vl_uindex	parentIndex
	)		[static]