classify/kdtree.h

Go to the documentation of this file.
00001 
00020 #ifndef   KDTREE_H
00021 #define   KDTREE_H
00022 
00023 /* =================
00024           Include Files and Type Defines
00025  ==================== */
00026 #include "general.h"
00027 #include "cutil.h"
00028 #include "ocrfeatures.h"
00029 
00030 /*
00031 All circular parameters of all keys must be in the range
00032 
00033 Min <= Param < Max
00034 
00035 where Min and Max are specified in the KeyDesc parameter passed to
00036 MakeKDTree.  All KD routines assume that this is true and will not operate
00037 correctly if circular parameters outside the specified range are used.
00038 */
00039 
00045 typedef struct kdnode
00046 {
00047   FLOAT32 *Key;                  /* search key */
00048   char *Data;                    /* data that corresponds to key */
00049   FLOAT32 BranchPoint;           /* needed to make deletes work efficiently */
00050   FLOAT32 LeftBranch;            /* used to optimize search pruning */
00051   FLOAT32 RightBranch;           /* used to optimize search pruning */
00052   struct kdnode *Left;           /* ptrs for KD tree structure */
00053   struct kdnode *Right;
00054 } KDNODE;
00055 
00060 typedef struct
00061 {
00062   INT16 KeySize;                 /* number of dimensions in the tree */
00063   KDNODE Root;                   /* Root.Left points to actual root node */
00064   PARAM_DESC KeyDesc[1];         /* description of each dimension */
00065 } KDTREE;
00066 
00072 typedef enum {
00073   preorder, postorder, endorder, leaf
00074 } VISIT;
00075 
00076 /*----------------------------------------------------------------------------
00077             Macros
00078 -----------------------------------------------------------------------------*/
00079 #define RootOf(T)   ((T)->Root.Left->Data)
00080 
00081 /* =================
00082           Public Function Prototypes
00083  ==================== */
00084 KDTREE *MakeKDTree (INT16 KeySize, PARAM_DESC KeyDesc[]);
00085 
00086 void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data); 
00087 
00088 void KDDelete (KDTREE * Tree, FLOAT32 Key[], void *Data);
00089 
00090 int KDNearestNeighborSearch (KDTREE * Tree,
00091 FLOAT32 Query[],
00092 int QuerySize,
00093 FLOAT32 MaxDistance,
00094 void *NBuffer, FLOAT32 DBuffer[]);
00095 
00096 void KDWalk(KDTREE *Tree, void_proc Action); 
00097 
00098 void FreeKDTree(KDTREE *Tree); 
00099 
00100 /* =================
00101           Private Function Prototypes
00102  ==================== */
00103 int Equal (FLOAT32 Key1[], FLOAT32 Key2[]);
00104 
00105 KDNODE *MakeKDNode (FLOAT32 Key[], char *Data, int Index);
00106 
00107 void FreeKDNode(KDNODE *Node); 
00108 
00109 void Search(int Level, KDNODE *SubTree); 
00110 
00111 FLOAT32 ComputeDistance (register int N,
00112 register PARAM_DESC Dim[],
00113 register FLOAT32 p1[], register FLOAT32 p2[]);
00114 
00115 void FindMaxDistance(); 
00116 
00117 int QueryIntersectsSearch(); 
00118 
00119 int QueryInSearch(); 
00120 
00121 void Walk(KDNODE *SubTree, INT32 Level); 
00122 
00123 void FreeSubTree(KDNODE *SubTree); 
00124 #endif

Generated on Wed Feb 28 19:49:10 2007 for Tesseract by  doxygen 1.5.1