tesseract  5.0.0-alpha-619-ge9db
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 28 of file kdtree.cpp.

◆ MAXSEARCH

#define MAXSEARCH   FLT_MAX

Definition at line 35 of file kdtree.cpp.

◆ MINSEARCH

#define MINSEARCH   -FLT_MAX

Definition at line 34 of file kdtree.cpp.

◆ NodeFound

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

Definition at line 29 of file kdtree.cpp.

Function Documentation

◆ ComputeDistance()

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

Definition at line 447 of file kdtree.cpp.

448  {
449  return sqrt(DistanceSquared(k, dim, p1, p2));

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

◆ FreeKDNode()

void FreeKDNode ( KDNODE Node)

Definition at line 369 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 330 of file kdtree.cpp.

331  {
332  FreeSubTree(Tree->Root.Left);
333  free(Tree);

◆ FreeSubTree()

void FreeSubTree ( KDNODE sub_tree)

Free all of the nodes of a sub tree.

Definition at line 531 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  }

◆ InsertNodes()

void InsertNodes ( KDTREE tree,
KDNODE nodes 
)

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

Definition at line 521 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);

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

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

307  {
308  KDTreeSearch search(Tree, Query, QuerySize);
309  search.Search(NumberOfResults, DBuffer, NBuffer);

◆ 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 211 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);

◆ KDWalk()

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

Walk a given Tree with action.

Definition at line 314 of file kdtree.cpp.

315  {
316  if (Tree->Root.Left != nullptr)
317  Walk(Tree, action, context, Tree->Root.Left, NextLevel(Tree, -1));

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

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

◆ 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 511 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));
KDNODE::Key
float * Key
Definition: kdtree.h:38
KDTreeSearch
Definition: kdtree.cpp:119
PARAM_DESC::Circular
bool Circular
Definition: ocrfeatures.h:42
Emalloc
void * Emalloc(int Size)
Definition: emalloc.cpp:31
DistanceSquared
float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[])
Definition: kdtree.cpp:426
MakeKDNode
KDNODE * MakeKDNode(KDTREE *tree, float Key[], void *Data, int Index)
Definition: kdtree.cpp:351
KDTREE::KeyDesc
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:50
PARAM_DESC::Min
float Min
Definition: ocrfeatures.h:44
KDTREE
Definition: kdtree.h:47
KDNODE::Data
void * Data
Definition: kdtree.h:39
KDTREE::Root
KDNODE Root
Definition: kdtree.h:49
KDStore
void KDStore(KDTREE *Tree, float *Key, void *Data)
Definition: kdtree.cpp:211
KDNODE::Left
struct KDNODE * Left
Definition: kdtree.h:43
InsertNodes
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:521
PARAM_DESC::Max
float Max
Definition: ocrfeatures.h:45
MAXSEARCH
#define MAXSEARCH
Definition: kdtree.cpp:35
PARAM_DESC
Definition: ocrfeatures.h:41
PARAM_DESC::NonEssential
bool NonEssential
Definition: ocrfeatures.h:43
FreeSubTree
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:531
NodeFound
#define NodeFound(N, K, D)
Definition: kdtree.cpp:29
Walk
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, int32_t level)
Definition: kdtree.cpp:511
KDNODE::Right
struct KDNODE * Right
Definition: kdtree.h:44
KDNODE::RightBranch
float RightBranch
Definition: kdtree.h:42
KDNODE::LeftBranch
float LeftBranch
Definition: kdtree.h:41
KDNODE::BranchPoint
float BranchPoint
Definition: kdtree.h:40
Magnitude
#define Magnitude(X)
Definition: kdtree.cpp:28
KDNODE
Definition: kdtree.h:37
tesstrain_utils.action
action
Definition: tesstrain_utils.py:159
search
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:202
MINSEARCH
#define MINSEARCH
Definition: kdtree.cpp:34