GRASS GIS 7 Programmer's Manual
7.9.dev(2021)-e5379bbd7
|
To make use of the binary balanced (Red-Black) search tree include:
#include <grass/rbtree.h>
and link to BTREE2LIB
in a Makefile.
Define custom compare function:
int my_compare_fn(const void *a, const void *b) { if ((mydatastruct *) a < (mydatastruct *) b) return -1; else if ((mydatastruct *) a > (mydatastruct *) b) return 1; else if ((mydatastruct *) a == (mydatastruct *) b) return 0; }
Create and initialize tree:
struct RB_TREE *mytree = rbtree_create(my_compare_fn, item_size);
Insert items to tree:
struct mydatastruct data = <some data>; if (rbtree_insert(mytree, &data) == 0) G_warning("could not insert data");
Find item in tree:
struct mydatastruct data = <some data>; if (rbtree_find(mytree, &data) == 0) G_message("data not found");
Delete item from tree:
struct mydatastruct data = <some data>; if (rbtree_remove(mytree, &data) == 0) G_warning("could not find data in tree");
Traverse tree (get all items in tree in ascending order):
struct RB_TRAV trav; rbtree_init_trav(&trav, tree); while ((data = rbtree_traverse(&trav)) != NULL) { if (my_compare_fn(data, threshold_data) == 0) break;
do something with data (using C++ comments because of Doxygen) }
Get a selection of items: all data > data1 and < data2. Start in tree where data is last smaller or first larger compared to data1:
struct RB_TRAV trav; rbtree_init_trav(&trav, tree); data = rbtree_traverse_start(&trav, &data1);
do something with data while ((data = rbtree_traverse(&trav)) != NULL) { if (data > data2) break; do something with data }
Destroy tree:
rbtree_destroy(mytree);
Debug the whole tree with:
rbtree_debug(mytree, mytree->root);
See also rbtree.h for more instructions on how to use it.
k-d tree is a multidimensional (k-dimensional) binary search tree for nearest neighbor search.
This k-d tree finds the exact nearest neighbor(s), not some approximation. It supports up to 255 dimensions. It is dynamic, i.e. points can be inserted and removed at any time. It is balanced to improve search performance. It provides k nearest neighbor search (find k neighbors to a given coordinate) as well as radius or distance search (find all neighbors within radius, i.e. not farther away than radius to a given coordinate).
Include:
#include <grass/kdtree.h>
and link to BTREE2LIB
in a Makefile.
Create a new k-d tree (here 3D):
struct kdtree *t = kdtree_create(3, NULL);
Insert items:
for (i = 0; i < npoints; i++) kdtree_insert(t, c, i, 1);
Find nearest neighbor for each point:
for (i = 0; i < npoints; i++) int found = kdtree_knn(t, c, &uid, &dist, 1, i);
Destroy the tree:
kdtree_destroy(t);
v.nnstat
used an external k-d tree from PCL (which in turn uses flann) which finds the approximate, not the exact nearest neighbor. The GRASS-native k-d tree always finds the real nearest neighbor.v.cluster
.v.clean
tool=snap
(Vect_snap_lines()), reducing both memory consumption and processing time.