tesseract  4.1.1
kdtree.cpp File Reference
#include "kdtree.h"
#include "emalloc.h"
#include <algorithm>
#include <cfloat>
#include <cstdio>
#include <cmath>

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   -FLT_MAX
 
#define MAXSEARCH   FLT_MAX
 

Functions

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

Macro Definition Documentation

◆ Magnitude

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

Definition at line 29 of file kdtree.cpp.

◆ MAXSEARCH

#define MAXSEARCH   FLT_MAX

Definition at line 36 of file kdtree.cpp.

◆ MINSEARCH

#define MINSEARCH   -FLT_MAX

Definition at line 35 of file kdtree.cpp.

◆ NodeFound

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

Definition at line 30 of file kdtree.cpp.

Function Documentation

◆ ComputeDistance()

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

Definition at line 448 of file kdtree.cpp.

448  {
449  return sqrt(DistanceSquared(k, dim, p1, p2));
450 }
float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[])
Definition: kdtree.cpp:427

◆ 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
kkeys are in k-space
dimdimension descriptions (essential, circular, etc)
p1,p2two different points in K-D space

Definition at line 427 of file kdtree.cpp.

427  {
428  float total_distance = 0;
429 
430  for (; k > 0; k--, p1++, p2++, dim++) {
431  if (dim->NonEssential)
432  continue;
433 
434  float dimension_distance = *p1 - *p2;
435 
436  /* if this dimension is circular - check wraparound distance */
437  if (dim->Circular) {
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);
441  }
442 
443  total_distance += dimension_distance * dimension_distance;
444  }
445  return total_distance;
446 }
#define Magnitude(X)
Definition: kdtree.cpp:29
bool Circular
Definition: ocrfeatures.h:43
float Max
Definition: ocrfeatures.h:46
bool NonEssential
Definition: ocrfeatures.h:44
float Min
Definition: ocrfeatures.h:45

◆ FreeKDNode()

void FreeKDNode ( KDNODE Node)

Definition at line 370 of file kdtree.cpp.

370 { free(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
Treetree data structure to be released

Definition at line 331 of file kdtree.cpp.

331  {
332  FreeSubTree(Tree->Root.Left);
333  free(Tree);
334 } /* FreeKDTree */
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:532
struct KDNODE * Left
Definition: kdtree.h:44
KDNODE Root
Definition: kdtree.h:50

◆ FreeSubTree()

void FreeSubTree ( KDNODE sub_tree)

Free all of the nodes of a sub tree.

Definition at line 532 of file kdtree.cpp.

532  {
533  if (sub_tree != nullptr) {
534  FreeSubTree(sub_tree->Left);
535  FreeSubTree(sub_tree->Right);
536  free(sub_tree);
537  }
538 }
struct KDNODE * Right
Definition: kdtree.h:45

◆ InsertNodes()

void InsertNodes ( KDTREE tree,
KDNODE nodes 
)

Given a subtree nodes, insert all of its elements into tree.

Definition at line 522 of file kdtree.cpp.

522  {
523  if (nodes == nullptr)
524  return;
525 
526  KDStore(tree, nodes->Key, nodes->Data);
527  InsertNodes(tree, nodes->Left);
528  InsertNodes(tree, nodes->Right);
529 }
void KDStore(KDTREE *Tree, float *Key, void *Data)
Definition: kdtree.cpp:212
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:522
float * Key
Definition: kdtree.h:39
void * Data
Definition: kdtree.h:40

◆ 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
TreeK-D tree to delete node from
Keykey of node to be deleted
Datadata contents of node to be deleted

Definition at line 253 of file kdtree.cpp.

253  {
254  int Level;
255  KDNODE *Current;
256  KDNODE *Father;
257 
258  /* initialize search at root of tree */
259  Father = &(Tree->Root);
260  Current = Father->Left;
261  Level = NextLevel(Tree, -1);
262 
263  /* search tree for node to be deleted */
264  while ((Current != nullptr) && (!NodeFound (Current, Key, Data))) {
265  Father = Current;
266  if (Key[Level] < Current->BranchPoint)
267  Current = Current->Left;
268  else
269  Current = Current->Right;
270 
271  Level = NextLevel(Tree, Level);
272  }
273 
274  if (Current != nullptr) { /* if node to be deleted was found */
275  if (Current == Father->Left) {
276  Father->Left = nullptr;
277  Father->LeftBranch = Tree->KeyDesc[Level].Min;
278  } else {
279  Father->Right = nullptr;
280  Father->RightBranch = Tree->KeyDesc[Level].Max;
281  }
282 
283  InsertNodes(Tree, Current->Left);
284  InsertNodes(Tree, Current->Right);
285  FreeSubTree(Current);
286  }
287 } /* KDDelete */
#define NodeFound(N, K, D)
Definition: kdtree.cpp:30
Definition: kdtree.h:38
float RightBranch
Definition: kdtree.h:43
float LeftBranch
Definition: kdtree.h:42
float BranchPoint
Definition: kdtree.h:41
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:51

◆ 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
Treeptr to K-D tree to be searched
Queryptr to query key (point in D-space)
QuerySizenumber of nearest neighbors to be found
MaxDistanceall neighbors must be within this distance
NBufferptr to QuerySize buffer to hold nearest neighbors
DBufferptr to QuerySize buffer to hold distances from nearest neighbor to query point
NumberOfResults[out] Number of nearest neighbors actually found

Definition at line 305 of file kdtree.cpp.

307  {
308  KDTreeSearch search(Tree, Query, QuerySize);
309  search.Search(NumberOfResults, DBuffer, NBuffer);
310 }
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:258

◆ 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
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

Definition at line 212 of file kdtree.cpp.

212  {
213  int Level;
214  KDNODE *Node;
215  KDNODE **PtrToNode;
216 
217  PtrToNode = &(Tree->Root.Left);
218  Node = *PtrToNode;
219  Level = NextLevel(Tree, -1);
220  while (Node != nullptr) {
221  if (Key[Level] < Node->BranchPoint) {
222  PtrToNode = &(Node->Left);
223  if (Key[Level] > Node->LeftBranch)
224  Node->LeftBranch = Key[Level];
225  }
226  else {
227  PtrToNode = &(Node->Right);
228  if (Key[Level] < Node->RightBranch)
229  Node->RightBranch = Key[Level];
230  }
231  Level = NextLevel(Tree, Level);
232  Node = *PtrToNode;
233  }
234 
235  *PtrToNode = MakeKDNode(Tree, Key, Data, Level);
236 } /* KDStore */
KDNODE * MakeKDNode(KDTREE *tree, float Key[], void *Data, int Index)
Definition: kdtree.cpp:352

◆ KDWalk()

void KDWalk ( KDTREE Tree,
void_proc  action,
void *  context 
)

Walk a given Tree with action.

Definition at line 315 of file kdtree.cpp.

315  {
316  if (Tree->Root.Left != nullptr)
317  Walk(Tree, action, context, Tree->Root.Left, NextLevel(Tree, -1));
318 }
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, int32_t level)
Definition: kdtree.cpp:512

◆ 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
treeThe tree to create the node for
KeyAccess key for new node in KD tree
Dataptr to data to be stored in new node
Indexindex of Key to branch on
Returns
pointer to new K-D tree node

Definition at line 352 of file kdtree.cpp.

352  {
353  KDNODE *NewNode;
354 
355  NewNode = static_cast<KDNODE *>(Emalloc (sizeof (KDNODE)));
356 
357  NewNode->Key = Key;
358  NewNode->Data = Data;
359  NewNode->BranchPoint = Key[Index];
360  NewNode->LeftBranch = tree->KeyDesc[Index].Min;
361  NewNode->RightBranch = tree->KeyDesc[Index].Max;
362  NewNode->Left = nullptr;
363  NewNode->Right = nullptr;
364 
365  return NewNode;
366 } /* MakeKDNode */
void * Emalloc(int Size)
Definition: emalloc.cpp:31

◆ MakeKDTree()

KDTREE* MakeKDTree ( int16_t  KeySize,
const PARAM_DESC  KeyDesc[] 
)
Returns
a new KDTREE based on the specified parameters.
Parameters
KeySize# of dimensions in the K-D tree
KeyDescarray of params to describe key dimensions

Definition at line 180 of file kdtree.cpp.

180  {
181  auto *KDTree = static_cast<KDTREE *>(Emalloc(
182  sizeof(KDTREE) + (KeySize - 1) * sizeof(PARAM_DESC)));
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;
192  } else {
193  KDTree->KeyDesc[i].Min = MINSEARCH;
194  KDTree->KeyDesc[i].Max = MAXSEARCH;
195  }
196  }
197  KDTree->KeySize = KeySize;
198  KDTree->Root.Left = nullptr;
199  KDTree->Root.Right = nullptr;
200  return KDTree;
201 }
#define MAXSEARCH
Definition: kdtree.cpp:36
#define MINSEARCH
Definition: kdtree.cpp:35
Definition: kdtree.h:48

◆ Walk()

void Walk ( KDTREE tree,
void_proc  action,
void *  context,
KDNODE sub_tree,
int32_t  level 
)

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
treeroot of the tree being walked.
actionaction to be performed at every node
contextaction's context
sub_treeptr to root of subtree to be walked
levelcurrent level in the tree for this node

Definition at line 512 of file kdtree.cpp.

513  {
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)
518  Walk(tree, action, context, sub_tree->Right, NextLevel(tree, level));
519 }