tesseract  5.0.0
kdtree.h
Go to the documentation of this file.
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 
18 #ifndef KDTREE_H
19 #define KDTREE_H
20 
21 #include "ocrfeatures.h"
22 
23 namespace tesseract {
24 
25 using void_proc = void (*)(...);
26 
37 struct KDTREE;
38 
39 struct KDNODE {
48  KDNODE() = default;
49  KDNODE(KDTREE *tree, float key[], void *data, int Index);
50  ~KDNODE() {
51  delete Left;
52  delete Right;
53  }
54 
55  float *Key;
56  void *Data;
57  float BranchPoint;
58  float LeftBranch;
59  float RightBranch;
62 };
63 
64 struct KDTREE {
65  KDTREE(size_t n) : KeySize(n), KeyDesc(n) {
66  }
67 
68  // The destructor frees all memory which is allocated to the
69  // specified KD-tree. This includes the data structure for
70  // the kd-tree itself plus the data structures for each node
71  // in the tree. It does not include the Key and Data items
72  // which are pointed to by the nodes. This memory is left
73  // untouched.
74  ~KDTREE() {
75  }
76 
77  // TODO: KeySize might be replaced by KeyDesc.size().
78  int16_t KeySize = 0; // number of dimensions in the tree
79  KDNODE Root; // Root.Left points to actual root node
80  std::vector<PARAM_DESC> KeyDesc; // description of each dimension
81 };
82 
83 inline KDNODE::KDNODE(KDTREE *tree, float key[], void *data, int Index) {
84  Key = key;
85  Data = data;
86  BranchPoint = Key[Index];
87  LeftBranch = tree->KeyDesc[Index].Min;
88  RightBranch = tree->KeyDesc[Index].Max;
89  Left = nullptr;
90  Right = nullptr;
91 }
92 
93 /*----------------------------------------------------------------------------
94  Macros
95 -----------------------------------------------------------------------------*/
96 #define RootOf(T) ((T)->Root.Left->Data)
97 
98 /*-----------------------------------------------------------------------------
99  Public Function Prototypes
100 -----------------------------------------------------------------------------*/
101 KDTREE *MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[]);
102 
103 void KDStore(KDTREE *Tree, float *Key, void *Data);
104 
105 void KDDelete(KDTREE *Tree, float Key[], void *Data);
106 
107 void KDNearestNeighborSearch(KDTREE *Tree, float Query[], int QuerySize, float MaxDistance,
108  int *NumberOfResults, void **NBuffer, float DBuffer[]);
109 
110 void KDWalk(KDTREE *Tree, void_proc Action, void *context);
111 
112 /*-----------------------------------------------------------------------------
113  Private Function Prototypes
114 -----------------------------------------------------------------------------*/
115 
116 float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[]);
117 
118 TESS_API
119 float ComputeDistance(int k, PARAM_DESC *dim, float p1[], float p2[]);
120 
122 
123 void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *SubTree, int32_t Level);
124 
125 void InsertNodes(KDTREE *tree, KDNODE *nodes);
126 
127 } // namespace tesseract
128 
129 #endif
void KDDelete(KDTREE *Tree, float Key[], void *Data)
Definition: kdtree.cpp:252
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, int32_t level)
Definition: kdtree.cpp:466
void KDStore(KDTREE *Tree, float *Key, void *Data)
Definition: kdtree.cpp:215
float ComputeDistance(int k, PARAM_DESC *dim, float p1[], float p2[])
Definition: kdtree.cpp:400
float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[])
Definition: kdtree.cpp:378
void(*)(...) void_proc
Definition: kdtree.h:25
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:477
KDTREE * MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[])
Definition: kdtree.cpp:186
void KDWalk(KDTREE *Tree, void_proc action, void *context)
Definition: kdtree.cpp:313
int QueryInSearch(KDTREE *tree)
void KDNearestNeighborSearch(KDTREE *Tree, float Query[], int QuerySize, float MaxDistance, int *NumberOfResults, void **NBuffer, float DBuffer[])
Definition: kdtree.cpp:305
float * Key
Definition: kdtree.h:55
KDNODE * Right
Definition: kdtree.h:61
void * Data
Definition: kdtree.h:56
float LeftBranch
Definition: kdtree.h:58
KDNODE * Left
Definition: kdtree.h:60
float RightBranch
Definition: kdtree.h:59
float BranchPoint
Definition: kdtree.h:57
std::vector< PARAM_DESC > KeyDesc
Definition: kdtree.h:80
KDTREE(size_t n)
Definition: kdtree.h:65
int16_t KeySize
Definition: kdtree.h:78
KDNODE Root
Definition: kdtree.h:79
#define TESS_API
Definition: export.h:34