#include "kdtree.h"
#include "const.h"
#include "emalloc.h"
#include "freelist.h"
#include <stdio.h>
#include <math.h>
#include <setjmp.h>
Go to the source code of this file.
#define Magnitude | ( | X | ) | ((X) < 0 ? -(X) : (X)) |
** (c) Copyright Hewlett-Packard Company, 1988. ** Licensed under the Apache License, Version 2.0 (the "License"); ** you may not use this file except in compliance with the License. ** You may obtain a copy of the License at ** http://www.apache.org/licenses/LICENSE-2.0 ** Unless required by applicable law or agreed to in writing, software ** distributed under the License is distributed on an "AS IS" BASIS, ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. ** See the License for the specific language governing permissions and ** limitations under the License.
Definition at line 34 of file kdtree.cpp.
Referenced by ComputeDistance().
#define MAXSEARCH MAX_FLOAT32 |
#define MIN | ( | A, | |||
B | ) | ((A) < (B) ? (A) : (B)) |
Definition at line 35 of file kdtree.cpp.
#define MINSEARCH -MAX_FLOAT32 |
FLOAT32 ComputeDistance | ( | register int | N, | |
register PARAM_DESC | Dim[], | |||
register FLOAT32 | p1[], | |||
register FLOAT32 | p2[] | |||
) |
Computes the euclidian distance between p1 and p2 in K-D space (an N dimensional space); where p1 != p2.
N | Number of dimensions in K-D space | |
Dim | Descriptions of each dimension | |
p1 | first point in K-D space | |
p2 | second point in K-D space |
Definition at line 603 of file kdtree.cpp.
References Magnitude, and MIN.
Referenced by Search().
00605 { 00606 register FLOAT32 TotalDistance; 00607 register FLOAT32 DimensionDistance; 00608 FLOAT32 WrapDistance; 00609 00610 TotalDistance = 0; 00611 for (; N > 0; N--, p1++, p2++, Dim++) { 00612 if (Dim->NonEssential) 00613 continue; 00614 00615 DimensionDistance = *p1 - *p2; 00616 00617 /* if this dimension is circular - check wraparound distance */ 00618 if (Dim->Circular) { 00619 DimensionDistance = Magnitude (DimensionDistance); 00620 WrapDistance = Dim->Max - Dim->Min - DimensionDistance; 00621 DimensionDistance = MIN (DimensionDistance, WrapDistance); 00622 } 00623 00624 TotalDistance += DimensionDistance * DimensionDistance; 00625 } 00626 return ((FLOAT32) sqrt ((FLOAT64) TotalDistance)); 00627 } /* ComputeDistance */
Compares values referenced by Key1 with that of Key2.
Key1 | Search key to be compared for equality | |
Key2 | Search key to be compared for equality |
Definition at line 438 of file kdtree.cpp.
References FALSE, N, and TRUE.
00438 { 00439 int i; 00440 00441 for (i = N; i > 0; i--, Key1++, Key2++) 00442 if (*Key1 != *Key2) 00443 return (FALSE); 00444 return (TRUE); 00445 } /* Equal */
void FindMaxDistance | ( | ) |
Searches the Distance buffer for the maximum distance, places this distance in Radius, and places the index of this distance in Furthest.
None |
Definition at line 646 of file kdtree.cpp.
References Distance, Furthest, MaxNeighbors, and Radius.
Referenced by Search().
00646 { 00647 int i; 00648 00649 Radius = Distance[Furthest]; 00650 for (i = 0; i < MaxNeighbors; i++) { 00651 if (Distance[i] > Radius) { 00652 Radius = Distance[i]; 00653 Furthest = i; 00654 } 00655 } 00656 } /* FindMaxDistance */
void FreeKDNode | ( | KDNODE * | Node | ) |
Frees up the memory allocated to Node.
Node | ptr to node data structure to be freed |
Definition at line 491 of file kdtree.cpp.
References memfree().
Referenced by KDDelete().
00491 { 00492 memfree ((char *) Node); 00493 } /* FreeKDNode */
void FreeKDTree | ( | KDTREE * | Tree | ) |
Frees all memory which is allocated to the specified KD-tree.
Tree | tree data structure to be released |
It does not include the Key and Data items which are pointed to by the nodes. This memory is left untouched.
Definition at line 418 of file kdtree.cpp.
References FreeSubTree(), kdnode::Left, memfree(), KDTREE::Root, and Tree.
Referenced by CreateClusterTree(), and FreeClusterer().
void FreeSubTree | ( | KDNODE * | SubTree | ) |
Recursively frees the memory allocated to to the specified subtree.
SubTree | ptr to root node of sub-tree to be freed |
Definition at line 827 of file kdtree.cpp.
References FreeSubTree(), kdnode::Left, memfree(), NULL, and kdnode::Right.
Referenced by FreeKDTree(), and FreeSubTree().
00827 { 00828 if (SubTree != NULL) { 00829 FreeSubTree (SubTree->Left); 00830 FreeSubTree (SubTree->Right); 00831 memfree(SubTree); 00832 } 00833 } /* FreeSubTree */
Deletes a node from Tree.
Tree | K-D tree to delete node from | |
Key | key of node to be deleted | |
Data | data contents of node to be deleted |
The empty space left in the tree is filled by pulling a leaf up from the bottom of one of the subtrees of the node being deleted. The leaf node will be pulled from left subtrees whenever possible (this was an arbitrary decision).
No attempt is made to pull the leaf from the deepest subtree (to minimize length). The branch point for the replacement node is changed to be the same as the branch point of the deleted node. This keeps us from having to rearrange the tree every time we delete a node. Also, the LeftBranch and RightBranch numbers of the replacement node are set to be the same as the deleted node. The makes the delete easier and more efficient, but it may make searches in the tree less efficient after many nodes are deleted.
If the node specified by Key and Data does not exist in the tree, then nothing is done.
Definition at line 232 of file kdtree.cpp.
References kdnode::BranchPoint, FreeKDNode(), KeyDesc, KDTREE::KeyDesc, KDTREE::KeySize, kdnode::Left, kdnode::LeftBranch, PARAM_DESC::Max, PARAM_DESC::Min, N, NodeFound, NULL, kdnode::Right, kdnode::RightBranch, KDTREE::Root, Tree, and TRUE.
Referenced by MakeNewCluster().
00232 { 00233 int Level; 00234 KDNODE *Current; 00235 KDNODE *Father; 00236 KDNODE *Replacement; 00237 KDNODE *FatherReplacement; 00238 00239 /* initialize search at root of tree */ 00240 N = Tree->KeySize; 00241 KeyDesc = &(Tree->KeyDesc[0]); 00242 Father = &(Tree->Root); 00243 Current = Father->Left; 00244 Level = 0; 00245 00246 /* search tree for node to be deleted */ 00247 while ((Current != NULL) && (!NodeFound (Current, Key, Data))) { 00248 Father = Current; 00249 if (Key[Level] < Current->BranchPoint) 00250 Current = Current->Left; 00251 else 00252 Current = Current->Right; 00253 00254 Level++; 00255 if (Level >= N) 00256 Level = 0; 00257 } 00258 00259 if (Current != NULL) { /* if node to be deleted was found */ 00260 Replacement = Current; 00261 FatherReplacement = Father; 00262 00263 /* search for replacement node (a leaf under node to be deleted */ 00264 while (TRUE) { 00265 if (Replacement->Left != NULL) { 00266 FatherReplacement = Replacement; 00267 Replacement = Replacement->Left; 00268 } 00269 else if (Replacement->Right != NULL) { 00270 FatherReplacement = Replacement; 00271 Replacement = Replacement->Right; 00272 } 00273 else 00274 break; 00275 00276 Level++; 00277 if (Level >= N) 00278 Level = 0; 00279 } 00280 00281 /* compute level of replacement node's father */ 00282 Level--; 00283 if (Level < 0) 00284 Level = N - 1; 00285 00286 /* disconnect replacement node from it's father */ 00287 if (FatherReplacement->Left == Replacement) { 00288 FatherReplacement->Left = NULL; 00289 FatherReplacement->LeftBranch = KeyDesc[Level].Min; 00290 } 00291 else { 00292 FatherReplacement->Right = NULL; 00293 FatherReplacement->RightBranch = KeyDesc[Level].Max; 00294 } 00295 00296 /* replace deleted node with replacement (unless they are the same) */ 00297 if (Replacement != Current) { 00298 Replacement->BranchPoint = Current->BranchPoint; 00299 Replacement->LeftBranch = Current->LeftBranch; 00300 Replacement->RightBranch = Current->RightBranch; 00301 Replacement->Left = Current->Left; 00302 Replacement->Right = Current->Right; 00303 00304 if (Father->Left == Current) 00305 Father->Left = Replacement; 00306 else 00307 Father->Right = Replacement; 00308 } 00309 FreeKDNode(Current); 00310 } 00311 } /* KDDelete */
int KDNearestNeighborSearch | ( | KDTREE * | Tree, | |
FLOAT32 | Query[], | |||
int | QuerySize, | |||
FLOAT32 | MaxDistance, | |||
void * | NBuffer, | |||
FLOAT32 | DBuffer[] | |||
) |
Finds QuerySize nearest neighbors of Query in KD-tree.
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 |
Definition at line 351 of file kdtree.cpp.
References Distance, Furthest, KeyDesc, KDTREE::KeyDesc, KDTREE::KeySize, LBMax, LBMin, kdnode::Left, PARAM_DESC::Max, MaxNeighbors, PARAM_DESC::Min, N, Neighbor, NULL, NumberOfNeighbors, QueryPoint, QuickExit, Radius, KDTREE::Root, SBMax, SBMin, Search(), and Tree.
Referenced by FindNearestNeighbor().
00355 { 00356 int i; 00357 00358 NumberOfNeighbors = 0; 00359 N = Tree->KeySize; 00360 KeyDesc = &(Tree->KeyDesc[0]); 00361 QueryPoint = Query; 00362 MaxNeighbors = QuerySize; 00363 Radius = MaxDistance; 00364 Furthest = 0; 00365 Neighbor = (char **) NBuffer; 00366 Distance = DBuffer; 00367 00368 for (i = 0; i < N; i++) { 00369 SBMin[i] = KeyDesc[i].Min; 00370 SBMax[i] = KeyDesc[i].Max; 00371 LBMin[i] = KeyDesc[i].Min; 00372 LBMax[i] = KeyDesc[i].Max; 00373 } 00374 00375 if (Tree->Root.Left != NULL) { 00376 if (setjmp (QuickExit) == 0) 00377 Search (0, Tree->Root.Left); 00378 } 00379 return (NumberOfNeighbors); 00380 } /* KDNearestNeighborSearch */
Stores Data in the K-D tree specified by Tree using Key as an access key.
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 156 of file kdtree.cpp.
References kdnode::BranchPoint, KeyDesc, KDTREE::KeyDesc, KDTREE::KeySize, kdnode::Left, kdnode::LeftBranch, MakeKDNode(), N, NULL, kdnode::Right, kdnode::RightBranch, KDTREE::Root, and Tree.
Referenced by MakeNewCluster(), and MakeSample().
00156 { 00157 int Level; 00158 KDNODE *Node; 00159 KDNODE **PtrToNode; 00160 00161 N = Tree->KeySize; 00162 KeyDesc = &(Tree->KeyDesc[0]); 00163 PtrToNode = &(Tree->Root.Left); 00164 Node = *PtrToNode; 00165 Level = 0; 00166 while (Node != NULL) { 00167 if (Key[Level] < Node->BranchPoint) { 00168 PtrToNode = &(Node->Left); 00169 if (Key[Level] > Node->LeftBranch) 00170 Node->LeftBranch = Key[Level]; 00171 } 00172 else { 00173 PtrToNode = &(Node->Right); 00174 if (Key[Level] < Node->RightBranch) 00175 Node->RightBranch = Key[Level]; 00176 } 00177 Level++; 00178 if (Level >= N) 00179 Level = 0; 00180 Node = *PtrToNode; 00181 } 00182 00183 *PtrToNode = MakeKDNode (Key, (char *) Data, Level); 00184 } /* KDStore */
Stores the desired action in a global variable and starts a recursive walk of Tree, starting at the root node.
Tree | Ptr to K-D tree to be walked | |
Action | Ptr to function to be executed at each node |
Definition at line 395 of file kdtree.cpp.
References kdnode::Left, NULL, KDTREE::Root, Tree, Walk(), and WalkAction.
Referenced by CreateClusterTree().
00395 { 00396 WalkAction = Action; 00397 if (Tree->Root.Left != NULL) 00398 Walk (Tree->Root.Left, 0); 00399 } /* KDWalk */
Allocates memory for a new K-D tree node and places the specified Key and Data into it.
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 |
Definition at line 465 of file kdtree.cpp.
References kdnode::BranchPoint, kdnode::Data, Emalloc(), kdnode::Key, KeyDesc, kdnode::Left, kdnode::LeftBranch, PARAM_DESC::Max, PARAM_DESC::Min, NULL, kdnode::Right, and kdnode::RightBranch.
Referenced by KDStore().
00465 { 00466 KDNODE *NewNode; 00467 00468 NewNode = (KDNODE *) Emalloc (sizeof (KDNODE)); 00469 00470 NewNode->Key = Key; 00471 NewNode->Data = Data; 00472 NewNode->BranchPoint = Key[Index]; 00473 NewNode->LeftBranch = KeyDesc[Index].Min; 00474 NewNode->RightBranch = KeyDesc[Index].Max; 00475 NewNode->Left = NULL; 00476 NewNode->Right = NULL; 00477 00478 return (NewNode); 00479 } /* MakeKDNode */
KDTREE* MakeKDTree | ( | INT16 | KeySize, | |
PARAM_DESC | KeyDesc[] | |||
) |
Allocates and returns a new K-D tree data structure.
KeySize | number of dimensions in the K-D tree | |
KeyDesc | Array of params to describe key dimensions |
Definition at line 94 of file kdtree.cpp.
References PARAM_DESC::Circular, Emalloc(), PARAM_DESC::HalfRange, KDTREE::KeyDesc, KeyDesc, KDTREE::KeySize, LBMax, LBMin, kdnode::Left, PARAM_DESC::Max, MaxDimension, MAXSEARCH, memfree(), PARAM_DESC::MidRange, PARAM_DESC::Min, MINSEARCH, PARAM_DESC::NonEssential, NULL, PARAM_DESC::Range, kdnode::Right, KDTREE::Root, SBMax, and SBMin.
Referenced by MakeClusterer().
00094 { 00095 int i; 00096 void *NewMemory; 00097 KDTREE *KDTree; 00098 00099 if (KeySize > MaxDimension) { 00100 NewMemory = Emalloc (KeySize * 4 * sizeof (FLOAT32)); 00101 if (MaxDimension > 0) { 00102 memfree ((char *) SBMin); 00103 memfree ((char *) SBMax); 00104 memfree ((char *) LBMin); 00105 memfree ((char *) LBMax); 00106 } 00107 SBMin = (FLOAT32 *) NewMemory; 00108 SBMax = SBMin + KeySize; 00109 LBMin = SBMax + KeySize; 00110 LBMax = LBMin + KeySize; 00111 } 00112 00113 KDTree = 00114 (KDTREE *) Emalloc (sizeof (KDTREE) + 00115 (KeySize - 1) * sizeof (PARAM_DESC)); 00116 for (i = 0; i < KeySize; i++) { 00117 KDTree->KeyDesc[i].NonEssential = KeyDesc[i].NonEssential; 00118 KDTree->KeyDesc[i].Circular = KeyDesc[i].Circular; 00119 if (KeyDesc[i].Circular) { 00120 KDTree->KeyDesc[i].Min = KeyDesc[i].Min; 00121 KDTree->KeyDesc[i].Max = KeyDesc[i].Max; 00122 KDTree->KeyDesc[i].Range = KeyDesc[i].Max - KeyDesc[i].Min; 00123 KDTree->KeyDesc[i].HalfRange = KDTree->KeyDesc[i].Range / 2; 00124 KDTree->KeyDesc[i].MidRange = (KeyDesc[i].Max + KeyDesc[i].Min) / 2; 00125 } 00126 else { 00127 KDTree->KeyDesc[i].Min = MINSEARCH; 00128 KDTree->KeyDesc[i].Max = MAXSEARCH; 00129 } 00130 } 00131 KDTree->KeySize = KeySize; 00132 KDTree->Root.Left = NULL; 00133 KDTree->Root.Right = NULL; 00134 return (KDTree); 00135 } /* MakeKDTree */
int QueryInSearch | ( | ) |
Determines if current query region is totally contained in current largest search region.
None |
The query region is the circle of radius Radius centered at QueryPoint. The search region is the box (in N dimensions) whose edges in each dimension are specified by LBMin and LBMax.
Definition at line 758 of file kdtree.cpp.
References FALSE, KeyDesc, LBMax, LBMin, N, QueryPoint, Radius, and TRUE.
Referenced by Search().
00758 { 00759 register int i; 00760 register FLOAT32 *Query; 00761 register FLOAT32 *Lower; 00762 register FLOAT32 *Upper; 00763 register PARAM_DESC *Dim; 00764 00765 Query = QueryPoint; 00766 Lower = LBMin; 00767 Upper = LBMax; 00768 Dim = KeyDesc; 00769 00770 for (i = N - 1; i >= 0; i--, Dim++, Query++, Lower++, Upper++) { 00771 if (Dim->NonEssential) 00772 continue; 00773 00774 if ((*Query < *Lower + Radius) || (*Query > *Upper - Radius)) 00775 return (FALSE); 00776 } 00777 return (TRUE); 00778 } /* QueryInSearch */
int QueryIntersectsSearch | ( | ) |
Determines if query region intersects current smallest search region.
None |
In the case of circular dimensions, we must also check the point which is one wrap-distance away from the query to see if it would intersect the search region.
Definition at line 685 of file kdtree.cpp.
References FALSE, KeyDesc, PARAM_DESC::Max, MAX_FLOAT32, MIN, N, QueryPoint, Radius, SBMax, and SBMin.
Referenced by Search().
00685 { 00686 register int i; 00687 register FLOAT32 *Query; 00688 register FLOAT32 *Lower; 00689 register FLOAT32 *Upper; 00690 register FLOAT64 TotalDistance; 00691 register FLOAT32 DimensionDistance; 00692 register FLOAT64 RadiusSquared; 00693 register PARAM_DESC *Dim; 00694 register FLOAT32 WrapDistance; 00695 00696 RadiusSquared = Radius * Radius; 00697 Query = QueryPoint; 00698 Lower = SBMin; 00699 Upper = SBMax; 00700 TotalDistance = 0.0; 00701 Dim = KeyDesc; 00702 for (i = N; i > 0; i--, Dim++, Query++, Lower++, Upper++) { 00703 if (Dim->NonEssential) 00704 continue; 00705 00706 if (*Query < *Lower) 00707 DimensionDistance = *Lower - *Query; 00708 else if (*Query > *Upper) 00709 DimensionDistance = *Query - *Upper; 00710 else 00711 DimensionDistance = 0; 00712 00714 if (Dim->Circular) { 00715 if (*Query < *Lower) 00716 WrapDistance = *Query + Dim->Max - Dim->Min - *Upper; 00717 else if (*Query > *Upper) 00718 WrapDistance = *Lower - (*Query - (Dim->Max - Dim->Min)); 00719 else 00720 WrapDistance = MAX_FLOAT32; 00721 00722 DimensionDistance = MIN (DimensionDistance, WrapDistance); 00723 } 00724 00725 TotalDistance += DimensionDistance * DimensionDistance; 00726 if (TotalDistance >= RadiusSquared) 00727 return (FALSE); 00728 } 00729 return (TRUE); 00730 } /* QueryIntersectsSearch */
void Search | ( | int | Level, | |
KDNODE * | SubTree | |||
) |
Searches SubTree for those entries which are possibly among the MaxNeighbors nearest neighbors of the QueryPoint and places their data in the Neighbor buffer and their distances from QueryPoint in the Distance buffer.
Level | level in tree of sub-tree to be searched | |
SubTree | sub-tree to be searched |
Definition at line 525 of file kdtree.cpp.
References kdnode::BranchPoint, ComputeDistance(), kdnode::Data, Distance, FindMaxDistance(), Furthest, kdnode::Key, KeyDesc, LBMax, LBMin, kdnode::Left, kdnode::LeftBranch, MaxNeighbors, N, Neighbor, NULL, NumberOfNeighbors, QueryInSearch(), QueryIntersectsSearch(), QueryPoint, QuickExit, Radius, kdnode::Right, kdnode::RightBranch, SBMax, SBMin, and Search().
Referenced by KDNearestNeighborSearch(), and Search().
00525 { 00526 FLOAT32 d; 00527 FLOAT32 OldSBoxEdge; 00528 FLOAT32 OldLBoxEdge; 00529 00530 if (Level >= N) 00531 Level = 0; 00532 00533 d = ComputeDistance (N, KeyDesc, QueryPoint, SubTree->Key); 00534 if (d < Radius) { 00535 if (NumberOfNeighbors < MaxNeighbors) { 00536 Neighbor[NumberOfNeighbors] = SubTree->Data; 00537 Distance[NumberOfNeighbors] = d; 00538 NumberOfNeighbors++; 00539 if (NumberOfNeighbors == MaxNeighbors) 00540 FindMaxDistance(); 00541 } 00542 else { 00543 Neighbor[Furthest] = SubTree->Data; 00544 Distance[Furthest] = d; 00545 FindMaxDistance(); 00546 } 00547 } 00548 if (QueryPoint[Level] < SubTree->BranchPoint) { 00549 OldSBoxEdge = SBMax[Level]; 00550 SBMax[Level] = SubTree->LeftBranch; 00551 OldLBoxEdge = LBMax[Level]; 00552 LBMax[Level] = SubTree->RightBranch; 00553 if (SubTree->Left != NULL) 00554 Search (Level + 1, SubTree->Left); 00555 SBMax[Level] = OldSBoxEdge; 00556 LBMax[Level] = OldLBoxEdge; 00557 OldSBoxEdge = SBMin[Level]; 00558 SBMin[Level] = SubTree->RightBranch; 00559 OldLBoxEdge = LBMin[Level]; 00560 LBMin[Level] = SubTree->LeftBranch; 00561 if ((SubTree->Right != NULL) && QueryIntersectsSearch ()) 00562 Search (Level + 1, SubTree->Right); 00563 SBMin[Level] = OldSBoxEdge; 00564 LBMin[Level] = OldLBoxEdge; 00565 } 00566 else { 00567 OldSBoxEdge = SBMin[Level]; 00568 SBMin[Level] = SubTree->RightBranch; 00569 OldLBoxEdge = LBMin[Level]; 00570 LBMin[Level] = SubTree->LeftBranch; 00571 if (SubTree->Right != NULL) 00572 Search (Level + 1, SubTree->Right); 00573 SBMin[Level] = OldSBoxEdge; 00574 LBMin[Level] = OldLBoxEdge; 00575 OldSBoxEdge = SBMax[Level]; 00576 SBMax[Level] = SubTree->LeftBranch; 00577 OldLBoxEdge = LBMax[Level]; 00578 LBMax[Level] = SubTree->RightBranch; 00579 if ((SubTree->Left != NULL) && QueryIntersectsSearch ()) 00580 Search (Level + 1, SubTree->Left); 00581 SBMax[Level] = OldSBoxEdge; 00582 LBMax[Level] = OldLBoxEdge; 00583 } 00584 if (QueryInSearch ()) 00585 longjmp (QuickExit, 1); 00586 } /* Search */
Walks thru the specified SubTree and invokes WalkAction at each node.
SubTree | ptr to root of subtree to be walked | |
Level | current level in the tree for this node |
Definition at line 802 of file kdtree.cpp.
References kdnode::Data, endorder, leaf, kdnode::Left, NULL, postorder, preorder, kdnode::Right, and Walk().
Referenced by KDWalk(), and Walk().
00802 { 00803 if ((SubTree->Left == NULL) && (SubTree->Right == NULL)) 00804 (*WalkAction) (SubTree->Data, leaf, Level); 00805 else { 00806 (*WalkAction) (SubTree->Data, preorder, Level); 00807 if (SubTree->Left != NULL) 00808 Walk (SubTree->Left, Level + 1); 00809 (*WalkAction) (SubTree->Data, postorder, Level); 00810 if (SubTree->Right != NULL) 00811 Walk (SubTree->Right, Level + 1); 00812 (*WalkAction) (SubTree->Data, endorder, Level); 00813 } 00814 } /* Walk */
Definition at line 53 of file kdtree.cpp.
Referenced by ComputeStatistics(), FindMaxDistance(), KDNearestNeighborSearch(), NormalDensity(), Search(), and SubfeatureEvidence().
int Furthest [static] |
Definition at line 51 of file kdtree.cpp.
Referenced by FindMaxDistance(), KDNearestNeighborSearch(), and Search().
PARAM_DESC* KeyDesc [static] |
Definition at line 61 of file kdtree.cpp.
Referenced by KDDelete(), KDNearestNeighborSearch(), KDStore(), MakeKDNode(), MakeKDTree(), QueryInSearch(), QueryIntersectsSearch(), and Search().
Definition at line 59 of file kdtree.cpp.
Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryInSearch(), and Search().
Definition at line 58 of file kdtree.cpp.
Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryInSearch(), and Search().
int MaxDimension = 0 [static] |
int MaxNeighbors [static] |
Definition at line 49 of file kdtree.cpp.
Referenced by FindMaxDistance(), KDNearestNeighborSearch(), and Search().
Dimensions in KD tree
Definition at line 46 of file kdtree.cpp.
Referenced by ChiArea(), Equal(), KDDelete(), KDNearestNeighborSearch(), KDStore(), NumberOfProtos(), QueryInSearch(), QueryIntersectsSearch(), Search(), SetUpForClustering(), TestEllipticalProto(), and WriteNormProtos().
char** Neighbor [static] |
Definition at line 52 of file kdtree.cpp.
Referenced by FindNearestNeighbor(), KDNearestNeighborSearch(), MakePotentialClusters(), and Search().
int NumberOfNeighbors [static] |
Definition at line 44 of file kdtree.cpp.
Referenced by FindNearestNeighbor(), KDNearestNeighborSearch(), and Search().
FLOAT32* QueryPoint [static] |
Definition at line 48 of file kdtree.cpp.
Referenced by KDNearestNeighborSearch(), QueryInSearch(), QueryIntersectsSearch(), and Search().
jmp_buf QuickExit [static] |
Definition at line 50 of file kdtree.cpp.
Referenced by FindMaxDistance(), KDNearestNeighborSearch(), QueryInSearch(), QueryIntersectsSearch(), and Search().
Definition at line 57 of file kdtree.cpp.
Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryIntersectsSearch(), and Search().
Definition at line 56 of file kdtree.cpp.
Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryIntersectsSearch(), and Search().
void_proc WalkAction [static] |