classify/kdtree.cpp File Reference

#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.

Defines

Functions

Variables


Define Documentation

#define Magnitude (  )     ((X) < 0 ? -(X) : (X))

Note:
File: kdtree.cpp
Routines for managing K-D search trees
None of these functions are called by default
Author:
Dan Johnson
Date:
3/10/89, DSJ, Created. 5/23/89, DSJ, Added circular feature capability. 7/13/89, DSJ, Made tree nodes invisible to outside.
 **	(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

Definition at line 42 of file kdtree.cpp.

Referenced by MakeKDTree().

#define MIN ( A,
 )     ((A) < (B) ? (A) : (B))

Definition at line 35 of file kdtree.cpp.

#define MINSEARCH   -MAX_FLOAT32

Definition at line 41 of file kdtree.cpp.

Referenced by MakeKDTree().

#define NodeFound ( N,
K,
 )     (( (N)->Key == (K) ) && ( (N)->Data == (D) ))

Definition at line 36 of file kdtree.cpp.

Referenced by KDDelete().


Function Documentation

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.

Parameters:
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
Returns:
Distance between p1 and p2.
Note:
Exceptions: None
Date:
3/11/89, DSJ, Created.

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 */

int Equal ( FLOAT32  Key1[],
FLOAT32  Key2[] 
)

Compares values referenced by Key1 with that of Key2.

Parameters:
Key1 Search key to be compared for equality
Key2 Search key to be compared for equality
Note:
Globals: N number of parameters per key
Returns:
TRUE if Key1 = Key2
Note:
Exceptions: None
Date:
3/11/89, DSJ, Created.

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.

Parameters:
None 
Note:
Globals:
  • MaxNeighbors Maximum # of neighbors to find
  • Radius Current distance of furthest neighbor
  • Furthest Index of furthest neighbor
  • Distance Buffer of neighbor distances
Returns:
None
Note:
Exceptions: None
Date:
3/11/89, DSJ, Created.

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.

Parameters:
Node ptr to node data structure to be freed
Returns:
None
Note:
Exceptions: None
Date:
3/13/89, DSJ, Created.

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.

Parameters:
Tree tree data structure to be released
Returns:
none
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.

Note:
Exceptions: none
Date:
5/26/89, DSJ, Created.

Definition at line 418 of file kdtree.cpp.

References FreeSubTree(), kdnode::Left, memfree(), KDTREE::Root, and Tree.

Referenced by CreateClusterTree(), and FreeClusterer().

00418                               { 
00419   FreeSubTree (Tree->Root.Left);
00420   memfree(Tree); 
00421 }                                /* FreeKDTree */

void FreeSubTree ( KDNODE SubTree  ) 

Recursively frees the memory allocated to to the specified subtree.

Parameters:
SubTree ptr to root node of sub-tree to be freed
Note:
Globals: none
Returns:
none
Note:
Exceptions: none
Date:
7/13/89, DSJ, Created.

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 */

void KDDelete ( KDTREE Tree,
FLOAT32  Key[],
void *  Data 
)

Deletes a node from Tree.

Parameters:
Tree K-D tree to delete node from
Key key of node to be deleted
Data data contents of node to be deleted
Note:
Globals:
  • N dimension of the K-D tree
  • KeyDesc description of each dimension
  • DeleteCount debug variables for performance tests
  • DeleteProbeCount
Returns:
none
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 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.

Note:
Exceptions: none
Date:
3/13/89, DSJ, Created. 7/13/89, DSJ, Specify node indirectly by key and data.

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.

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
Note:
Globals:
  • NumberOfNeighbors # of neighbors found so far
  • N # of features in each key
  • KeyDesc description of tree dimensions
  • QueryPoint point in D-space to find neighbors of
  • MaxNeighbors maximum # of neighbors to find
  • Radius current distance of furthest neighbor
  • Furthest index of furthest neighbor
  • Neighbor buffer of current neighbors
  • Distance buffer of neighbor distances
  • SBMin lower extent of small search region
  • SBMax upper extent of small search region
  • LBMin lower extent of large search region
  • LBMax upper extent of large search region
  • QuickExit quick exit from recursive search
Returns:
Number of nearest neighbors actually found
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.
Note:
Exceptions: none
Date:
3/10/89, DSJ, Created. 7/13/89, DSJ, Return contents of node instead of node itself.

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 */

void KDStore ( KDTREE Tree,
FLOAT32 Key,
void *  Data 
)

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
Note:
Globals:
  • N dimension of the K-D tree
  • KeyDesc descriptions of tree dimensions
  • StoreCount debug variables for performance tests
  • StoreUniqueCount
  • StoreProbeCount
Returns:
none
Note:
Exceptions: none
Date:
3/10/89, DSJ, Created. 7/13/89, DSJ, Changed return to void.

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 */

void KDWalk ( KDTREE Tree,
void_proc  Action 
)

Stores the desired action in a global variable and starts a recursive walk of Tree, starting at the root node.

Parameters:
Tree Ptr to K-D tree to be walked
Action Ptr to function to be executed at each node
Note:
Globals: WalkAction action to be performed at every node
Returns:
None
Note:
Exceptions: None
Date:
3/13/89, DSJ, Created.

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 */

KDNODE* MakeKDNode ( FLOAT32  Key[],
char *  Data,
int  Index 
)

Allocates memory for a new K-D tree node and places the specified Key and Data into it.

Parameters:
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
Note:
Globals: KeyDesc descriptions of key dimensions
Returns:
pointer to new K-D tree node
The left and right subtree pointers for the node are initialized to empty subtrees.
Note:
Exceptions: None
Date:
3/11/89, DSJ, Created.

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.

Parameters:
KeySize number of dimensions in the K-D tree
KeyDesc Array of params to describe key dimensions
Note:
Globals:
  • MaxDimension Largest number of dimensions in any K-D tree
  • SBMin Small search region box
  • SBMax Small search region box
  • LBMin Large search region box
  • LBMax Large search region box
  • Key Description of key dimensions
Returns:
Pointer to new K-D tree
Routine also reallocates the small and large search region boxes if they are not large enough to accomodate the size of the new K-D tree. KeyDesc is an array of key descriptors that indicate which dimensions are circular and, if they are circular, what the range is.
Note:
Exceptions: None
Date:
3/13/89, DSJ, Created.

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.

Parameters:
None 
Note:
Globals:
  • N Number of features in each key
  • KeyDesc descriptions of each dimension
  • QueryPoint point in D-space to find neighbors of
  • Radius current distance of furthest neighbor
  • LBMin lower extent of large search region
  • LBMax upper extent of large search region
Returns:
TRUE if query region is inside search region, else FALSE
Returns TRUE if the current query region is totally contained in the current largest search region.

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.

Note:
Exceptions: None
Date:
3/11/89, DSJ, Created.

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.

Parameters:
None 
Note:
Globals:
  • N Number of features in each key
  • KeyDesc Descriptions of each dimension
  • QueryPoint Point in D-space to find neighbors of
  • Radius Current distance of furthest neighbor
  • SBMin Lower extent of small search region
  • SBMax Upper extent of small search region
Returns:
TRUE if query region intersects search region, else FALSE
Returns TRUE if the query region intersects the current smallest search region. The query region is the circle of radius Radius centered at QueryPoint. The smallest search region is the box (in N dimensions) whose edges in each dimension are specified by SBMin and SBMax.

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.

Note:
Exceptions: None
Date:
3/11/89, DSJ, Created.

Note:
if this dimension is circular - check wraparound distance

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.

Parameters:
Level level in tree of sub-tree to be searched
SubTree sub-tree to be searched
Note:
Globals:
  • NumberOfNeighbors # of neighbors found so far
  • N # of features in each key
  • KeyDesc description of key dimensions
  • QueryPoint point in D-space to find neighbors of
  • MaxNeighbors maximum # of neighbors to find
  • Radius current distance of furthest neighbor
  • Furthest index of furthest neighbor
  • Neighbor buffer of current neighbors
  • Distance buffer of neighbor distances
  • SBMin lower extent of small search region
  • SBMax upper extent of small search region
  • LBMin lower extent of large search region
  • LBMax upper extent of large search region
  • QuickExit quick exit from recursive search
Returns:
none
Note:
Exceptions: none
Date:
3/11/89, DSJ, Created. 7/13/89, DSJ, Save node contents, not node, in neighbor buffer

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 */

void Walk ( KDNODE SubTree,
INT32  Level 
)

Walks thru the specified SubTree and invokes WalkAction at each node.

Parameters:
SubTree ptr to root of subtree to be walked
Level current level in the tree for this node
Note:
Globals: WalkAction action to be performed at every node
Returns:
none
WalkAction is invoked with three arguments as follows:
See also:
WalkAction( NodeData, Order, Level )
NodeData is the data contents of the node being visited, Order is either preorder, postorder, endorder, or leaf depending on whether this is the 1st, 2nd, or 3rd time a node has been visited, or whether the node is a leaf. Level is the level of the node in the tree with the root being level 0.
Note:
Exceptions: none
Date:
3/13/89, DSJ, Created. 7/13/89, DSJ, Pass node contents, not node, to WalkAction().

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 */


Variable Documentation

FLOAT32* Distance [static]

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().

FLOAT32* LBMax [static]

Definition at line 59 of file kdtree.cpp.

Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryInSearch(), and Search().

FLOAT32* LBMin [static]

Definition at line 58 of file kdtree.cpp.

Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryInSearch(), and Search().

int MaxDimension = 0 [static]

Definition at line 55 of file kdtree.cpp.

Referenced by MakeKDTree().

int MaxNeighbors [static]

Definition at line 49 of file kdtree.cpp.

Referenced by FindMaxDistance(), KDNearestNeighborSearch(), and Search().

INT16 N [static]

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 63 of file kdtree.cpp.

Referenced by KDNearestNeighborSearch(), and Search().

FLOAT32 Radius [static]

Definition at line 50 of file kdtree.cpp.

Referenced by FindMaxDistance(), KDNearestNeighborSearch(), QueryInSearch(), QueryIntersectsSearch(), and Search().

FLOAT32* SBMax [static]

Definition at line 57 of file kdtree.cpp.

Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryIntersectsSearch(), and Search().

FLOAT32* SBMin [static]

Definition at line 56 of file kdtree.cpp.

Referenced by KDNearestNeighborSearch(), MakeKDTree(), QueryIntersectsSearch(), and Search().

void_proc WalkAction [static]

Definition at line 65 of file kdtree.cpp.

Referenced by KDWalk().


Generated on Wed Feb 28 19:49:20 2007 for Tesseract by  doxygen 1.5.1