Tesseract  3.02
tesseract-ocr/classify/kdtree.h
Go to the documentation of this file.
00001 /******************************************************************************
00002  **     Filename:       kdtree.h
00003  **     Purpose:        Definition of K-D tree access routines.
00004  **     Author:         Dan Johnson
00005  **     History:        3/11/89, DSJ, Created.
00006  **                     5/23/89, DSJ, Added circular feature capability.
00007  **
00008  **     (c) Copyright Hewlett-Packard Company, 1988.
00009  ** Licensed under the Apache License, Version 2.0 (the "License");
00010  ** you may not use this file except in compliance with the License.
00011  ** You may obtain a copy of the License at
00012  ** http://www.apache.org/licenses/LICENSE-2.0
00013  ** Unless required by applicable law or agreed to in writing, software
00014  ** distributed under the License is distributed on an "AS IS" BASIS,
00015  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00016  ** See the License for the specific language governing permissions and
00017  ** limitations under the License.
00018  ******************************************************************************/
00019 #ifndef   KDTREE_H
00020 #define   KDTREE_H
00021 
00022 /*-----------------------------------------------------------------------------
00023           Include Files and Type Defines
00024 -----------------------------------------------------------------------------*/
00025 #include "host.h"
00026 #include "cutil.h"
00027 #include "ocrfeatures.h"
00028 
00039 struct KDNODE {
00040   FLOAT32 *Key;                  
00041   void *Data;                    
00042   FLOAT32 BranchPoint;           
00043   FLOAT32 LeftBranch;            
00044   FLOAT32 RightBranch;           
00045   struct KDNODE *Left;           
00046   struct KDNODE *Right;
00047 };
00048 
00049 struct KDTREE {
00050   inT16 KeySize;                 /* number of dimensions in the tree */
00051   KDNODE Root;                   /* Root.Left points to actual root node */
00052   PARAM_DESC KeyDesc[1];         /* description of each dimension */
00053 };
00054 
00055 /*----------------------------------------------------------------------------
00056             Macros
00057 -----------------------------------------------------------------------------*/
00058 #define RootOf(T)   ((T)->Root.Left->Data)
00059 
00060 /*-----------------------------------------------------------------------------
00061           Public Function Prototypes
00062 -----------------------------------------------------------------------------*/
00063 KDTREE *MakeKDTree(inT16 KeySize, const PARAM_DESC KeyDesc[]);
00064 
00065 void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data);
00066 
00067 void KDDelete(KDTREE * Tree, FLOAT32 Key[], void *Data);
00068 
00069 void KDNearestNeighborSearch(
00070     KDTREE *Tree, FLOAT32 Query[], int QuerySize, FLOAT32 MaxDistance,
00071     int *NumberOfResults, void **NBuffer, FLOAT32 DBuffer[]);
00072 
00073 void KDWalk(KDTREE *Tree, void_proc Action, void *context);
00074 
00075 void FreeKDTree(KDTREE *Tree);
00076 
00077 /*-----------------------------------------------------------------------------
00078           Private Function Prototypes
00079 -----------------------------------------------------------------------------*/
00080 KDNODE *MakeKDNode(KDTREE *tree, FLOAT32 Key[], void *Data, int Index);
00081 
00082 void FreeKDNode(KDNODE *Node);
00083 
00084 FLOAT32 DistanceSquared(int k, PARAM_DESC *dim, FLOAT32 p1[], FLOAT32 p2[]);
00085 
00086 FLOAT32 ComputeDistance(int k, PARAM_DESC *dim, FLOAT32 p1[], FLOAT32 p2[]);
00087 
00088 int QueryInSearch(KDTREE *tree);
00089 
00090 void Walk(KDTREE *tree, void_proc action, void *context,
00091           KDNODE *SubTree, inT32 Level);
00092 
00093 void InsertNodes(KDTREE *tree, KDNODE *nodes);
00094 
00095 void FreeSubTree(KDNODE *SubTree);
00096 #endif