kdtree.cpp

一ＯＣＲ的相关资料。．希望对研究ＯＣＲ的朋友有所帮助．

/******************************************************************************
 **	Filename:	kdtree.c
 **	Purpose:	Routines for managing K-D search trees
 **	Author:		Dan Johnson
 **	History:	3/10/89, DSJ, Created.
 **			5/23/89, DSJ, Added circular feature capability.
 **			7/13/89, DSJ, Made tree nodes invisible to outside.
 **
 **	(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.
 ******************************************************************************/

/**----------------------------------------------------------------------------
          Include Files and Type Defines
----------------------------------------------------------------------------**/
#include "kdtree.h"
#include "const.h"
#include "emalloc.h"
#include "freelist.h"
#include <stdio.h>
#include <math.h>
#include <setjmp.h>

#define Magnitude(X)    ((X) < 0 ? -(X) : (X))
#define MIN(A,B)    ((A) < (B) ? (A) : (B))
#define NodeFound(N,K,D)  (( (N)->Key == (K) ) && ( (N)->Data == (D) ))

/**----------------------------------------------------------------------------
        Global Data Definitions and Declarations
----------------------------------------------------------------------------**/
#define MINSEARCH -MAX_FLOAT32
#define MAXSEARCH MAX_FLOAT32

static int NumberOfNeighbors;
static INT16 N;                  /* number of dimensions in the kd tree */

static FLOAT32 *QueryPoint;
static int MaxNeighbors;
static FLOAT32 Radius;
static int Furthest;
static char **Neighbor;
static FLOAT32 *Distance;

static int MaxDimension = 0;
static FLOAT32 *SBMin;
static FLOAT32 *SBMax;
static FLOAT32 *LBMin;
static FLOAT32 *LBMax;

static PARAM_DESC *KeyDesc;

static jmp_buf QuickExit;

static void_proc WalkAction;

/**----------------------------------------------------------------------------
              Public Code
----------------------------------------------------------------------------**/
/*---------------------------------------------------------------------------*/
KDTREE *
MakeKDTree (INT16 KeySize, PARAM_DESC KeyDesc[]) {
/*
 **	Parameters:
 **		KeySize		# of dimensions in the K-D tree
 **		KeyDesc		array of params to describe key dimensions
 **	Globals:
 **		MaxDimension	largest # of dimensions in any K-D tree
 **		SBMin		small search region box
 **		SBMax
 **		LBMin		large search region box
 **		LBMax
 **		Key		description of key dimensions
 **	Operation:
 **		This routine allocates and returns a new K-D tree data
 **		structure.  It also reallocates the small and large
 **		search region boxes if they are not large enough to
 **		accomodate the size of the new K-D tree.  KeyDesc is
 **		an array of key descriptors that indicate which dimensions
 **		are circular and, if they are circular, what the range is.
 **	Return:
 **		Pointer to new K-D tree
 **	Exceptions:
 **		None
 **	History:
 **		3/13/89, DSJ, Created.
 */
  int i;
  void *NewMemory;
  KDTREE *KDTree;

  if (KeySize > MaxDimension) {
    NewMemory = Emalloc (KeySize * 4 * sizeof (FLOAT32));
    if (MaxDimension > 0) {
      memfree ((char *) SBMin);
      memfree ((char *) SBMax);
      memfree ((char *) LBMin);
      memfree ((char *) LBMax);
    }
    SBMin = (FLOAT32 *) NewMemory;
    SBMax = SBMin + KeySize;
    LBMin = SBMax + KeySize;
    LBMax = LBMin + KeySize;
  }

  KDTree =
    (KDTREE *) Emalloc (sizeof (KDTREE) +
    (KeySize - 1) * sizeof (PARAM_DESC));
  for (i = 0; i < KeySize; i++) {
    KDTree->KeyDesc[i].NonEssential = KeyDesc[i].NonEssential;
    KDTree->KeyDesc[i].Circular = KeyDesc[i].Circular;
    if (KeyDesc[i].Circular) {
      KDTree->KeyDesc[i].Min = KeyDesc[i].Min;
      KDTree->KeyDesc[i].Max = KeyDesc[i].Max;
      KDTree->KeyDesc[i].Range = KeyDesc[i].Max - KeyDesc[i].Min;
      KDTree->KeyDesc[i].HalfRange = KDTree->KeyDesc[i].Range / 2;
      KDTree->KeyDesc[i].MidRange = (KeyDesc[i].Max + KeyDesc[i].Min) / 2;
    }
    else {
      KDTree->KeyDesc[i].Min = MINSEARCH;
      KDTree->KeyDesc[i].Max = MAXSEARCH;
    }
  }
  KDTree->KeySize = KeySize;
  KDTree->Root.Left = NULL;
  KDTree->Root.Right = NULL;
  return (KDTree);
}                                /* MakeKDTree */


/*---------------------------------------------------------------------------*/
void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data) { 
/*
 **	Parameters:
 **		Tree		K-D tree in which data is to be stored
 **		Key		ptr to key by which data can be retrieved
 **		Data		ptr to data to be stored in the tree
 **	Globals:
 **		N		dimension of the K-D tree
 **		KeyDesc		descriptions of tree dimensions
 **		StoreCount	debug variables for performance tests
 **		StoreUniqueCount
 **		StoreProbeCount
 **	Operation:
 **		This routine stores Data in the K-D tree specified by Tree
 **		using Key as an access key.
 **	Return: none
 **	Exceptions: none
 **	History:	3/10/89, DSJ, Created.
 **			7/13/89, DSJ, Changed return to void.
 */
  int Level;
  KDNODE *Node;
  KDNODE **PtrToNode;

  N = Tree->KeySize;
  KeyDesc = &(Tree->KeyDesc[0]);
  PtrToNode = &(Tree->Root.Left);
  Node = *PtrToNode;
  Level = 0;
  while (Node != NULL) {
    if (Key[Level] < Node->BranchPoint) {
      PtrToNode = &(Node->Left);
      if (Key[Level] > Node->LeftBranch)
        Node->LeftBranch = Key[Level];
    }
    else {
      PtrToNode = &(Node->Right);
      if (Key[Level] < Node->RightBranch)
        Node->RightBranch = Key[Level];
    }
    Level++;
    if (Level >= N)
      Level = 0;
    Node = *PtrToNode;
  }

  *PtrToNode = MakeKDNode (Key, (char *) Data, Level);
}                                /* KDStore */


/*---------------------------------------------------------------------------*/
void
KDDelete (KDTREE * Tree, FLOAT32 Key[], void *Data) {
/*
 **	Parameters:
 **		Tree		K-D tree to delete node from
 **		Key		key of node to be deleted
 **		Data		data contents of node to be deleted
 **	Globals:
 **		N		dimension of the K-D tree
 **		KeyDesc		description of each dimension
 **		DeleteCount	debug variables for performance tests
 **		DeleteProbeCount
 **	Operation:
 **		This routine deletes a node from Tree.  The node to be
 **		deleted is specified by the Key for the node and the Data
 **		contents of the node.  These two pointers must be identical
 **		to the pointers that were used for the node when it was
 **		originally stored in the tree.  A node will be deleted from
 **		the tree only if its key and data pointers are identical
 **		to Key and Data respectively.  The empty space left in the tree
 **		is filled by pulling a leaf up from the bottom of one of
 **		the subtrees of the node being deleted.  The leaf node will
 **		be pulled from left subtrees whenever possible (this was
 **		an arbitrary decision).  No attempt is made to pull the leaf
 **		from the deepest subtree (to minimize length).  The branch
 **		point for the replacement node is changed to be the same as
 **		the branch point of the deleted node.  This keeps us from
 **		having to rearrange the tree every time we delete a node.
 **		Also, the LeftBranch and RightBranch numbers of the
 **		replacement node are set to be the same as the deleted node.
 **		The makes the delete easier and more efficient, but it may
 **		make searches in the tree less efficient after many nodes are
 **		deleted.  If the node specified by Key and Data does not
 **		exist in the tree, then nothing is done.
 **	Return: none
 **		None
 **	Exceptions: none
 **		None
 **	History:	3/13/89, DSJ, Created.
 **			7/13/89, DSJ, Specify node indirectly by key and data.
 */
  int Level;
  KDNODE *Current;
  KDNODE *Father;
  KDNODE *Replacement;
  KDNODE *FatherReplacement;

  /* initialize search at root of tree */
  N = Tree->KeySize;
  KeyDesc = &(Tree->KeyDesc[0]);
  Father = &(Tree->Root);
  Current = Father->Left;
  Level = 0;

  /* search tree for node to be deleted */
  while ((Current != NULL) && (!NodeFound (Current, Key, Data))) {
    Father = Current;
    if (Key[Level] < Current->BranchPoint)
      Current = Current->Left;
    else
      Current = Current->Right;

    Level++;
    if (Level >= N)
      Level = 0;
  }

  if (Current != NULL) {         /* if node to be deleted was found */
    Replacement = Current;
    FatherReplacement = Father;

    /* search for replacement node (a leaf under node to be deleted */
    while (TRUE) {
      if (Replacement->Left != NULL) {
        FatherReplacement = Replacement;
        Replacement = Replacement->Left;
      }
      else if (Replacement->Right != NULL) {
        FatherReplacement = Replacement;
        Replacement = Replacement->Right;
      }
      else
        break;

      Level++;
      if (Level >= N)
        Level = 0;
    }

    /* compute level of replacement node's father */
    Level--;
    if (Level < 0)
      Level = N - 1;

    /* disconnect replacement node from it's father */
    if (FatherReplacement->Left == Replacement) {
      FatherReplacement->Left = NULL;
      FatherReplacement->LeftBranch = KeyDesc[Level].Min;
    }
    else {
      FatherReplacement->Right = NULL;
      FatherReplacement->RightBranch = KeyDesc[Level].Max;
    }

    /* replace deleted node with replacement (unless they are the same) */
    if (Replacement != Current) {
      Replacement->BranchPoint = Current->BranchPoint;
      Replacement->LeftBranch = Current->LeftBranch;
      Replacement->RightBranch = Current->RightBranch;
      Replacement->Left = Current->Left;
      Replacement->Right = Current->Right;

      if (Father->Left == Current)
        Father->Left = Replacement;
      else
        Father->Right = Replacement;
    }
    FreeKDNode(Current); 
  }
}                                /* KDDelete */


/*---------------------------------------------------------------------------*/
int
KDNearestNeighborSearch (KDTREE * Tree,
FLOAT32 Query[],
int QuerySize,
FLOAT32 MaxDistance,
void *NBuffer, FLOAT32 DBuffer[]) {
/*
 **	Parameters:
 **		Tree		ptr to K-D tree to be searched
 **		Query		ptr to query key (point in D-space)
 **		QuerySize	number of nearest neighbors to be found
 **		MaxDistance	all neighbors must be within this distance
 **		NBuffer		ptr to QuerySize buffer to hold nearest neighbors
 **		DBuffer		ptr to QuerySize buffer to hold distances
 **					from nearest neighbor to query point
 **	Globals:
 **		NumberOfNeighbors	# of neighbors found so far
 **		N			# of features in each key
 **		KeyDesc			description of tree dimensions
 **		QueryPoint		point in D-space to find neighbors of
 **		MaxNeighbors		maximum # of neighbors to find
 **		Radius			current distance of furthest neighbor
 **		Furthest		index of furthest neighbor
 **		Neighbor		buffer of current neighbors
 **		Distance		buffer of neighbor distances
 **		SBMin			lower extent of small search region
 **		SBMax			upper extent of small search region
 **		LBMin			lower extent of large search region
 **		LBMax			upper extent of large search region
 **		QuickExit		quick exit from recursive search
 **	Operation:
 **		This routine searches the K-D tree specified by Tree and
 **		finds the QuerySize nearest neighbors of Query.  All neighbors
 **		must be within MaxDistance of Query.  The data contents of
 **		the nearest neighbors
 **		are placed in NBuffer and their distances from Query are
 **		placed in DBuffer.
 **	Return: Number of nearest neighbors actually found
 **	Exceptions: none
 **	History:
 **		3/10/89, DSJ, Created.
 **		7/13/89, DSJ, Return contents of node instead of node itself.
 */
  int i;

  NumberOfNeighbors = 0;
  N = Tree->KeySize;
  KeyDesc = &(Tree->KeyDesc[0]);
  QueryPoint = Query;
  MaxNeighbors = QuerySize;
  Radius = MaxDistance;
  Furthest = 0;
  Neighbor = (char **) NBuffer;
  Distance = DBuffer;

  for (i = 0; i < N; i++) {
    SBMin[i] = KeyDesc[i].Min;
    SBMax[i] = KeyDesc[i].Max;
    LBMin[i] = KeyDesc[i].Min;
    LBMax[i] = KeyDesc[i].Max;
  }

  if (Tree->Root.Left != NULL) {
    if (setjmp (QuickExit) == 0)
      Search (0, Tree->Root.Left);
  }
  return (NumberOfNeighbors);
}                                /* KDNearestNeighborSearch */


/*---------------------------------------------------------------------------*/
void KDWalk(KDTREE *Tree, void_proc Action) { 
/*
 **	Parameters:
 **		Tree	ptr to K-D tree to be walked
 **		Action	ptr to function to be executed at each node
 **	Globals:
 **		WalkAction	action to be performed at every node
 **	Operation:
 **		This routine stores the desired action in a global
 **		variable and starts a recursive walk of Tree.  The walk
 **		is started at the root node.
 **	Return:
 **		None
 **	Exceptions:
 **		None
 **	History:
 **		3/13/89, DSJ, Created.
 */
  WalkAction = Action;
  if (Tree->Root.Left != NULL)
    Walk (Tree->Root.Left, 0);
}                                /* KDWalk */


/*---------------------------------------------------------------------------*/
void FreeKDTree(KDTREE *Tree) { 
/*
 **	Parameters:
 **		Tree	tree data structure to be released
 **	Globals: none
 **	Operation:
 **		This routine 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.
 **	Return: none
 **	Exceptions: none
 **	History:
 **		5/26/89, DSJ, Created.
 */
  FreeSubTree (Tree->Root.Left);
  memfree(Tree); 
}                                /* FreeKDTree */


/**----------------------------------------------------------------------------
              Private Code
----------------------------------------------------------------------------**/
/*---------------------------------------------------------------------------*/
int
Equal (FLOAT32 Key1[], FLOAT32 Key2[]) {
/*