GRASS GIS 8 Programmer's Manual 8.3.2(2024)-exported
|
binary search tree More...
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <grass/gis.h>
#include <grass/glocale.h>
#include "kdtree.h"
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) |
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.
Definition in file kdtree.c.
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().
struct kdtree * kdtree_create | ( | char | ndims, |
int * | btol | ||
) |
creae a new k-d tree
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.
void kdtree_destroy | ( | struct kdtree * | t | ) |
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
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.
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.
int kdtree_insert | ( | struct kdtree * | t, |
double * | c, | ||
int | uid, | ||
int | dc | ||
) |
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
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.
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
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.
int kdtree_remove | ( | struct kdtree * | t, |
double * | c, | ||
int | uid | ||
) |
remove an item from the k-d tree coordinates c and uid must match
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.
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
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.
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 kdnode::c, kdtrav::curr_node, kdtrav::first, G_debug(), NULL, and kdnode::uid.