Go to the source code of this file.
|
#define | RootOf(T) ((T)->Root.Left->Data) |
|
|
KDTREE * | MakeKDTree (int16_t KeySize, const PARAM_DESC KeyDesc[]) |
|
void | KDStore (KDTREE *Tree, float *Key, void *Data) |
|
void | KDDelete (KDTREE *Tree, float Key[], void *Data) |
|
void | KDNearestNeighborSearch (KDTREE *Tree, float Query[], int QuerySize, float MaxDistance, int *NumberOfResults, void **NBuffer, float DBuffer[]) |
|
void | KDWalk (KDTREE *Tree, void_proc Action, void *context) |
|
void | FreeKDTree (KDTREE *Tree) |
|
KDNODE * | MakeKDNode (KDTREE *tree, float Key[], void *Data, int Index) |
|
void | FreeKDNode (KDNODE *Node) |
|
float | DistanceSquared (int k, PARAM_DESC *dim, float p1[], float p2[]) |
|
float | ComputeDistance (int k, PARAM_DESC *dim, float p1[], float p2[]) |
|
int | QueryInSearch (KDTREE *tree) |
|
void | Walk (KDTREE *tree, void_proc action, void *context, KDNODE *SubTree, int32_t Level) |
|
void | InsertNodes (KDTREE *tree, KDNODE *nodes) |
|
void | FreeSubTree (KDNODE *SubTree) |
|
◆ RootOf
#define RootOf |
( |
|
T | ) |
((T)->Root.Left->Data) |
◆ void_proc
◆ ComputeDistance()
float ComputeDistance |
( |
int |
k, |
|
|
PARAM_DESC * |
dim, |
|
|
float |
p1[], |
|
|
float |
p2[] |
|
) |
| |
◆ DistanceSquared()
float DistanceSquared |
( |
int |
k, |
|
|
PARAM_DESC * |
dim, |
|
|
float |
p1[], |
|
|
float |
p2[] |
|
) |
| |
Returns the Euclidean distance squared between p1 and p2 for all essential dimensions.
- Parameters
-
k | keys are in k-space |
dim | dimension descriptions (essential, circular, etc) |
p1,p2 | two different points in K-D space |
Definition at line 426 of file kdtree.cpp.
428 float total_distance = 0;
430 for (; k > 0; k--, p1++, p2++, dim++) {
434 float dimension_distance = *p1 - *p2;
438 dimension_distance =
Magnitude(dimension_distance);
439 float wrap_distance = dim->
Max - dim->
Min - dimension_distance;
440 dimension_distance = std::min(dimension_distance, wrap_distance);
443 total_distance += dimension_distance * dimension_distance;
445 return total_distance;
◆ FreeKDNode()
void FreeKDNode |
( |
KDNODE * |
Node | ) |
|
◆ FreeKDTree()
void FreeKDTree |
( |
KDTREE * |
Tree | ) |
|
This routine frees all memory which is allocated to the specified KD-tree. This includes the data structure for the kd-tree itself plus the data structures for each node in the tree. It does not include the Key and Data items which are pointed to by the nodes. This memory is left untouched.
- Parameters
-
Tree | tree data structure to be released |
Definition at line 330 of file kdtree.cpp.
◆ FreeSubTree()
void FreeSubTree |
( |
KDNODE * |
sub_tree | ) |
|
Free all of the nodes of a sub tree.
Definition at line 531 of file kdtree.cpp.
533 if (sub_tree !=
nullptr) {
◆ InsertNodes()
Given a subtree nodes, insert all of its elements into tree.
Definition at line 521 of file kdtree.cpp.
523 if (nodes ==
nullptr)
◆ KDDelete()
void KDDelete |
( |
KDTREE * |
Tree, |
|
|
float |
Key[], |
|
|
void * |
Data |
|
) |
| |
This routine deletes a node from Tree. The node to be deleted is specified by the Key for the node and the Data contents of the node. These two pointers must be identical to the pointers that were used for the node when it was originally stored in the tree. A node will be deleted from the tree only if its key and data pointers are identical to Key and Data respectively. The tree is re-formed by removing the affected subtree and inserting all elements but the root.
- Parameters
-
Tree | K-D tree to delete node from |
Key | key of node to be deleted |
Data | data contents of node to be deleted |
Definition at line 252 of file kdtree.cpp.
259 Father = &(Tree->
Root);
260 Current = Father->
Left;
261 Level = NextLevel(Tree, -1);
264 while ((Current !=
nullptr) && (!
NodeFound (Current, Key, Data))) {
267 Current = Current->
Left;
269 Current = Current->
Right;
271 Level = NextLevel(Tree, Level);
274 if (Current !=
nullptr) {
275 if (Current == Father->
Left) {
276 Father->
Left =
nullptr;
279 Father->
Right =
nullptr;
◆ KDNearestNeighborSearch()
void KDNearestNeighborSearch |
( |
KDTREE * |
Tree, |
|
|
float |
Query[], |
|
|
int |
QuerySize, |
|
|
float |
MaxDistance, |
|
|
int * |
NumberOfResults, |
|
|
void ** |
NBuffer, |
|
|
float |
DBuffer[] |
|
) |
| |
This routine searches the K-D tree specified by Tree and finds the QuerySize nearest neighbors of Query. All neighbors must be within MaxDistance of Query. The data contents of the nearest neighbors are placed in NBuffer and their distances from Query are placed in DBuffer.
- Parameters
-
Tree | ptr to K-D tree to be searched |
Query | ptr to query key (point in D-space) |
QuerySize | number of nearest neighbors to be found |
MaxDistance | all neighbors must be within this distance |
NBuffer | ptr to QuerySize buffer to hold nearest neighbors |
DBuffer | ptr to QuerySize buffer to hold distances from nearest neighbor to query point |
NumberOfResults | [out] Number of nearest neighbors actually found |
Definition at line 304 of file kdtree.cpp.
309 search.Search(NumberOfResults, DBuffer, NBuffer);
◆ KDStore()
void KDStore |
( |
KDTREE * |
Tree, |
|
|
float * |
Key, |
|
|
void * |
Data |
|
) |
| |
This routine stores Data in the K-D tree specified by Tree using Key as an access key.
- Parameters
-
Tree | K-D tree in which data is to be stored |
Key | ptr to key by which data can be retrieved |
Data | ptr to data to be stored in the tree |
Definition at line 211 of file kdtree.cpp.
219 Level = NextLevel(Tree, -1);
220 while (Node !=
nullptr) {
222 PtrToNode = &(Node->
Left);
227 PtrToNode = &(Node->
Right);
231 Level = NextLevel(Tree, Level);
235 *PtrToNode =
MakeKDNode(Tree, Key, Data, Level);
◆ KDWalk()
Walk a given Tree with action.
Definition at line 314 of file kdtree.cpp.
◆ MakeKDNode()
KDNODE* MakeKDNode |
( |
KDTREE * |
tree, |
|
|
float |
Key[], |
|
|
void * |
Data, |
|
|
int |
Index |
|
) |
| |
This routine allocates memory for a new K-D tree node and places the specified Key and Data into it. The left and right subtree pointers for the node are initialized to empty subtrees.
- Parameters
-
tree | The tree to create the node for |
Key | Access key for new node in KD tree |
Data | ptr to data to be stored in new node |
Index | index of Key to branch on |
- Returns
- pointer to new K-D tree node
Definition at line 351 of file kdtree.cpp.
358 NewNode->
Data = Data;
362 NewNode->
Left =
nullptr;
363 NewNode->
Right =
nullptr;
◆ MakeKDTree()
- Returns
- a new KDTREE based on the specified parameters.
- Parameters
-
KeySize | # of dimensions in the K-D tree |
KeyDesc | array of params to describe key dimensions |
Definition at line 179 of file kdtree.cpp.
181 auto *KDTree = static_cast<KDTREE *>(
Emalloc(
183 for (
int i = 0; i < KeySize; i++) {
184 KDTree->KeyDesc[i].NonEssential = KeyDesc[i].
NonEssential;
185 KDTree->KeyDesc[i].Circular = KeyDesc[i].
Circular;
186 if (KeyDesc[i].Circular) {
187 KDTree->KeyDesc[i].Min = KeyDesc[i].
Min;
188 KDTree->KeyDesc[i].Max = KeyDesc[i].
Max;
189 KDTree->KeyDesc[i].Range = KeyDesc[i].
Max - KeyDesc[i].
Min;
190 KDTree->KeyDesc[i].HalfRange = KDTree->KeyDesc[i].Range / 2;
191 KDTree->KeyDesc[i].MidRange = (KeyDesc[i].
Max + KeyDesc[i].
Min) / 2;
197 KDTree->KeySize = KeySize;
198 KDTree->Root.Left =
nullptr;
199 KDTree->Root.Right =
nullptr;
◆ QueryInSearch()
int QueryInSearch |
( |
KDTREE * |
tree | ) |
|
◆ Walk()
Walk a tree, calling action once on each node.
Operation: This routine walks through the specified sub_tree and invokes action action at each node as follows: action(context, data, level) data the data contents of the node being visited, level is the level of the node in the tree with the root being level 0.
- Parameters
-
tree | root of the tree being walked. |
action | action to be performed at every node |
context | action's context |
sub_tree | ptr to root of subtree to be walked |
level | current level in the tree for this node |
Definition at line 511 of file kdtree.cpp.
514 (*action)(context, sub_tree->
Data, level);
515 if (sub_tree->
Left !=
nullptr)
516 Walk(tree,
action, context, sub_tree->
Left, NextLevel(tree, level));
517 if (sub_tree->
Right !=
nullptr)