00001
00020 #ifndef KDTREE_H
00021 #define KDTREE_H
00022
00023
00024
00025
00026 #include "general.h"
00027 #include "cutil.h"
00028 #include "ocrfeatures.h"
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00045 typedef struct kdnode
00046 {
00047 FLOAT32 *Key;
00048 char *Data;
00049 FLOAT32 BranchPoint;
00050 FLOAT32 LeftBranch;
00051 FLOAT32 RightBranch;
00052 struct kdnode *Left;
00053 struct kdnode *Right;
00054 } KDNODE;
00055
00060 typedef struct
00061 {
00062 INT16 KeySize;
00063 KDNODE Root;
00064 PARAM_DESC KeyDesc[1];
00065 } KDTREE;
00066
00072 typedef enum {
00073 preorder, postorder, endorder, leaf
00074 } VISIT;
00075
00076
00077
00078
00079 #define RootOf(T) ((T)->Root.Left->Data)
00080
00081
00082
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
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