Loading...
Searching...
No Matches
kdtree.h File Reference

Dynamic balanced k-d tree implementation. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

## Data Structures

struct | kdnode
| Node for k-d tree. More...
struct | kdtree
| k-d tree More...
struct | kdtrav
| k-d tree traversal More...

## Functions

struct kdtree * | kdtree_create (char ndims, int *btol)
void | kdtree_destroy (struct kdtree *t)
void | kdtree_clear (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)
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)
void | kdtree_optimize (struct kdtree *t, int level)
int | kdtree_init_trav (struct kdtrav *trav, struct kdtree *tree)
int | kdtree_traverse (struct kdtrav *trav, double *c, int *uid)

## Detailed Description

Dynamic balanced k-d tree implementation.

k-d tree is a multidimensional (k-dimensional) binary search tree for nearest neighbor search and is part of GRASS Btree2 and k-d tree libraries.

Copyright and license:

(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

References
  Bentley, J. L. (1975). "Multidimensional binary search trees used for associative searching". Communications of the ACM 18 (9): 509. doi:10.1145/361002.361007

Features
  - This k-d tree is a dynamic tree: elements can be inserted and removed any time.
  - This k-d tree is balanced: subtrees have a similar depth (the difference in subtrees' depths is not allowed to be larger than the balancing tolerance).

Here is a structure of basic usage:

Create a new k-d tree:

    kdtree_create(...);

Insert points into the tree:

    kdtree_insert(...);

Optionally optimize the tree:

    kdtree_optimize(...);

Search k nearest neighbors:

    kdtree_knn(...);

Search all neighbors in radius:

    kdtree_dnn(...);

Destroy the tree:

    kdtree_destroy(...);

Todo
  Doxygen ignores comment for last parameter after );. The parameter description now goes to the end of function description.

Todo
  Include formatting to function descriptions.

Definition in file kdtree.h.

## Function Documentation

## kdtree_clear()

void kdtree_clear | ( | struct kdtree * | t | ) |

clear a tree, removing all entries

Definition at line 139 of file kdtree.c.

References kdnode::child, NULL, and t.

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 111 of file kdtree.c.

References kdtree::btol, KD_BTOL, kdtree::ndims, NULL, and t.

## kdtree_destroy()

void kdtree_destroy | ( | struct kdtree * | t | ) |

destroy a tree

Definition at line 167 of file kdtree.c.

References G_free(), kdtree_clear(), NULL, and t.

## 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 636 of file kdtree.c.

References kdnode::c, kdnode::child, kdnode::dim, G_fatal_error(), NULL, t, and kdnode::uid.

## 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 847 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 179 of file kdtree.c.

References kdnode::c, count, t, and kdnode::uid.

## 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 512 of file kdtree.c.

References kdnode::c, kdnode::child, kdnode::dim, G_fatal_error(), t, and kdnode::uid.

## 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 334 of file kdtree.c.

References kdnode::child, kdnode::depth, G_debug(), MAX, and t.

## 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 202 of file kdtree.c.

References kdnode::balance, kdnode::c, kdnode::child, kdnode::depth, kdnode::dim, G_warning(), NULL, r, t, and kdnode::uid.

## 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 751 of file kdtree.c.

References kdnode::c, kdnode::child, kdnode::dim, NULL, t, and kdnode::uid.

## 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 862 of file kdtree.c.

References kdtrav::curr_node, kdtrav::first, G_debug(), NULL, and kdnode::uid.