kdtree.h

Go to the documentation of this file.

/******************************************************************************
 ** Filename:   kdtree.h
 ** Purpose:    Definition of K-D tree access routines.
 ** Author:     Dan Johnson
 **
 ** (c) Copyright Hewlett-Packard Company, 1988.
 ** Licensed under the Apache License, Version 2.0 (the "License");
 ** you may not use this file except in compliance with the License.
 ** You may obtain a copy of the License at
 ** http://www.apache.org/licenses/LICENSE-2.0
 ** Unless required by applicable law or agreed to in writing, software
 ** distributed under the License is distributed on an "AS IS" BASIS,
 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 ** See the License for the specific language governing permissions and
 ** limitations under the License.
 *****************************************************************************/
 
#ifndef KDTREE_H
#define KDTREE_H
 
#include "ocrfeatures.h"
 
namespace tesseract {
 
struct ClusteringContext;
struct CLUSTER;
struct KDTREE;
 
using kdwalk_proc = void (*)(ClusteringContext *context, CLUSTER *Cluster, int32_t Level);
 
struct KDNODE {
  KDNODE() = default;
  KDNODE(KDTREE *tree, float key[], CLUSTER *data, int Index);
  ~KDNODE() {
    delete Left;
    delete Right;
  }
 
  float *Key;          
  CLUSTER *Data;       
  float BranchPoint;   
  float LeftBranch;    
  float RightBranch;   
  KDNODE *Left;        
  KDNODE *Right;
};
 
struct KDTREE {
  KDTREE(size_t n) : KeySize(n), KeyDesc(n) {
  }
 
  // The destructor frees all memory which is allocated to the
  // specified KD-tree.  This includes the data structure for
  // the kd-tree itself plus the data structures for each node
  // in the tree.  It does not include the Key and Data items
  // which are pointed to by the nodes.  This memory is left
  // untouched.
  ~KDTREE() {
  }
 
  // TODO: KeySize might be replaced by KeyDesc.size().
  int16_t KeySize = 0;   // number of dimensions in the tree
  KDNODE Root;           // Root.Left points to actual root node
  std::vector<PARAM_DESC> KeyDesc; // description of each dimension
};
 
inline KDNODE::KDNODE(KDTREE *tree, float key[], CLUSTER *data, int Index) {
  Key = key;
  Data = data;
  BranchPoint = Key[Index];
  LeftBranch = tree->KeyDesc[Index].Min;
  RightBranch = tree->KeyDesc[Index].Max;
  Left = nullptr;
  Right = nullptr;
}
 
/*----------------------------------------------------------------------------
            Macros
-----------------------------------------------------------------------------*/
#define RootOf(T) ((T)->Root.Left->Data)
 
/*-----------------------------------------------------------------------------
          Public Function Prototypes
-----------------------------------------------------------------------------*/
KDTREE *MakeKDTree(int16_t KeySize, const PARAM_DESC KeyDesc[]);
 
void KDStore(KDTREE *Tree, float *Key, CLUSTER *Data);
 
void KDDelete(KDTREE *Tree, float Key[], void *Data);
 
void KDNearestNeighborSearch(KDTREE *Tree, float Query[], int QuerySize, float MaxDistance,
                             int *NumberOfResults, void **NBuffer, float DBuffer[]);
 
void KDWalk(KDTREE *Tree, kdwalk_proc Action, ClusteringContext *context);
 
/*-----------------------------------------------------------------------------
          Private Function Prototypes
-----------------------------------------------------------------------------*/
 
float DistanceSquared(int k, PARAM_DESC *dim, float p1[], float p2[]);
 
TESS_API
float ComputeDistance(int k, PARAM_DESC *dim, float p1[], float p2[]);
 
int QueryInSearch(KDTREE *tree);
 
void Walk(KDTREE *tree, kdwalk_proc action, ClusteringContext *context, KDNODE *SubTree, int32_t Level);
 
void InsertNodes(KDTREE *tree, KDNODE *nodes);
 
} // namespace tesseract
 
#endif