kdtree.c File Reference

#include "include/kdtree.h"

Include dependency graph for kdtree.c:

Functions
void	kd_tree_build_tree (TREE_RECORD *tree_record, TREE_PARAMETERS *params)
void	kd_tree_find_best_split (int depth, int left, int right, TREE_RECORD *tree_record, TREE_PARAMETERS *params, int *axis, int *pivot_idx, FLOAT_TYPE *splitting_value)
void	kd_tree_build_recursive (TREE_RECORD *tree_record, TREE_PARAMETERS *params, INT_TYPE left, INT_TYPE right, INT_TYPE idx, INT_TYPE depth)
void	kd_tree_generate_training_patterns_indices (void *XI, FLOAT_TYPE *X, INT_TYPE n, INT_TYPE dim)
INT_TYPE	kd_tree_split_training_patterns_via_pivot (void *XI, INT_TYPE left, INT_TYPE right, INT_TYPE axis, INT_TYPE dim)

Function Documentation

void kd_tree_build_recursive	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params,
		INT_TYPE	left,
		INT_TYPE	right,
		INT_TYPE	idx,
		INT_TYPE	depth
	)

Helper method to build up the kd-tree in a recursive manner.

Parameters

*tree_record	Pointer to struct instance storing the model
*params	Pointer to struct instance storing all model parameters
left	The left bound of values to be tested
right	The right bound of values to be tested
idx	The current node index
depth	The current tree depth

void kd_tree_build_tree	(	TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params
	)

Builds the kd-tree (recursive construction)

Parameters

*tree_record	Pointer to struct instance storing the model
*params	Pointer to struct instance storing all model parameters

void kd_tree_find_best_split	(	int	depth,
		int	left,
		int	right,
		TREE_RECORD *	tree_record,
		TREE_PARAMETERS *	params,
		int *	axis,
		int *	pivot_idx,
		FLOAT_TYPE *	splitting_value
	)

Finds the optimal splitting axis.

Parameters

depth	The current depth of the splitting process
left	The left bound of values to be tested
right	The right bound of values to be tested
*tree_record	Pointer to struct instance storing the model
*params	Pointer to struct instance storing all model parameters
*axis	The current axis
*pivot_idx	The output pivot index
*splitting_value	The output splitting value

void kd_tree_generate_training_patterns_indices	(	void *	XI,
		FLOAT_TYPE *	X,
		INT_TYPE	n,
		INT_TYPE	dim
	)

Parse patterns and store the original indices (this array of both the FLOAT_TYPEs and the indices) is sorted in-place during the construction of the kd-tree.

Parameters

*XI	Pointer to array containing patterns and indices
*X	Pointer to array containing patterns
n	Number of elements in arrays
dim	Dimensionality of patterns

INT_TYPE kd_tree_split_training_patterns_via_pivot	(	void *	XI,
		INT_TYPE	left,
		INT_TYPE	right,
		INT_TYPE	axis,
		INT_TYPE	dim
	)

Sorts the training patterns in range left to right (inclusive) with respect to "axis".

Parameters

*XI	Pointer to array containing patterns and indices
left	The left bound of points to be tested
right	The right bound of points to be tested
axis	The current axis
dim	Dimensionality of patterns