Documentation>C API
Data Structures | Enumerations
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...
struct | VlKDForestSearcher
| VlKDForest searcher object More...

## Enumerations

enum | VlKDTreeThresholdingMethod
| Thresholding method.

## Functions

Creating, copying and disposing
VlKDForest * | vl_kdforest_new (vl_type dataType, vl_size dimension, vl_size numTrees, VlVectorComparisonType normType)
| Create new KDForest object. More...
VlKDForestSearcher * | vl_kdforest_new_searcher (VlKDForest *kdforest)
| Create a KDForest searcher object, used for processing queries. More...
void | vl_kdforest_delete (VlKDForest *self)
| Delete KDForest object. More...
void | vl_kdforestsearcher_delete (VlKDForestSearcher *searcher)
| Delete object. More...
Building and querying
void | vl_kdforest_build (VlKDForest *self, vl_size numData, void const *data)
| Build KDTree from data. More...
vl_size | vl_kdforest_query (VlKDForest *self, VlKDForestNeighbor *neighbors, vl_size numNeighbors, void const *query)
| Query the forest. More...
vl_size | vl_kdforest_query_with_array (VlKDForest *self, vl_uint32 *index, vl_size numNeighbors, vl_size numQueries, void *distance, void const *queries)
| Run multiple queries. More...
vl_size | vl_kdforestsearcher_query (VlKDForestSearcher *self, VlKDForestNeighbor *neighbors, vl_size numNeighbors, void const *query)
| Query the forest. More...
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. More...
vl_size | vl_kdforest_get_num_nodes_of_tree (VlKDForest const *self, vl_uindex treeIndex)
| Get the number of nodes of a given tree. More...
vl_size | vl_kdforest_get_num_trees (VlKDForest const *self)
| Get the number of trees in the forest. More...
vl_size | vl_kdforest_get_data_dimension (VlKDForest const *self)
| Get the dimension of the data. More...
vl_type | vl_kdforest_get_data_type (VlKDForest const *self)
| Get the data type. More...
void | vl_kdforest_set_max_num_comparisons (VlKDForest *self, vl_size n)
| Set the maximum number of comparisons for a search. More...
vl_size | vl_kdforest_get_max_num_comparisons (VlKDForest *self)
| Get the maximum number of comparisons for a search. More...
void | vl_kdforest_set_thresholding_method (VlKDForest *self, VlKDTreeThresholdingMethod method)
| Set the thresholding method. More...
VlKDTreeThresholdingMethod | vl_kdforest_get_thresholding_method (VlKDForest const *self)
| Get the thresholding method. More...
VlKDForest * | vl_kdforest_searcher_get_forest (VlKDForestSearcher const *self)
VlKDForestSearcher * | vl_kdforest_get_searcher (VlKDForest const *self, vl_uindex pos)

## Detailed Description

Author
  Andrea Vedaldi, David Novotny

## Function Documentation

## ◆ vl_kdforest_build()

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 make a copy the data, but retains a pointer to it. Therefore the data buffer must be valid and unchanged for the lifespan of the object.

The number of data points `numData` must not be smaller than one.

## ◆ vl_kdforest_delete()

void vl_kdforest_delete | ( | VlKDForest * | self | ) |

Parameters

  self | KDForest object to delete

See also
  vl_kdforest_new

## ◆ vl_kdforest_get_data_dimension()

vl_size vl_kdforest_get_data_dimension | ( | VlKDForest const * | self | ) |

Parameters

  self | KDForest object.

Returns
  dimension of the data.

## ◆ vl_kdforest_get_data_type()

vl_type vl_kdforest_get_data_type | ( | VlKDForest const * | self | ) |

Parameters

  self | KDForest object.

Returns
  data type (one of VL_TYPE_FLOAT, VL_TYPE_DOUBLE).

## ◆ vl_kdforest_get_depth_of_tree()

vl_size vl_kdforest_get_depth_of_tree | ( | VlKDForest const * | self,
|  | vl_uindex | treeIndex
| ) |  |

Parameters

  self | KDForest object.
  treeIndex | index of the tree.

Returns
  number of trees.

## ◆ vl_kdforest_get_max_num_comparisons()

vl_size vl_kdforest_get_max_num_comparisons | ( | VlKDForest * | self | ) |

Parameters

  self | KDForest object.

Returns
  maximum number of leaves.

See also
  vl_kdforest_set_max_num_comparisons.

## ◆ vl_kdforest_get_num_nodes_of_tree()

vl_size vl_kdforest_get_num_nodes_of_tree | ( | VlKDForest const * | self,
|  | vl_uindex | treeIndex
| ) |  |

Parameters

  self | KDForest object.
  treeIndex | index of the tree.

Returns
  number of trees.

## ◆ vl_kdforest_get_num_trees()

vl_size vl_kdforest_get_num_trees | ( | VlKDForest const * | self | ) |

Parameters

  self | KDForest object.

Returns
  number of trees.

## ◆ vl_kdforest_get_thresholding_method()

VlKDTreeThresholdingMethod vl_kdforest_get_thresholding_method | ( | VlKDForest const * | self | ) |

Parameters

  self | KDForest object.

Returns
  thresholding method.

See also
  vl_kdforest_set_thresholding_method

## ◆ vl_kdforest_new()

VlKDForest* vl_kdforest_new | ( | vl_type | dataType,
|  | vl_size | dimension,
|  | vl_size | numTrees,
|  | VlVectorComparisonType | distance
| ) |  |

Parameters

  dataType | type of data (VL_TYPE_FLOAT or VL_TYPE_DOUBLE)
  dimension | data dimensionality.
  numTrees | number of trees in the forest.
  distance | type of distance norm (VlDistanceL1 or VlDistanceL2).

Returns
  new KDForest.

The data dimension dimension and the number of trees numTrees must not be smaller than one.

## ◆ vl_kdforest_new_searcher()

VlKDForestSearcher* vl_kdforest_new_searcher | ( | VlKDForest * | kdforest | ) |

Parameters

  kdforest | a forest to which the queries should be pointing.

Returns
  KDForest searcher object.

A searcher is an object attached to the forest which must be created before running the queries. Each query has to be invoked with the searcher as its argument.

When using a multi-threaded approach a user should at first instantiate a correct number of searchers - each used in one thread. Then in each thread a query to the given searcher could be run.

## ◆ vl_kdforest_query()

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

Parameters

  self | object.
  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.

## ◆ vl_kdforest_query_with_array()

vl_size vl_kdforest_query_with_array | ( | VlKDForest * | self,
|  | vl_uint32 * | indexes,
|  | vl_size | numNeighbors,
|  | vl_size | numQueries,
|  | void * | distances,
|  | void const * | queries
| ) |  |

Parameters

  self | object.
  indexes | assignments of points.
  numNeighbors | number of nearest neighbors to be found for each data point
  numQueries | number of query points.
  distances | distances of query points.
  queries | lisf of vectors to use as queries.

indexes and distances are numNeighbors by numQueries matrices containing the indexes and distances of the nearest neighbours for each of the numQueries queries queries.

This function is similar to vl_kdforest_query. The main difference is that the function can use multiple cores to query large amounts of data.

See also
  vl_kdforest_query.

## ◆ vl_kdforest_set_max_num_comparisons()

void vl_kdforest_set_max_num_comparisons | ( | VlKDForest * | self,
|  | vl_size | n
| ) |  |

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.

## ◆ vl_kdforest_set_thresholding_method()

void vl_kdforest_set_thresholding_method | ( | VlKDForest * | self,
|  | VlKDTreeThresholdingMethod | method
| ) |  |

Parameters

  self | KDForest object.
  method | one of VlKDTreeThresholdingMethod.

See also
  vl_kdforest_get_thresholding_method

## ◆ vl_kdforestsearcher_delete()

void vl_kdforestsearcher_delete | ( | VlKDForestSearcher * | self | ) |

Parameters

  self | object.

## ◆ vl_kdforestsearcher_query()

vl_size vl_kdforestsearcher_query | ( | VlKDForestSearcher * | self,
|  | VlKDForestNeighbor * | neighbors,
|  | vl_size | numNeighbors,
|  | void const * | query
| ) |  |

Parameters

  self | object.
  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.