tesseract 4.1.1
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/*-----------------------------------------------------------------------------
22 Include Files and Type Defines
23-----------------------------------------------------------------------------*/
24#include "ocrfeatures.h"
25
26using void_proc = void (*)(...);
27
38struct KDNODE {
39 float* Key;
40 void* Data;
42 float LeftBranch;
44 struct KDNODE* Left;
45 struct KDNODE* Right;
46};
47
48struct KDTREE {
49 int16_t KeySize; /* number of dimensions in the tree */
50 KDNODE Root; /* Root.Left points to actual root node */
51 PARAM_DESC KeyDesc[1]; /* description of each dimension */
52};
53
54/*----------------------------------------------------------------------------
55 Macros
56-----------------------------------------------------------------------------*/
57#define RootOf(T) ((T)->Root.Left->Data)
58
59/*-----------------------------------------------------------------------------
60 Public Function Prototypes
61-----------------------------------------------------------------------------*/
62KDTREE* MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[]);
63
64void KDStore(KDTREE* Tree, float* Key, void* Data);
65
66void KDDelete(KDTREE* Tree, float Key[], void* Data);
67
68void KDNearestNeighborSearch(KDTREE* Tree, float Query[], int QuerySize,
69 float MaxDistance, int* NumberOfResults,
70 void** NBuffer, float DBuffer[]);
71
72void KDWalk(KDTREE* Tree, void_proc Action, void* context);
73
74void FreeKDTree(KDTREE* Tree);
75
76/*-----------------------------------------------------------------------------
77 Private Function Prototypes
78-----------------------------------------------------------------------------*/
79KDNODE* MakeKDNode(KDTREE* tree, float Key[], void* Data, int Index);
80
81void FreeKDNode(KDNODE* Node);
82
83float DistanceSquared(int k, PARAM_DESC* dim, float p1[], float p2[]);
84
85float ComputeDistance(int k, PARAM_DESC* dim, float p1[], float p2[]);
86
88
89void Walk(KDTREE* tree, void_proc action, void* context, KDNODE* SubTree,
90 int32_t Level);
91
92void InsertNodes(KDTREE* tree, KDNODE* nodes);
93
94void FreeSubTree(KDNODE* SubTree);
95
96#endif
void Walk(KDTREE *tree, void_proc action, void *context, KDNODE *SubTree, int32_t Level)
Definition: kdtree.cpp:512
void(*)(...) void_proc
Definition: kdtree.h:26
void FreeKDNode(KDNODE *Node)
Definition: kdtree.cpp:370
void KDStore(KDTREE *Tree, float *Key, void *Data)
Definition: kdtree.cpp:212
float ComputeDistance(int k, PARAM_DESC *dim, float p1[], float p2[])
Definition: kdtree.cpp:448
void FreeKDTree(KDTREE *Tree)
Definition: kdtree.cpp:331
void KDNearestNeighborSearch(KDTREE *Tree, float Query[], int QuerySize, float MaxDistance, int *NumberOfResults, void **NBuffer, float DBuffer[])
Definition: kdtree.cpp:305
KDNODE * MakeKDNode(KDTREE *tree, float Key[], void *Data, int Index)
Definition: kdtree.cpp:352
void KDWalk(KDTREE *Tree, void_proc Action, void *context)
Definition: kdtree.cpp:315
int QueryInSearch(KDTREE *tree)
void FreeSubTree(KDNODE *SubTree)
Definition: kdtree.cpp:532
void KDDelete(KDTREE *Tree, float Key[], void *Data)
Definition: kdtree.cpp:253
KDTREE * MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[])
Definition: kdtree.cpp:180
float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[])
Definition: kdtree.cpp:427
void InsertNodes(KDTREE *tree, KDNODE *nodes)
Definition: kdtree.cpp:522
Definition: kdtree.h:38
float RightBranch
Definition: kdtree.h:43
float * Key
Definition: kdtree.h:39
float LeftBranch
Definition: kdtree.h:42
float BranchPoint
Definition: kdtree.h:41
struct KDNODE * Left
Definition: kdtree.h:44
struct KDNODE * Right
Definition: kdtree.h:45
void * Data
Definition: kdtree.h:40
Definition: kdtree.h:48
PARAM_DESC KeyDesc[1]
Definition: kdtree.h:51
int16_t KeySize
Definition: kdtree.h:49
KDNODE Root
Definition: kdtree.h:50