tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
kdtree.h
1 /******************************************************************************
2  ** Filename: kdtree.h
3  ** Purpose: Definition of K-D tree access routines.
4  ** Author: Dan Johnson
5  **
6  ** (c) Copyright Hewlett-Packard Company, 1988.
7  ** Licensed under the Apache License, Version 2.0 (the "License");
8  ** you may not use this file except in compliance with the License.
9  ** You may obtain a copy of the License at
10  ** http://www.apache.org/licenses/LICENSE-2.0
11  ** Unless required by applicable law or agreed to in writing, software
12  ** distributed under the License is distributed on an "AS IS" BASIS,
13  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  ** See the License for the specific language governing permissions and
15  ** limitations under the License.
16  *****************************************************************************/
17 #ifndef KDTREE_H
18 #define KDTREE_H
19 
20 /*-----------------------------------------------------------------------------
21  Include Files and Type Defines
22 -----------------------------------------------------------------------------*/
23 #include "cutil.h" // for void_proc
24 #include "host.h"
25 #include "ocrfeatures.h"
26 
37 struct KDNODE {
38  float *Key;
39  void *Data;
40  float BranchPoint;
41  float LeftBranch;
42  float RightBranch;
43  struct KDNODE *Left;
44  struct KDNODE *Right;
45 };
46 
47 struct KDTREE {
48  int16_t KeySize; /* number of dimensions in the tree */
49  KDNODE Root; /* Root.Left points to actual root node */
50  PARAM_DESC KeyDesc[1]; /* description of each dimension */
51 };
52 
53 /*----------------------------------------------------------------------------
54  Macros
55 -----------------------------------------------------------------------------*/
56 #define RootOf(T) ((T)->Root.Left->Data)
57 
58 /*-----------------------------------------------------------------------------
59  Public Function Prototypes
60 -----------------------------------------------------------------------------*/
61 KDTREE *MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[]);
62 
63 void KDStore(KDTREE *Tree, float *Key, void *Data);
64 
65 void KDDelete(KDTREE * Tree, float Key[], void *Data);
66 
67 void KDNearestNeighborSearch(
68  KDTREE *Tree, float Query[], int QuerySize, float MaxDistance,
69  int *NumberOfResults, void **NBuffer, float DBuffer[]);
70 
71 void KDWalk(KDTREE *Tree, void_proc Action, void *context);
72 
73 void FreeKDTree(KDTREE *Tree);
74 
75 /*-----------------------------------------------------------------------------
76  Private Function Prototypes
77 -----------------------------------------------------------------------------*/
78 KDNODE *MakeKDNode(KDTREE *tree, float Key[], void *Data, int Index);
79 
80 void FreeKDNode(KDNODE *Node);
81 
82 float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[]);
83 
84 float ComputeDistance(int k, PARAM_DESC *dim, float p1[], float p2[]);
85 
86 int QueryInSearch(KDTREE *tree);
87 
88 void Walk(KDTREE *tree, void_proc action, void *context,
89  KDNODE *SubTree, int32_t Level);
90 
91 void InsertNodes(KDTREE *tree, KDNODE *nodes);
92 
93 void FreeSubTree(KDNODE *SubTree);
94 #endif
float * Key
Definition: kdtree.h:38
float RightBranch
Definition: kdtree.h:42
struct KDNODE * Left
Definition: kdtree.h:43
struct KDNODE * Right
Definition: kdtree.h:44
Definition: kdtree.h:37
float LeftBranch
Definition: kdtree.h:41
void * Data
Definition: kdtree.h:39
float BranchPoint
Definition: kdtree.h:40
KDNODE Root
Definition: kdtree.h:49
Definition: ocrfeatures.h:43
int16_t KeySize
Definition: kdtree.h:48
Definition: kdtree.h:47