kdtree.h File Reference

KD-tree (KD-trees and forests) More...

#include "generic.h"
#include "mathop.h"

Data Structures
struct	VlKDForestNeighbor
	Neighbor of a query point. More...
struct	VlKDForest
	KDForest object. More...
Enumerations
enum	VlKDTreeThresholdingMethod
	Thresholding method.
Functions
Creatind and disposing
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.
Building and querying
void	vl_kdforest_build (VlKDForest *self, vl_size numData, void const *data)
	Build KDTree from data.
vl_size	vl_kdforest_query (VlKDForest *self, VlKDForestNeighbor *neighbors, vl_size numNeighbors, void const *query)
	Query operation.
Retrieving and setting parameters
vl_size	vl_kdforest_get_depth_of_tree (VlKDForest const *self, vl_uindex treeIndex)
	Get the detph of a given tree.
vl_size	vl_kdforest_get_num_nodes_of_tree (VlKDForest const *self, vl_uindex treeIndex)
	Get the number of nodes of a given tree.
vl_size	vl_kdforest_get_num_trees (VlKDForest const *self)
	Get the number of trees in the forest.
vl_size	vl_kdforest_get_data_dimension (VlKDForest const *self)
	Get the dimension of the data.
vl_type	vl_kdforest_get_data_type (VlKDForest const *self)
	Get the data type.
void	vl_kdforest_set_max_num_comparisons (VlKDForest *self, vl_size n)
	Set the maximum number of comparisons for a search.
vl_size	vl_kdforest_get_max_num_comparisons (VlKDForest *self)
	Get the maximum number of comparisons for a search.
void	vl_kdforest_set_thresholding_method (VlKDForest *self, VlKDTreeThresholdingMethod method)
	Set the thresholding method.
VlKDTreeThresholdingMethod	vl_kdforest_get_thresholding_method (VlKDForest const *self)
	Get the thresholding method.

---

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

vl_size vl_kdforest_get_data_dimension

(

VlKDForest const *

self

)

[inline]

Parameters:

self	KDForest object.

Returns:

dimension of the data.

vl_type vl_kdforest_get_data_type

(

VlKDForest const *

self

)

[inline]

Parameters:

self	KDForest object.

Returns:

data type (one of VL_TYPE_FLOAT, VL_TYPE_DOUBLE).

vl_size vl_kdforest_get_depth_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)		[inline]

Parameters:

self	KDForest object.
treeIndex	index of the tree.

Returns:

number of trees.

vl_size vl_kdforest_get_max_num_comparisons

(

VlKDForest *

self

)

[inline]

Parameters:

self	KDForest object.

Returns:

maximum number of leaves.

See also:

vl_kdforest_set_max_num_comparisons.

vl_size vl_kdforest_get_num_nodes_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)		[inline]

Parameters:

self	KDForest object.
treeIndex	index of the tree.

Returns:

number of trees.

vl_size vl_kdforest_get_num_trees

(

VlKDForest const *

self

)

[inline]

Parameters:

self	KDForest object.

Returns:

number of trees.

VlKDTreeThresholdingMethod vl_kdforest_get_thresholding_method

(

VlKDForest const *

self

)

[inline]

Parameters:

self	KDForest object.

Returns:

thresholding method.

See also:

vl_kdforest_set_thresholding_method

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.

void vl_kdforest_set_max_num_comparisons	(	VlKDForest *	self,
		vl_size	n
	)		[inline]

Parameters:

self	KDForest object.
n	maximum number of leaves.

This function sets the maximum number of comparisons for a nearest neighbor search. Setting it to 0 means unbounded comparisons.

See also:

vl_kdforest_query, vl_kdforest_get_max_num_comparisons.

void vl_kdforest_set_thresholding_method	(	VlKDForest *	self,
		VlKDTreeThresholdingMethod	method
	)		[inline]

Parameters:

self	KDForest object.
method	one of VlKDTreeThresholdingMethod.

See also:

vl_kdforest_get_thresholding_method