tesseract 4.1.1
Loading...
Searching...
No Matches
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}