tesseract 5.2.0
Loading...
Searching...
No Matches
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
23namespace tesseract {
24
25using void_proc = void (*)(...);
26
37struct KDTREE;
38
39struct KDNODE {
48 KDNODE() = default;
49 KDNODE(KDTREE *tree, float key[], void *data, int Index);
51 delete Left;
52 delete Right;
53 }
54
55 float *Key;
56 void *Data;
58 float LeftBranch;
62};
63
64struct 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.
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
83inline 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-----------------------------------------------------------------------------*/
101KDTREE *MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[]);
102
103void KDStore(KDTREE *Tree, float *Key, void *Data);
104
105void KDDelete(KDTREE *Tree, float Key[], void *Data);
106
107void KDNearestNeighborSearch(KDTREE *Tree, float Query[], int QuerySize, float MaxDistance,
108 int *NumberOfResults, void **NBuffer, float DBuffer[]);
109
110void KDWalk(KDTREE *Tree, void_proc Action, void *context);
111
112/*-----------------------------------------------------------------------------
113 Private Function Prototypes
114-----------------------------------------------------------------------------*/
115
116float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[]);
117
119float ComputeDistance(int k, PARAM_DESC *dim, float p1[], float p2[]);
120
122
123void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *SubTree, int32_t Level);
124
125void 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:32