tdkdtree.h File Reference
A kd-tree data structure for top-down searching: header file. More...
Go to the source code of this file.
Data Structures | |
| struct | kdnode |
Node definition. There exists two types of nodes: internal nodes partition the space by a cut plane defined by a value in one of the k dimensions; external nodes (aka buckets) store the points in the resulting hyperplanes of the partition. The variable bucket is 1 if the node is a bucket and zero if it is an internal node. In an internal node, cutdim gives the dimension being partitioned, cutval is a value in that dimension, and loson and hison are pointers to its two subtrees (containing respectively, points not greather than and not less than cutval in that dimension). In a bucket, the points that are contained in it are represented by indexes that are in the range perm[lopt,hipt]. The global variable perm is called as permutation vector. The number of points is represented by the expression hipt - lopt + 1. More... | |
| struct | infokdnode |
| Information for a Node definition. This data structure saves the information related for a virtual internal node. The variables have the meaning given for the kdnode data structure. The points that are virtually contained in the loson and hison are represented by indexes that are in the range perm[lopt_l,hipt_l] and perm[lopt_h,hipt_h], respectively. More... | |
| struct | kdtree |
| Multidimensional tree definition. A k-dimensional binary search tree (abbreviated kd-tree) represents a set of n points {y} in an space of k dimensions. The variable perm is the permutation vector that contains the indices of all the points. The variable root is the tree root. More... | |
Typedefs | |
| typedef struct kdnode | kdnode |
Node definition. There exists two types of nodes: internal nodes partition the space by a cut plane defined by a value in one of the k dimensions; external nodes (aka buckets) store the points in the resulting hyperplanes of the partition. The variable bucket is 1 if the node is a bucket and zero if it is an internal node. In an internal node, cutdim gives the dimension being partitioned, cutval is a value in that dimension, and loson and hison are pointers to its two subtrees (containing respectively, points not greather than and not less than cutval in that dimension). In a bucket, the points that are contained in it are represented by indexes that are in the range perm[lopt,hipt]. The global variable perm is called as permutation vector. The number of points is represented by the expression hipt - lopt + 1. | |
| typedef struct infokdnode | infokdnode |
| Information for a Node definition. This data structure saves the information related for a virtual internal node. The variables have the meaning given for the kdnode data structure. The points that are virtually contained in the loson and hison are represented by indexes that are in the range perm[lopt_l,hipt_l] and perm[lopt_h,hipt_h], respectively. | |
| typedef struct kdtree | kdtree |
| Multidimensional tree definition. A k-dimensional binary search tree (abbreviated kd-tree) represents a set of n points {y} in an space of k dimensions. The variable perm is the permutation vector that contains the indices of all the points. The variable root is the tree root. | |
Functions | |
| kdtree * | newtdkdtree () |
| int | tdnn () |
| void | destroytdkdtree () |
Detailed Description
A kd-tree data structure for top-down searching: header file.
- Version:
- 10.10
- Date:
- October 10th, 2010
A straightforward implementation of a kd-tree data structure for top-down searching based on a description of J. L. Bentley (1990).
- Note:
- Last change was in October 19th, 2010.
Definition in file tdkdtree.h.
Typedef Documentation
| typedef struct infokdnode infokdnode |
Information for a Node definition. This data structure saves the information related for a virtual internal node.
The variables have the meaning given for the kdnode data structure. The points that are virtually contained in the loson and hison are represented by indexes that are in the range perm[lopt_l,hipt_l] and perm[lopt_h,hipt_h], respectively.
Node definition. There exists two types of nodes: internal nodes partition the space by a cut plane defined by a value in one of the k dimensions; external nodes (aka buckets) store the points in the resulting hyperplanes of the partition. The variable bucket is 1 if the node is a bucket and zero if it is an internal node.
In an internal node, cutdim gives the dimension being partitioned, cutval is a value in that dimension, and loson and hison are pointers to its two subtrees (containing respectively, points not greather than and not less than cutval in that dimension).
In a bucket, the points that are contained in it are represented by indexes that are in the range perm[lopt,hipt]. The global variable perm is called as permutation vector. The number of points is represented by the expression hipt - lopt + 1.
Multidimensional tree definition. A k-dimensional binary search tree (abbreviated kd-tree) represents a set of n points {y} in an space of k dimensions.
The variable perm is the permutation vector that contains the indices of all the points. The variable root is the tree root.
Function Documentation
| void destroytdkdtree | ( | ) |
- See also:
- destroytdkdtree
| kdtree* newtdkdtree | ( | ) |
- See also:
- newtdkdtree
| int tdnn | ( | ) |
- See also:
- tdnn
