tesseract  3.04.00
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
kdtree.h File Reference
#include "host.h"
#include "cutil.h"
#include "ocrfeatures.h"

Go to the source code of this file.

Classes

struct  KDNODE
 
struct  KDTREE
 

Macros

#define RootOf(T)   ((T)->Root.Left->Data)
 

Functions

KDTREEMakeKDTree (inT16 KeySize, const PARAM_DESC KeyDesc[])
 
void KDStore (KDTREE *Tree, FLOAT32 *Key, void *Data)
 
void KDDelete (KDTREE *Tree, FLOAT32 Key[], void *Data)
 
void KDNearestNeighborSearch (KDTREE *Tree, FLOAT32 Query[], int QuerySize, FLOAT32 MaxDistance, int *NumberOfResults, void **NBuffer, FLOAT32 DBuffer[])
 
void KDWalk (KDTREE *Tree, void_proc Action, void *context)
 
void FreeKDTree (KDTREE *Tree)
 
KDNODEMakeKDNode (KDTREE *tree, FLOAT32 Key[], void *Data, int Index)
 
void FreeKDNode (KDNODE *Node)
 
FLOAT32 DistanceSquared (int k, PARAM_DESC *dim, FLOAT32 p1[], FLOAT32 p2[])
 
FLOAT32 ComputeDistance (int k, PARAM_DESC *dim, FLOAT32 p1[], FLOAT32 p2[])
 
int QueryInSearch (KDTREE *tree)
 
void Walk (KDTREE *tree, void_proc action, void *context, KDNODE *SubTree, inT32 Level)
 
void InsertNodes (KDTREE *tree, KDNODE *nodes)
 
void FreeSubTree (KDNODE *SubTree)
 

Macro Definition Documentation

#define RootOf (   T)    ((T)->Root.Left->Data)

Definition at line 58 of file kdtree.h.

Function Documentation

FLOAT32 ComputeDistance ( int  k,
PARAM_DESC dim,
FLOAT32  p1[],
FLOAT32  p2[] 
)

Definition at line 486 of file kdtree.cpp.

486  {
487  return sqrt(DistanceSquared(k, dim, p1, p2));
488 }
FLOAT32 DistanceSquared(int k, PARAM_DESC *dim, FLOAT32 p1[], FLOAT32 p2[])
Definition: kdtree.cpp:465
FLOAT32 DistanceSquared ( int  k,
PARAM_DESC dim,
FLOAT32  p1[],
FLOAT32  p2[] 
)

Definition at line 465 of file kdtree.cpp.

465  {
466  FLOAT32 total_distance = 0;
467 
468  for (; k > 0; k--, p1++, p2++, dim++) {
469  if (dim->NonEssential)
470  continue;
471 
472  FLOAT32 dimension_distance = *p1 - *p2;
473 
474  /* if this dimension is circular - check wraparound distance */
475  if (dim->Circular) {
476  dimension_distance = Magnitude(dimension_distance);
477  FLOAT32 wrap_distance = dim->Max - dim->Min - dimension_distance;
478  dimension_distance = MIN(dimension_distance, wrap_distance);
479  }
480 
481  total_distance += dimension_distance * dimension_distance;
482  }
483  return total_distance;
484 }
FLOAT32 Min
Definition: ocrfeatures.h:49
float FLOAT32
Definition: host.h:111
#define MIN(x, y)
Definition: ndminx.h:28
inT8 NonEssential
Definition: ocrfeatures.h:48
inT8 Circular
Definition: ocrfeatures.h:47
FLOAT32 Max
Definition: ocrfeatures.h:50
#define Magnitude(X)
Definition: kdtree.cpp:31
void FreeKDNode ( KDNODE Node)

Definition at line 407 of file kdtree.cpp.

407  {
408  memfree ((char *)Node);
409 }
void memfree(void *element)
Definition: freelist.cpp:30
void FreeKDTree ( KDTREE Tree)

Definition at line 346 of file kdtree.cpp.

346  {
347 /*
348  ** Parameters:
349  ** Tree tree data structure to be released
350  ** Operation:
351  ** This routine frees all memory which is allocated to the
352  ** specified KD-tree. This includes the data structure for
353  ** the kd-tree itself plus the data structures for each node
354  ** in the tree. It does not include the Key and Data items
355  ** which are pointed to by the nodes. This memory is left
356  ** untouched.
357  ** Return: none
358  ** Exceptions: none
359  ** History:
360  ** 5/26/89, DSJ, Created.
361  */
362  FreeSubTree(Tree->Root.Left);
363  memfree(Tree);
364 } /* FreeKDTree */
KDNODE Root
Definition: kdtree.h:51
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:568
struct KDNODE * Left
Definition: kdtree.h:45
void memfree(void *element)
Definition: freelist.cpp:30
void FreeSubTree ( KDNODE SubTree)

Definition at line 568 of file kdtree.cpp.

568  {
569  if (sub_tree != NULL) {
570  FreeSubTree(sub_tree->Left);
571  FreeSubTree(sub_tree->Right);
572  memfree(sub_tree);
573  }
574 } /* FreeSubTree */
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:568
void memfree(void *element)
Definition: freelist.cpp:30
#define NULL
Definition: host.h:144
void InsertNodes ( KDTREE tree,
KDNODE nodes 
)

Definition at line 558 of file kdtree.cpp.

558  {
559  if (nodes == NULL)
560  return;
561 
562  KDStore(tree, nodes->Key, nodes->Data);
563  InsertNodes(tree, nodes->Left);
564  InsertNodes(tree, nodes->Right);
565 }
struct KDNODE * Left
Definition: kdtree.h:45
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:558
struct KDNODE * Right
Definition: kdtree.h:46
void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data)
Definition: kdtree.cpp:209
#define NULL
Definition: host.h:144
void * Data
Definition: kdtree.h:41
FLOAT32 * Key
Definition: kdtree.h:40
void KDDelete ( KDTREE Tree,
FLOAT32  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
TreeK-D tree to delete node from
Keykey of node to be deleted
Datadata contents of node to be deleted
Note
Exceptions: none
History: 3/13/89, DSJ, Created. 7/13/89, DSJ, Specify node indirectly by key and data.

Definition at line 269 of file kdtree.cpp.

269  {
270  int Level;
271  KDNODE *Current;
272  KDNODE *Father;
273 
274  /* initialize search at root of tree */
275  Father = &(Tree->Root);
276  Current = Father->Left;
277  Level = NextLevel(Tree, -1);
278 
279  /* search tree for node to be deleted */
280  while ((Current != NULL) && (!NodeFound (Current, Key, Data))) {
281  Father = Current;
282  if (Key[Level] < Current->BranchPoint)
283  Current = Current->Left;
284  else
285  Current = Current->Right;
286 
287  Level = NextLevel(Tree, Level);
288  }
289 
290  if (Current != NULL) { /* if node to be deleted was found */
291  if (Current == Father->Left) {
292  Father->Left = NULL;
293  Father->LeftBranch = Tree->KeyDesc[Level].Min;
294  } else {
295  Father->Right = NULL;
296  Father->RightBranch = Tree->KeyDesc[Level].Max;
297  }
298 
299  InsertNodes(Tree, Current->Left);
300  InsertNodes(Tree, Current->Right);
301  FreeSubTree(Current);
302  }
303 } /* KDDelete */
FLOAT32 RightBranch
Definition: kdtree.h:44
FLOAT32 Min
Definition: ocrfeatures.h:49
#define NodeFound(N, K, D)
Definition: kdtree.cpp:32
KDNODE Root
Definition: kdtree.h:51
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:52
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:568
struct KDNODE * Left
Definition: kdtree.h:45
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:558
struct KDNODE * Right
Definition: kdtree.h:46
Definition: kdtree.h:39
FLOAT32 LeftBranch
Definition: kdtree.h:43
#define NULL
Definition: host.h:144
FLOAT32 BranchPoint
Definition: kdtree.h:42
FLOAT32 Max
Definition: ocrfeatures.h:50
void KDNearestNeighborSearch ( KDTREE Tree,
FLOAT32  Query[],
int  QuerySize,
FLOAT32  MaxDistance,
int *  NumberOfResults,
void **  NBuffer,
FLOAT32  DBuffer[] 
)

Definition at line 307 of file kdtree.cpp.

309  {
310 /*
311  ** Parameters:
312  ** Tree ptr to K-D tree to be searched
313  ** Query ptr to query key (point in D-space)
314  ** QuerySize number of nearest neighbors to be found
315  ** MaxDistance all neighbors must be within this distance
316  ** NBuffer ptr to QuerySize buffer to hold nearest neighbors
317  ** DBuffer ptr to QuerySize buffer to hold distances
318  ** from nearest neighbor to query point
319  ** Operation:
320  ** This routine searches the K-D tree specified by Tree and
321  ** finds the QuerySize nearest neighbors of Query. All neighbors
322  ** must be within MaxDistance of Query. The data contents of
323  ** the nearest neighbors
324  ** are placed in NBuffer and their distances from Query are
325  ** placed in DBuffer.
326  ** Return: Number of nearest neighbors actually found
327  ** Exceptions: none
328  ** History:
329  ** 3/10/89, DSJ, Created.
330  ** 7/13/89, DSJ, Return contents of node instead of node itself.
331  */
332  KDTreeSearch search(Tree, Query, QuerySize);
333  search.Search(NumberOfResults, DBuffer, NBuffer);
334 }
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:413
void KDStore ( KDTREE Tree,
FLOAT32 Key,
void *  Data 
)

This routine stores Data in the K-D tree specified by Tree using Key as an access key.

Parameters
TreeK-D tree in which data is to be stored
Keyptr to key by which data can be retrieved
Dataptr to data to be stored in the tree
Note
Exceptions: none
History: 3/10/89, DSJ, Created. 7/13/89, DSJ, Changed return to void.

Definition at line 209 of file kdtree.cpp.

209  {
222  int Level;
223  KDNODE *Node;
224  KDNODE **PtrToNode;
225 
226  PtrToNode = &(Tree->Root.Left);
227  Node = *PtrToNode;
228  Level = NextLevel(Tree, -1);
229  while (Node != NULL) {
230  if (Key[Level] < Node->BranchPoint) {
231  PtrToNode = &(Node->Left);
232  if (Key[Level] > Node->LeftBranch)
233  Node->LeftBranch = Key[Level];
234  }
235  else {
236  PtrToNode = &(Node->Right);
237  if (Key[Level] < Node->RightBranch)
238  Node->RightBranch = Key[Level];
239  }
240  Level = NextLevel(Tree, Level);
241  Node = *PtrToNode;
242  }
243 
244  *PtrToNode = MakeKDNode(Tree, Key, (void *) Data, Level);
245 } /* KDStore */
FLOAT32 RightBranch
Definition: kdtree.h:44
KDNODE * MakeKDNode(KDTREE *tree, FLOAT32 Key[], void *Data, int Index)
Definition: kdtree.cpp:371
KDNODE Root
Definition: kdtree.h:51
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
Definition: kdtree.h:39
FLOAT32 LeftBranch
Definition: kdtree.h:43
#define NULL
Definition: host.h:144
FLOAT32 BranchPoint
Definition: kdtree.h:42
void KDWalk ( KDTREE Tree,
void_proc  Action,
void *  context 
)

Definition at line 339 of file kdtree.cpp.

339  {
340  if (Tree->Root.Left != NULL)
341  Walk(Tree, action, context, Tree->Root.Left, NextLevel(Tree, -1));
342 }
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, inT32 level)
Definition: kdtree.cpp:547
KDNODE Root
Definition: kdtree.h:51
struct KDNODE * Left
Definition: kdtree.h:45
#define NULL
Definition: host.h:144
KDNODE* MakeKDNode ( KDTREE tree,
FLOAT32  Key[],
void *  Data,
int  Index 
)

Definition at line 371 of file kdtree.cpp.

371  {
372 /*
373  ** Parameters:
374  ** tree The tree to create the node for
375  ** Key Access key for new node in KD tree
376  ** Data ptr to data to be stored in new node
377  ** Index index of Key to branch on
378  ** Operation:
379  ** This routine allocates memory for a new K-D tree node
380  ** and places the specified Key and Data into it. The
381  ** left and right subtree pointers for the node are
382  ** initialized to empty subtrees.
383  ** Return:
384  ** pointer to new K-D tree node
385  ** Exceptions:
386  ** None
387  ** History:
388  ** 3/11/89, DSJ, Created.
389  */
390  KDNODE *NewNode;
391 
392  NewNode = (KDNODE *) Emalloc (sizeof (KDNODE));
393 
394  NewNode->Key = Key;
395  NewNode->Data = Data;
396  NewNode->BranchPoint = Key[Index];
397  NewNode->LeftBranch = tree->KeyDesc[Index].Min;
398  NewNode->RightBranch = tree->KeyDesc[Index].Max;
399  NewNode->Left = NULL;
400  NewNode->Right = NULL;
401 
402  return NewNode;
403 } /* MakeKDNode */
FLOAT32 RightBranch
Definition: kdtree.h:44
FLOAT32 Min
Definition: ocrfeatures.h:49
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:52
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
Definition: kdtree.h:39
void * Emalloc(int Size)
Definition: emalloc.cpp:35
FLOAT32 LeftBranch
Definition: kdtree.h:43
#define NULL
Definition: host.h:144
void * Data
Definition: kdtree.h:41
FLOAT32 * Key
Definition: kdtree.h:40
FLOAT32 BranchPoint
Definition: kdtree.h:42
FLOAT32 Max
Definition: ocrfeatures.h:50
KDTREE* MakeKDTree ( inT16  KeySize,
const PARAM_DESC  KeyDesc[] 
)

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

184  {
185  KDTREE *KDTree = (KDTREE *) Emalloc(
186  sizeof(KDTREE) + (KeySize - 1) * sizeof(PARAM_DESC));
187  for (int i = 0; i < KeySize; i++) {
188  KDTree->KeyDesc[i].NonEssential = KeyDesc[i].NonEssential;
189  KDTree->KeyDesc[i].Circular = KeyDesc[i].Circular;
190  if (KeyDesc[i].Circular) {
191  KDTree->KeyDesc[i].Min = KeyDesc[i].Min;
192  KDTree->KeyDesc[i].Max = KeyDesc[i].Max;
193  KDTree->KeyDesc[i].Range = KeyDesc[i].Max - KeyDesc[i].Min;
194  KDTree->KeyDesc[i].HalfRange = KDTree->KeyDesc[i].Range / 2;
195  KDTree->KeyDesc[i].MidRange = (KeyDesc[i].Max + KeyDesc[i].Min) / 2;
196  } else {
197  KDTree->KeyDesc[i].Min = MINSEARCH;
198  KDTree->KeyDesc[i].Max = MAXSEARCH;
199  }
200  }
201  KDTree->KeySize = KeySize;
202  KDTree->Root.Left = NULL;
203  KDTree->Root.Right = NULL;
204  return KDTree;
205 }
FLOAT32 Min
Definition: ocrfeatures.h:49
Definition: kdtree.h:49
inT16 KeySize
Definition: kdtree.h:50
KDNODE Root
Definition: kdtree.h:51
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:52
FLOAT32 HalfRange
Definition: ocrfeatures.h:52
struct KDNODE * Left
Definition: kdtree.h:45
#define MINSEARCH
Definition: kdtree.cpp:37
FLOAT32 MidRange
Definition: ocrfeatures.h:53
struct KDNODE * Right
Definition: kdtree.h:46
inT8 NonEssential
Definition: ocrfeatures.h:48
inT8 Circular
Definition: ocrfeatures.h:47
void * Emalloc(int Size)
Definition: emalloc.cpp:35
FLOAT32 Range
Definition: ocrfeatures.h:51
#define MAXSEARCH
Definition: kdtree.cpp:38
#define NULL
Definition: host.h:144
FLOAT32 Max
Definition: ocrfeatures.h:50
int QueryInSearch ( KDTREE tree)
void Walk ( KDTREE tree,
void_proc  action,
void *  context,
KDNODE SubTree,
inT32  Level 
)

Definition at line 547 of file kdtree.cpp.

548  {
549  (*action)(context, sub_tree->Data, level);
550  if (sub_tree->Left != NULL)
551  Walk(tree, action, context, sub_tree->Left, NextLevel(tree, level));
552  if (sub_tree->Right != NULL)
553  Walk(tree, action, context, sub_tree->Right, NextLevel(tree, level));
554 }
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, inT32 level)
Definition: kdtree.cpp:547
#define NULL
Definition: host.h:144