tesseract  4.0.0-1-g2a2b
kdtree.cpp File Reference
#include "kdtree.h"
#include "cutil.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 30 of file kdtree.cpp.

◆ MAXSEARCH

#define MAXSEARCH   FLT_MAX

Definition at line 37 of file kdtree.cpp.

◆ MINSEARCH

#define MINSEARCH   -FLT_MAX

Definition at line 36 of file kdtree.cpp.

◆ NodeFound

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

Definition at line 31 of file kdtree.cpp.

Function Documentation

◆ ComputeDistance()

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

Definition at line 450 of file kdtree.cpp.

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

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

429  {
430  float total_distance = 0;
431 
432  for (; k > 0; k--, p1++, p2++, dim++) {
433  if (dim->NonEssential)
434  continue;
435 
436  float dimension_distance = *p1 - *p2;
437 
438  /* if this dimension is circular - check wraparound distance */
439  if (dim->Circular) {
440  dimension_distance = Magnitude(dimension_distance);
441  float wrap_distance = dim->Max - dim->Min - dimension_distance;
442  dimension_distance = std::min(dimension_distance, wrap_distance);
443  }
444 
445  total_distance += dimension_distance * dimension_distance;
446  }
447  return total_distance;
448 }
int8_t Circular
Definition: ocrfeatures.h:44
float Min
Definition: ocrfeatures.h:46
#define Magnitude(X)
Definition: kdtree.cpp:30
int8_t NonEssential
Definition: ocrfeatures.h:45
float Max
Definition: ocrfeatures.h:47

◆ FreeKDNode()

void FreeKDNode ( KDNODE Node)

Definition at line 372 of file kdtree.cpp.

372 { 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
Returns
none

Definition at line 333 of file kdtree.cpp.

333  {
334  FreeSubTree(Tree->Root.Left);
335  free(Tree);
336 } /* FreeKDTree */
struct KDNODE * Left
Definition: kdtree.h:43
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:534
KDNODE Root
Definition: kdtree.h:49

◆ FreeSubTree()

void FreeSubTree ( KDNODE sub_tree)

Free all of the nodes of a sub tree.

Definition at line 534 of file kdtree.cpp.

534  {
535  if (sub_tree != nullptr) {
536  FreeSubTree(sub_tree->Left);
537  FreeSubTree(sub_tree->Right);
538  free(sub_tree);
539  }
540 }
struct KDNODE * Left
Definition: kdtree.h:43
void FreeSubTree(KDNODE *sub_tree)
Definition: kdtree.cpp:534
struct KDNODE * Right
Definition: kdtree.h:44

◆ InsertNodes()

void InsertNodes ( KDTREE tree,
KDNODE nodes 
)

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

Definition at line 524 of file kdtree.cpp.

524  {
525  if (nodes == nullptr)
526  return;
527 
528  KDStore(tree, nodes->Key, nodes->Data);
529  InsertNodes(tree, nodes->Left);
530  InsertNodes(tree, nodes->Right);
531 }
float * Key
Definition: kdtree.h:38
struct KDNODE * Left
Definition: kdtree.h:43
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:524
void KDStore(KDTREE *Tree, float *Key, void *Data)
Definition: kdtree.cpp:213
void * Data
Definition: kdtree.h:39
struct KDNODE * Right
Definition: kdtree.h:44

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

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

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

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

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

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

◆ KDWalk()

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

Walk a given Tree with action.

Definition at line 316 of file kdtree.cpp.

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

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

354  {
355  KDNODE *NewNode;
356 
357  NewNode = (KDNODE *) Emalloc (sizeof (KDNODE));
358 
359  NewNode->Key = Key;
360  NewNode->Data = Data;
361  NewNode->BranchPoint = Key[Index];
362  NewNode->LeftBranch = tree->KeyDesc[Index].Min;
363  NewNode->RightBranch = tree->KeyDesc[Index].Max;
364  NewNode->Left = nullptr;
365  NewNode->Right = nullptr;
366 
367  return NewNode;
368 } /* MakeKDNode */
float * Key
Definition: kdtree.h:38
struct KDNODE * Left
Definition: kdtree.h:43
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:50
float Min
Definition: ocrfeatures.h:46
void * Emalloc(int Size)
Definition: emalloc.cpp:31
float LeftBranch
Definition: kdtree.h:41
float RightBranch
Definition: kdtree.h:42
Definition: kdtree.h:37
float BranchPoint
Definition: kdtree.h:40
void * Data
Definition: kdtree.h:39
float Max
Definition: ocrfeatures.h:47
struct KDNODE * Right
Definition: kdtree.h:44

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

181  {
182  KDTREE *KDTree = (KDTREE *) Emalloc(
183  sizeof(KDTREE) + (KeySize - 1) * sizeof(PARAM_DESC));
184  for (int i = 0; i < KeySize; i++) {
185  KDTree->KeyDesc[i].NonEssential = KeyDesc[i].NonEssential;
186  KDTree->KeyDesc[i].Circular = KeyDesc[i].Circular;
187  if (KeyDesc[i].Circular) {
188  KDTree->KeyDesc[i].Min = KeyDesc[i].Min;
189  KDTree->KeyDesc[i].Max = KeyDesc[i].Max;
190  KDTree->KeyDesc[i].Range = KeyDesc[i].Max - KeyDesc[i].Min;
191  KDTree->KeyDesc[i].HalfRange = KDTree->KeyDesc[i].Range / 2;
192  KDTree->KeyDesc[i].MidRange = (KeyDesc[i].Max + KeyDesc[i].Min) / 2;
193  } else {
194  KDTree->KeyDesc[i].Min = MINSEARCH;
195  KDTree->KeyDesc[i].Max = MAXSEARCH;
196  }
197  }
198  KDTree->KeySize = KeySize;
199  KDTree->Root.Left = nullptr;
200  KDTree->Root.Right = nullptr;
201  return KDTree;
202 }
float MidRange
Definition: ocrfeatures.h:50
int8_t Circular
Definition: ocrfeatures.h:44
float HalfRange
Definition: ocrfeatures.h:49
struct KDNODE * Left
Definition: kdtree.h:43
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:50
float Min
Definition: ocrfeatures.h:46
void * Emalloc(int Size)
Definition: emalloc.cpp:31
Definition: kdtree.h:47
#define MINSEARCH
Definition: kdtree.cpp:36
float Range
Definition: ocrfeatures.h:48
#define MAXSEARCH
Definition: kdtree.cpp:37
int16_t KeySize
Definition: kdtree.h:48
int8_t NonEssential
Definition: ocrfeatures.h:45
KDNODE Root
Definition: kdtree.h:49
float Max
Definition: ocrfeatures.h:47
struct KDNODE * Right
Definition: kdtree.h:44

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

515  {
516  (*action)(context, sub_tree->Data, level);
517  if (sub_tree->Left != nullptr)
518  Walk(tree, action, context, sub_tree->Left, NextLevel(tree, level));
519  if (sub_tree->Right != nullptr)
520  Walk(tree, action, context, sub_tree->Right, NextLevel(tree, level));
521 }
struct KDNODE * Left
Definition: kdtree.h:43
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, int32_t level)
Definition: kdtree.cpp:514
void * Data
Definition: kdtree.h:39
struct KDNODE * Right
Definition: kdtree.h:44