Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Macros | Functions
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

KDTREE * | MakeKDTree (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)
KDNODE * | MakeKDNode (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,
|  |  | D
| ) |  | (( (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.

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

FLOAT32 DistanceSquared | ( | int | k,
|  | PARAM_DESC * | dim,
|  | FLOAT32 | p1[],
|  | FLOAT32 | p2[]
| ) |  |

Definition at line 465 of file kdtree.cpp.

{
FLOAT32 total_distance = 0;
for (; k > 0; k--, p1++, p2++, dim++) {
if (dim->NonEssential)
continue;
FLOAT32 dimension_distance = *p1 - *p2;
/* if this dimension is circular - check wraparound distance */
if (dim->Circular) {
dimension_distance = Magnitude(dimension_distance);
FLOAT32 wrap_distance = dim->Max - dim->Min - dimension_distance;
dimension_distance = MIN(dimension_distance, wrap_distance);
}
total_distance += dimension_distance * dimension_distance;
}
return total_distance;
}

void FreeKDNode | ( | KDNODE * | Node | ) |

Definition at line 407 of file kdtree.cpp.

{
memfree ((char *)Node);
}

void FreeKDTree | ( | KDTREE * | Tree | ) |

Definition at line 346 of file kdtree.cpp.

{
/*
** Parameters:
** Tree tree data structure to be released
** Operation:
** 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.
** Return: none
** Exceptions: none
** History:
** 5/26/89, DSJ, Created.
*/
FreeSubTree(Tree->Root.Left);
memfree(Tree);
} /* FreeKDTree */

void FreeSubTree | ( | KDNODE * | sub_tree | ) |

Definition at line 568 of file kdtree.cpp.

{
if (sub_tree != NULL) {
FreeSubTree(sub_tree->Left);
FreeSubTree(sub_tree->Right);
memfree(sub_tree);
}
} /* FreeSubTree */

void InsertNodes | ( | KDTREE * | tree,
|  | KDNODE * | nodes
| ) |  |

Definition at line 558 of file kdtree.cpp.

{
if (nodes == NULL)
return;
KDStore(tree, nodes->Key, nodes->Data);
InsertNodes(tree, nodes->Left);
InsertNodes(tree, nodes->Right);
}

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:

  Tree | K-D tree to delete node from
  Key | key of node to be deleted
  Data | data 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.

{
int Level;
KDNODE *Current;
KDNODE *Father;
/* initialize search at root of tree */
Father = &(Tree->Root);
Current = Father->Left;
Level = NextLevel(Tree, -1);
/* search tree for node to be deleted */
while ((Current != NULL) && (!NodeFound (Current, Key, Data))) {
Father = Current;
if (Key[Level] < Current->BranchPoint)
Current = Current->Left;
else
Current = Current->Right;
Level = NextLevel(Tree, Level);
}
if (Current != NULL) { /* if node to be deleted was found */
if (Current == Father->Left) {
Father->Left = NULL;
Father->LeftBranch = Tree->KeyDesc[Level].Min;
} else {
Father->Right = NULL;
Father->RightBranch = Tree->KeyDesc[Level].Max;
}
InsertNodes(Tree, Current->Left);
InsertNodes(Tree, Current->Right);
FreeSubTree(Current);
}
} /* KDDelete */

void KDNearestNeighborSearch | ( | KDTREE * | Tree,
|  | FLOAT32 | Query[],
|  | int | QuerySize,
|  | FLOAT32 | MaxDistance,
|  | int * | NumberOfResults,
|  | void ** | NBuffer,
|  | FLOAT32 | DBuffer[]
| ) |  |

Definition at line 307 of file kdtree.cpp.

{
/*
** Parameters:
** Tree ptr to K-D tree to be searched
** Query ptr to query key (point in D-space)
** QuerySize number of nearest neighbors to be found
** MaxDistance all neighbors must be within this distance
** NBuffer ptr to QuerySize buffer to hold nearest neighbors
** DBuffer ptr to QuerySize buffer to hold distances
** from nearest neighbor to query point
** Operation:
** 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.
** Return: Number of nearest neighbors actually found
** Exceptions: none
** History:
** 3/10/89, DSJ, Created.
** 7/13/89, DSJ, Return contents of node instead of node itself.
*/
KDTreeSearch search(Tree, Query, QuerySize);
search.Search(NumberOfResults, DBuffer, NBuffer);
}

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:

  Tree | K-D tree in which data is to be stored
  Key | ptr to key by which data can be retrieved
  Data | ptr 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.

{
int Level;
KDNODE *Node;
KDNODE **PtrToNode;
PtrToNode = &(Tree->Root.Left);
Node = *PtrToNode;
Level = NextLevel(Tree, -1);
while (Node != NULL) {
if (Key[Level] < Node->BranchPoint) {
PtrToNode = &(Node->Left);
if (Key[Level] > Node->LeftBranch)
Node->LeftBranch = Key[Level];
}
else {
PtrToNode = &(Node->Right);
if (Key[Level] < Node->RightBranch)
Node->RightBranch = Key[Level];
}
Level = NextLevel(Tree, Level);
Node = *PtrToNode;
}
*PtrToNode = MakeKDNode(Tree, Key, (void *) Data, Level);
} /* KDStore */

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

Definition at line 339 of file kdtree.cpp.

{
if (Tree->Root.Left != NULL)
Walk(Tree, action, context, Tree->Root.Left, NextLevel(Tree, -1));
}

KDNODE* MakeKDNode | ( | KDTREE * | tree,
|  | FLOAT32 | Key[],
|  | void * | Data,
|  | int | Index
| ) |  |

Definition at line 371 of file kdtree.cpp.

{
/*
** Parameters:
** tree The tree to create the node for
** Key Access key for new node in KD tree
** Data ptr to data to be stored in new node
** Index index of Key to branch on
** Operation:
** 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.
** Return:
** pointer to new K-D tree node
** Exceptions:
** None
** History:
** 3/11/89, DSJ, Created.
*/
KDNODE *NewNode;
NewNode = (KDNODE *) Emalloc (sizeof (KDNODE));
NewNode->Key = Key;
NewNode->Data = Data;
NewNode->BranchPoint = Key[Index];
NewNode->LeftBranch = tree->KeyDesc[Index].Min;
NewNode->RightBranch = tree->KeyDesc[Index].Max;
NewNode->Left = NULL;
NewNode->Right = NULL;
return NewNode;
} /* MakeKDNode */

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.

{
KDTREE *KDTree = (KDTREE *) Emalloc(
sizeof(KDTREE) + (KeySize - 1) * sizeof(PARAM_DESC));
for (int i = 0; i < KeySize; i++) {
KDTree->KeyDesc[i].NonEssential = KeyDesc[i].NonEssential;
KDTree->KeyDesc[i].Circular = KeyDesc[i].Circular;
if (KeyDesc[i].Circular) {
KDTree->KeyDesc[i].Min = KeyDesc[i].Min;
KDTree->KeyDesc[i].Max = KeyDesc[i].Max;
KDTree->KeyDesc[i].Range = KeyDesc[i].Max - KeyDesc[i].Min;
KDTree->KeyDesc[i].HalfRange = KDTree->KeyDesc[i].Range / 2;
KDTree->KeyDesc[i].MidRange = (KeyDesc[i].Max + KeyDesc[i].Min) / 2;
} else {
KDTree->KeyDesc[i].Min = MINSEARCH;
KDTree->KeyDesc[i].Max = MAXSEARCH;
}
}
KDTree->KeySize = KeySize;
KDTree->Root.Left = NULL;
KDTree->Root.Right = NULL;
return KDTree;
}

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

Definition at line 547 of file kdtree.cpp.

{
(*action)(context, sub_tree->Data, level);
if (sub_tree->Left != NULL)
Walk(tree, action, context, sub_tree->Left, NextLevel(tree, level));
if (sub_tree->Right != NULL)
Walk(tree, action, context, sub_tree->Right, NextLevel(tree, level));
}