|
Crater Container Library 0.2.0
|
|
| |
|
Crater Container Library 0.2.0
|
|
|
| |
Function table for kd tree, see cr8r_kd_ft. More...
#include <kd_tree.h>
Data Fields | |
| cr8r_vec_ft | super |
| Subtable for vector ft. More... | |
| uint64_t | dim |
| Dimension of the kd tree. More... | |
| size_t | bounds_size |
| Size of a bounds object. More... | |
| void(* | split )(const cr8r_kd_ft *ft, const void *self, const void *root_pt, void *o1, void *o2) |
| split a bounds object in two along some dimension More... | |
| void(* | update )(const cr8r_kd_ft *ft, void *self, const void *pt) |
| update a bounds object to include some point More... | |
| double(* | min_sqdist )(const cr8r_kd_ft *ft, const void *self, const void *pt) |
| find the minimum squared distance from a bounds object to a point | |
| double(* | sqdist )(const cr8r_kd_ft *ft, const void *a, const void *b) |
| find the squared distance between two points | |
Function table for kd tree, see cr8r_kd_ft.
Function table for kd tree.
A kd tree is stored as an implicit binary tree in a vector. The root of the tree is the element of the vector at the middle position, and the left and right subranges correstpond to subtrees with roots at their middles and so on. This means kd trees do NOT support efficient insertion/removal of points. For that, we would need to use a self balancing tree like a modified avl or red black tree. Implicit binary trees are maximally balanced and do not have the space or time overheads of child pointers, so they are the better choice when adding/removing points is rare enough that performing linear time re-treeifying is acceptable.
| cr8r_vec_ft cr8r_kd_ft::super |
Subtable for vector ft.
Since kd trees are stored as vectors, a vector ft is included in the kd ft so that vector functions may be used and vector len/elem size queried without carrying around two fts. Note that this is exactly like saying kd extends vec if we consider how fts are just an implementation of classes in C, hence the name super.
| uint64_t cr8r_kd_ft::dim |
Dimension of the kd tree.
This is the number of directions points are split in. For instance, in a kd cuboid tree, there are k directions to split in. However, for a sphere in k dimensions, we can split in only k-1 directions. The first k-2 simply split points along some axis. For the final one however, points are split based on their angle about the origin in some plane. The important takeaway about this field is that points in the tree might have more than dim coordinates. To be clear, this is because for a spherical kd tree in k dimensions, only points on the surface of the sphere are allowed, or to be more accurate, all points are effectively projected onto the surface of a (hyper)cylinder with the same axis (axes). These peculiarities are specific to the implementation of cr8r_kdft_s2i64 and one could easily create a spherical kd tree that resolves these issues in other ways.
| size_t cr8r_kd_ft::bounds_size |
Size of a bounds object.
Generally a bounds object is encoded as bl, tr, where bl is a point with each coordinate equal to the minimum of that coordinate over all points in the tree, and tr is the same but for maximum (standing for bottom left and top right). TODO: should we replace bounds_size with coords or something? ft->super.base.size is the size of the key (point) + value (tag), dim is <= the number of coordinates in each point, etc
| void(* cr8r_kd_ft::split) (const cr8r_kd_ft *ft, const void *self, const void *root_pt, void *o1, void *o2) |
| void(* cr8r_kd_ft::update) (const cr8r_kd_ft *ft, void *self, const void *pt) |