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"

Go to the source code of this file.

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

Definition in file kdtree.c.

---

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.

Definition at line 372 of file kdtree.c.

References vl_kdtree_build_recursively(), vl_kdtree_node_new(), and vl_malloc().

void vl_kdforest_delete

(

VlKDForest *

self

)

Parameters:

self

KDForest object to delete

See also:

vl_kdforest_new

Definition at line 343 of file kdtree.c.

References vl_free().

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.

Definition at line 293 of file kdtree.c.

References vl_get_rand(), vl_get_vector_comparison_function_d(), vl_get_vector_comparison_function_f(), vl_malloc(), VL_TYPE_DOUBLE, VL_TYPE_FLOAT, and VlDistanceL2.

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.

Definition at line 589 of file kdtree.c.

References _VlKDForestNeighbor::distance, _VlKDForestNeighbor::index, vl_calloc(), vl_free(), VL_INFINITY_F, vl_kdforest_query_recursively(), vl_kdtree_calc_bounds_recursively(), vl_malloc(), and VL_NAN_F.

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
	)

For internal use only.

Definition at line 403 of file kdtree.c.

References _VlKDForestNeighbor::distance, _VlKDForestNeighbor::index, VL_TYPE_DOUBLE, and VL_TYPE_FLOAT.

Referenced by vl_kdforest_query().

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

For internal use only.

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.

Definition at line 157 of file kdtree.c.

References vl_kdtree_compare_index_entries(), vl_kdtree_node_new(), VL_MIN, vl_rand_uint32(), VL_TYPE_DOUBLE, and VL_TYPE_FLOAT.

Referenced by vl_kdforest_build().

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

For internal use only.

Parameters:

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

Definition at line 552 of file kdtree.c.

Referenced by vl_kdforest_query().

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

For internal use only.

Definition at line 133 of file kdtree.c.

Referenced by vl_kdtree_build_recursively().

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

For internal use only.

Definition at line 110 of file kdtree.c.

Referenced by vl_kdforest_build(), and vl_kdtree_build_recursively().