kdtree.c File Reference

binary search tree More...

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <grass/gis.h>
#include <grass/glocale.h>
#include "kdtree.h"

Include dependency graph for kdtree.c:

Go to the source code of this file.

Macros
#define	KD_BTOL   7

Functions
struct kdtree *	kdtree_create (char ndims, int *btol)
void	kdtree_clear (struct kdtree *t)
void	kdtree_destroy (struct kdtree *t)
int	kdtree_insert (struct kdtree *t, double *c, int uid, int dc)
int	kdtree_remove (struct kdtree *t, double *c, int uid)
void	kdtree_optimize (struct kdtree *t, int level)
int	kdtree_knn (struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
int	kdtree_dnn (struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
int	kdtree_rnn (struct kdtree *t, double *c, int **puid, int *skip)
int	kdtree_init_trav (struct kdtrav *trav, struct kdtree *tree)
int	kdtree_traverse (struct kdtrav *trav, double *c, int *uid)

Detailed Description

binary search tree

Dynamic balanced k-d tree implementation

(C) 2014 by the GRASS Development Team

This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.

Author

Markus Metz

Definition in file kdtree.c.

Macro Definition Documentation

KD_BTOL

#define KD_BTOL   7

Definition at line 23 of file kdtree.c.

Referenced by kdtree_create().

Function Documentation

kdtree_clear()

void kdtree_clear

(

struct kdtree *

t

)

clear a tree, removing all entries

Definition at line 138 of file kdtree.c.

References kdnode::child, NULL, and kdtree::root.

Referenced by kdtree_destroy().

kdtree_create()

struct kdtree* kdtree_create	(	char	ndims,
		int *	btol
	)

creae a new k-d tree

Parameters

ndims	number of dimensions
btol	optional balancing tolerance

Definition at line 110 of file kdtree.c.

References kdtree::btol, kdtree::count, kdtree::csize, G_malloc, KD_BTOL, kdtree::ndims, kdtree::nextdim, NULL, kdtree::root, and t.

kdtree_destroy()

void kdtree_destroy

(

struct kdtree *

t

)

destroy a tree

Definition at line 166 of file kdtree.c.

References G_free(), kdtree_clear(), kdtree::nextdim, and NULL.

kdtree_dnn()

int kdtree_dnn	(	struct kdtree *	t,
		double *	c,
		int **	puid,
		double **	pd,
		double	maxdist,
		int *	skip
	)

find all nearest neighbors within distance aka radius search results are stored in puid (uids) and pd (squared distances) memory is allocated as needed, the calling fn must free the memory optionally an uid to be skipped can be given

Parameters

t	k-d tree
c	coordinates
puid	unique ids of the neighbors
pd	squared distances to the neighbors
maxdist	radius to search around the given coordinates
skip	unique id to skip

Definition at line 624 of file kdtree.c.

kdtree_init_trav()

int kdtree_init_trav	(	struct kdtrav *	trav,
		struct kdtree *	tree
	)

initialize tree traversal (re-)sets trav structure returns 0

Definition at line 835 of file kdtree.c.

References kdtrav::curr_node, kdtrav::first, kdtree::root, kdtrav::top, and kdtrav::tree.

kdtree_insert()

int kdtree_insert	(	struct kdtree *	t,
		double *	c,
		int	uid,
		int	dc
	)

insert an item (coordinates c and uid) into the k-d tree

Parameters

t	k-d tree
c	coordinates
uid	the point's unique id
dc	allow duplicate coordinates

Definition at line 178 of file kdtree.c.

kdtree_knn()

int kdtree_knn	(	struct kdtree *	t,
		double *	c,
		int *	uid,
		double *	d,
		int	k,
		int *	skip
	)

find k nearest neighbors results are stored in uid (uids) and d (squared distances) optionally an uid to be skipped can be given useful when searching for the nearest neighbors of an item that is also in the tree

Parameters

t	k-d tree
c	coordinates
uid	unique ids of the neighbors
d	squared distances to the neighbors
k	number of neighbors to find
skip	unique id to skip

Definition at line 501 of file kdtree.c.

kdtree_optimize()

void kdtree_optimize	(	struct kdtree *	t,
		int	level
	)

k-d tree optimization, only useful if the tree will be heavily used (more searches than items in the tree) level 0 = a bit, 1 = more, 2 = a lot

Parameters

t	k-d tree
level	optimization level

Definition at line 331 of file kdtree.c.

kdtree_remove()

int kdtree_remove	(	struct kdtree *	t,
		double *	c,
		int	uid
	)

remove an item from the k-d tree coordinates c and uid must match

Parameters

t	k-d tree
c	coordinates
uid	the point's unique id

Definition at line 201 of file kdtree.c.

kdtree_rnn()

int kdtree_rnn	(	struct kdtree *	t,
		double *	c,
		int **	puid,
		int *	skip
	)

find all nearest neighbors within range aka box search the range is specified with min and max for each dimension as (min1, min2, ..., minn, max1, max2, ..., maxn) results are stored in puid (uids) and pd (squared distances) memory is allocated as needed, the calling fn must free the memory optionally an uid to be skipped can be given

Parameters

t	k-d tree
c	coordinates for range
puid	unique ids of the neighbors
skip	unique id to skip

Definition at line 739 of file kdtree.c.

kdtree_traverse()

int kdtree_traverse	(	struct kdtrav *	trav,
		double *	c,
		int *	uid
	)

traverse the tree useful to get all items in the tree non-recursively struct kdtrav *trav needs to be initialized first returns 1, 0 when finished

Definition at line 850 of file kdtree.c.