tesseract  3.04.00
kdtree.cpp File Reference
#include "kdtree.h"
#include "const.h"
#include "emalloc.h"
#include "freelist.h"
#include <stdio.h>
#include <math.h>

Go to the source code of this file.

Classes

class  MinK< Key, Value >
 
struct  MinK< Key, Value >::Element
 
class  KDTreeSearch
 

Macros

#define Magnitude(X)    ((X) < 0 ? -(X) : (X))
 
#define NodeFound(N, K, D)   (( (N)->Key == (K) ) && ( (N)->Data == (D) ))
 
#define MINSEARCH   -MAX_FLOAT32
 
#define MAXSEARCH   MAX_FLOAT32
 

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[])
 
void Walk (KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, inT32 level)
 
void InsertNodes (KDTREE *tree, KDNODE *nodes)
 
void FreeSubTree (KDNODE *sub_tree)
 

Macro Definition Documentation

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

Definition at line 31 of file kdtree.cpp.

#define MAXSEARCH   MAX_FLOAT32

Definition at line 38 of file kdtree.cpp.

#define MINSEARCH   -MAX_FLOAT32

Definition at line 37 of file kdtree.cpp.

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

Definition at line 32 of file kdtree.cpp.

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 }
#define MIN(x, y)
Definition: ndminx.h:28
#define Magnitude(X)
Definition: kdtree.cpp:31
inT8 NonEssential
Definition: ocrfeatures.h:48
inT8 Circular
Definition: ocrfeatures.h:47
FLOAT32 Min
Definition: ocrfeatures.h:49
FLOAT32 Max
Definition: ocrfeatures.h:50
float FLOAT32
Definition: host.h:111
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 */
struct KDNODE * Left
Definition: kdtree.h:45
KDNODE Root
Definition: kdtree.h:51
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:568
void memfree(void *element)
Definition: freelist.cpp:30
void FreeSubTree ( KDNODE sub_tree)

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 */
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
#define NULL
Definition: host.h:144
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:568
void memfree(void *element)
Definition: freelist.cpp:30
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 }
void * Data
Definition: kdtree.h:41
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
#define NULL
Definition: host.h:144
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:558
FLOAT32 * Key
Definition: kdtree.h:40
void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data)
Definition: kdtree.cpp:209
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 */
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
Definition: kdtree.h:39
#define NULL
Definition: host.h:144
KDNODE Root
Definition: kdtree.h:51
FLOAT32 BranchPoint
Definition: kdtree.h:42
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:568
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:558
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:52
FLOAT32 RightBranch
Definition: kdtree.h:44
FLOAT32 Min
Definition: ocrfeatures.h:49
FLOAT32 LeftBranch
Definition: kdtree.h:43
FLOAT32 Max
Definition: ocrfeatures.h:50
#define NodeFound(N, K, D)
Definition: kdtree.cpp:32
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 */
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
Definition: kdtree.h:39
#define NULL
Definition: host.h:144
KDNODE Root
Definition: kdtree.h:51
FLOAT32 BranchPoint
Definition: kdtree.h:42
KDNODE * MakeKDNode(KDTREE *tree, FLOAT32 Key[], void *Data, int Index)
Definition: kdtree.cpp:371
FLOAT32 RightBranch
Definition: kdtree.h:44
FLOAT32 LeftBranch
Definition: kdtree.h:43
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 }
struct KDNODE * Left
Definition: kdtree.h:45
#define NULL
Definition: host.h:144
KDNODE Root
Definition: kdtree.h:51
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, inT32 level)
Definition: kdtree.cpp:547
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 */
void * Data
Definition: kdtree.h:41
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
Definition: kdtree.h:39
#define NULL
Definition: host.h:144
FLOAT32 BranchPoint
Definition: kdtree.h:42
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:52
FLOAT32 * Key
Definition: kdtree.h:40
FLOAT32 RightBranch
Definition: kdtree.h:44
void * Emalloc(int Size)
Definition: emalloc.cpp:35
FLOAT32 Min
Definition: ocrfeatures.h:49
FLOAT32 LeftBranch
Definition: kdtree.h:43
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 }
#define MAXSEARCH
Definition: kdtree.cpp:38
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
#define NULL
Definition: host.h:144
KDNODE Root
Definition: kdtree.h:51
FLOAT32 HalfRange
Definition: ocrfeatures.h:52
FLOAT32 MidRange
Definition: ocrfeatures.h:53
inT16 KeySize
Definition: kdtree.h:50
#define MINSEARCH
Definition: kdtree.cpp:37
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:52
inT8 NonEssential
Definition: ocrfeatures.h:48
inT8 Circular
Definition: ocrfeatures.h:47
Definition: kdtree.h:49
void * Emalloc(int Size)
Definition: emalloc.cpp:35
FLOAT32 Range
Definition: ocrfeatures.h:51
FLOAT32 Min
Definition: ocrfeatures.h:49
FLOAT32 Max
Definition: ocrfeatures.h:50
void Walk ( KDTREE tree,
void_proc  action,
void *  context,
KDNODE sub_tree,
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 * Data
Definition: kdtree.h:41
struct KDNODE * Left
Definition: kdtree.h:45
struct KDNODE * Right
Definition: kdtree.h:46
#define NULL
Definition: host.h:144
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, inT32 level)
Definition: kdtree.cpp:547