Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/classify/kdtree.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 /**
26 NOTE: All circular parameters of all keys must be in the range
27
28 Min <= Param < Max
29
30 where Min and Max are specified in the KeyDesc parameter passed to
31 MakeKDTree. All KD routines assume that this is true and will not operate
32 correctly if circular parameters outside the specified range are used.
33 */
34
35 struct ClusteringContext;
36 struct CLUSTER;
37 struct KDTREE;
38
39 using kdwalk_proc = void (*)(ClusteringContext *context, CLUSTER *Cluster, int32_t Level);
40
41 struct KDNODE {
42 /// This routine allocates memory for a new K-D tree node
43 /// and places the specified Key and Data into it. The
44 /// left and right subtree pointers for the node are
45 /// initialized to empty subtrees.
46 /// @param tree The tree to create the node for
47 /// @param Key Access key for new node in KD tree
48 /// @param Data ptr to data to be stored in new node
49 /// @param Index index of Key to branch on
50 KDNODE() = default;
51 KDNODE(KDTREE *tree, float key[], CLUSTER *data, int Index);
52 ~KDNODE() {
53 delete Left;
54 delete Right;
55 }
56
57 float *Key; /**< search key */
58 CLUSTER *Data; /**< data that corresponds to key */
59 float BranchPoint; /**< needed to make deletes work efficiently */
60 float LeftBranch; /**< used to optimize search pruning */
61 float RightBranch; /**< used to optimize search pruning */
62 KDNODE *Left; /**< ptrs for KD tree structure */
63 KDNODE *Right;
64 };
65
66 struct KDTREE {
67 KDTREE(size_t n) : KeySize(n), KeyDesc(n) {
68 }
69
70 // The destructor frees all memory which is allocated to the
71 // specified KD-tree. This includes the data structure for
72 // the kd-tree itself plus the data structures for each node
73 // in the tree. It does not include the Key and Data items
74 // which are pointed to by the nodes. This memory is left
75 // untouched.
76 ~KDTREE() {
77 }
78
79 // TODO: KeySize might be replaced by KeyDesc.size().
80 int16_t KeySize = 0; // number of dimensions in the tree
81 KDNODE Root; // Root.Left points to actual root node
82 std::vector<PARAM_DESC> KeyDesc; // description of each dimension
83 };
84
85 inline KDNODE::KDNODE(KDTREE *tree, float key[], CLUSTER *data, int Index) {
86 Key = key;
87 Data = data;
88 BranchPoint = Key[Index];
89 LeftBranch = tree->KeyDesc[Index].Min;
90 RightBranch = tree->KeyDesc[Index].Max;
91 Left = nullptr;
92 Right = nullptr;
93 }
94
95 /*----------------------------------------------------------------------------
96 Macros
97 -----------------------------------------------------------------------------*/
98 #define RootOf(T) ((T)->Root.Left->Data)
99
100 /*-----------------------------------------------------------------------------
101 Public Function Prototypes
102 -----------------------------------------------------------------------------*/
103 KDTREE *MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[]);
104
105 void KDStore(KDTREE *Tree, float *Key, CLUSTER *Data);
106
107 void KDDelete(KDTREE *Tree, float Key[], void *Data);
108
109 void KDNearestNeighborSearch(KDTREE *Tree, float Query[], int QuerySize, float MaxDistance,
110 int *NumberOfResults, void **NBuffer, float DBuffer[]);
111
112 void KDWalk(KDTREE *Tree, kdwalk_proc Action, ClusteringContext *context);
113
114 /*-----------------------------------------------------------------------------
115 Private Function Prototypes
116 -----------------------------------------------------------------------------*/
117
118 float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[]);
119
120 TESS_API
121 float ComputeDistance(int k, PARAM_DESC *dim, float p1[], float p2[]);
122
123 int QueryInSearch(KDTREE *tree);
124
125 void Walk(KDTREE *tree, kdwalk_proc action, ClusteringContext *context, KDNODE *SubTree, int32_t Level);
126
127 void InsertNodes(KDTREE *tree, KDNODE *nodes);
128
129 } // namespace tesseract
130
131 #endif