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