kdtree.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "kdtree/kdtree.h"

Include dependency graph for kdtree.c:

Data Structures
struct	kdhyperrect
struct	kdnode
struct	res_node
struct	kdtree
struct	kdres

Macros
#define	SQ(x)   ((x) * (x))
#define	alloc_resnode()   malloc(sizeof(struct res_node))
#define	free_resnode(n)   free(n)

Functions
static void	clear_rec (struct kdnode *node, void(*destr)(void *))
static int	insert_rec (struct kdnode **node, const double *pos, void *data, int dir, int dim)
static int	rlist_insert (struct res_node *list, struct kdnode *item, double dist_sq)
static void	clear_results (struct kdres *set)
static struct kdhyperrect *	hyperrect_create (int dim, const double *min, const double *max)
static void	hyperrect_free (struct kdhyperrect *rect)
static struct kdhyperrect *	hyperrect_duplicate (const struct kdhyperrect *rect)
static void	hyperrect_extend (struct kdhyperrect *rect, const double *pos)
static double	hyperrect_dist_sq (struct kdhyperrect *rect, const double *pos)
int	init_kdtree ()
struct kdtree *	kd_create (int k)
void	kd_free (struct kdtree *tree)
void	kd_clear (struct kdtree *tree)
void	kd_data_destructor (struct kdtree *tree, void(*destr)(void *))
int	kd_insert (struct kdtree *tree, const double *pos, void *data)
int	kd_insertf (struct kdtree *tree, const float *pos, void *data)
int	kd_insert3 (struct kdtree *tree, double x, double y, double z, void *data)
int	kd_insert3f (struct kdtree *tree, float x, float y, float z, void *data)
static int	find_nearest (struct kdnode *node, const double *pos, double range, struct res_node *list, int ordered, int dim)
static void	kd_nearest_i (struct kdnode *node, const double *pos, struct kdnode **result, double *result_dist_sq, struct kdhyperrect *rect)
struct kdres *	kd_nearest (struct kdtree *kd, const double *pos)
struct kdres *	kd_nearestf (struct kdtree *tree, const float *pos)
struct kdres *	kd_nearest3 (struct kdtree *tree, double x, double y, double z)
struct kdres *	kd_nearest3f (struct kdtree *tree, float x, float y, float z)
struct kdres *	kd_nearest_range (struct kdtree *kd, const double *pos, double range)
struct kdres *	kd_nearest_rangef (struct kdtree *kd, const float *pos, float range)
struct kdres *	kd_nearest_range3 (struct kdtree *tree, double x, double y, double z, double range)
struct kdres *	kd_nearest_range3f (struct kdtree *tree, float x, float y, float z, float range)
void	kd_res_free (struct kdres *rset)
int	kd_res_size (struct kdres *set)
void	kd_res_rewind (struct kdres *rset)
int	kd_res_end (struct kdres *rset)
int	kd_res_next (struct kdres *rset)
void *	kd_res_item (struct kdres *rset, double *pos)
void *	kd_res_itemf (struct kdres *rset, float *pos)
void *	kd_res_item3 (struct kdres *rset, double *x, double *y, double *z)
void *	kd_res_item3f (struct kdres *rset, float *x, float *y, float *z)
void *	kd_res_item_data (struct kdres *set)

Macro Definition Documentation

alloc_resnode

#define alloc_resnode

(

)

malloc(sizeof(struct res_node))

free_resnode

#define free_resnode

(

n

)

free(n)

SQ

#define SQ

(

x

)

((x) * (x))

Function Documentation

clear_rec()

static void clear_rec ( struct kdnode *  node, void(*)(void *)  destr  )

static

clear_results()

static void clear_results ( struct kdres *  set )

static

find_nearest()

static int find_nearest ( struct kdnode *  node, const double *  pos, double  range, struct res_node *  list, int  ordered, int  dim  )

static

hyperrect_create()

static struct kdhyperrect * hyperrect_create ( int  dim, const double *  min, const double *  max  )

static

hyperrect_dist_sq()

static double hyperrect_dist_sq ( struct kdhyperrect *  rect, const double *  pos  )

static

hyperrect_duplicate()

static struct kdhyperrect * hyperrect_duplicate ( const struct kdhyperrect *  rect )

static

hyperrect_extend()

static void hyperrect_extend ( struct kdhyperrect *  rect, const double *  pos  )

static

hyperrect_free()

static void hyperrect_free ( struct kdhyperrect *  rect )

static

init_kdtree()

int init_kdtree

(

)

insert_rec()

static int insert_rec ( struct kdnode **  node, const double *  pos, void *  data, int  dir, int  dim  )

static

kd_clear()

void kd_clear

(

struct kdtree *

tree

)

kd_create()

struct kdtree* kd_create

(

int

k

)

kd_data_destructor()

void kd_data_destructor	(	struct kdtree *	tree,
		void(*)(void *)	destr
	)

kd_free()

void kd_free

(

struct kdtree *

tree

)

kd_insert()

int kd_insert	(	struct kdtree *	tree,
		const double *	pos,
		void *	data
	)

kd_insert3()

int kd_insert3	(	struct kdtree *	tree,
		double	x,
		double	y,
		double	z,
		void *	data
	)

kd_insert3f()

int kd_insert3f	(	struct kdtree *	tree,
		float	x,
		float	y,
		float	z,
		void *	data
	)

kd_insertf()

int kd_insertf	(	struct kdtree *	tree,
		const float *	pos,
		void *	data
	)

kd_nearest()

struct kdres* kd_nearest	(	struct kdtree *	kd,
		const double *	pos
	)

kd_nearest3()

struct kdres* kd_nearest3	(	struct kdtree *	tree,
		double	x,
		double	y,
		double	z
	)

kd_nearest3f()

struct kdres* kd_nearest3f	(	struct kdtree *	tree,
		float	x,
		float	y,
		float	z
	)

kd_nearest_i()

static void kd_nearest_i ( struct kdnode *  node, const double *  pos, struct kdnode **  result, double *  result_dist_sq, struct kdhyperrect *  rect  )

static

kd_nearest_range()

struct kdres* kd_nearest_range	(	struct kdtree *	kd,
		const double *	pos,
		double	range
	)

kd_nearest_range3()

struct kdres* kd_nearest_range3	(	struct kdtree *	tree,
		double	x,
		double	y,
		double	z,
		double	range
	)

kd_nearest_range3f()

struct kdres* kd_nearest_range3f	(	struct kdtree *	tree,
		float	x,
		float	y,
		float	z,
		float	range
	)

kd_nearest_rangef()

struct kdres* kd_nearest_rangef	(	struct kdtree *	kd,
		const float *	pos,
		float	range
	)

kd_nearestf()

struct kdres* kd_nearestf	(	struct kdtree *	tree,
		const float *	pos
	)

kd_res_end()

int kd_res_end

(

struct kdres *

rset

)

kd_res_free()

void kd_res_free

(

struct kdres *

rset

)

kd_res_item()

void* kd_res_item	(	struct kdres *	rset,
		double *	pos
	)

kd_res_item3()

void* kd_res_item3	(	struct kdres *	rset,
		double *	x,
		double *	y,
		double *	z
	)

kd_res_item3f()

void* kd_res_item3f	(	struct kdres *	rset,
		float *	x,
		float *	y,
		float *	z
	)

kd_res_item_data()

void* kd_res_item_data

(

struct kdres *

set

)

kd_res_itemf()

void* kd_res_itemf	(	struct kdres *	rset,
		float *	pos
	)

kd_res_next()

int kd_res_next

(

struct kdres *

rset

)

kd_res_rewind()

void kd_res_rewind

(

struct kdres *

rset

)

kd_res_size()

int kd_res_size

(

struct kdres *

set

)

rlist_insert()

static int rlist_insert ( struct res_node *  list, struct kdnode *  item, double  dist_sq  )

static