kdtree.cpp File Reference

#include "kdtree.h"
#include "cutil.h"
#include "emalloc.h"
#include <algorithm>
#include <cfloat>
#include <cstdio>
#include <cmath>

Go to the source code of this file.

Classes
class	MinK< Key, Value >
struct	MinK< Key, Value >::Element
class	KDTreeSearch

Macros
#define	Magnitude(X)   ((X) < 0 ? -(X) : (X))
#define	NodeFound(N, K, D)   (((N)->Key == (K)) && ((N)->Data == (D)))
#define	MINSEARCH   -FLT_MAX
#define	MAXSEARCH   FLT_MAX

Functions
KDTREE *	MakeKDTree (int16_t KeySize, const PARAM_DESC KeyDesc[])
void	KDStore (KDTREE *Tree, float *Key, void *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, void_proc action, void *context)
void	FreeKDTree (KDTREE *Tree)
KDNODE *	MakeKDNode (KDTREE *tree, float Key[], void *Data, int Index)
void	FreeKDNode (KDNODE *Node)
float	DistanceSquared (int k, PARAM_DESC *dim, float p1[], float p2[])
float	ComputeDistance (int k, PARAM_DESC *dim, float p1[], float p2[])
void	Walk (KDTREE *tree, void_proc action, void *context, KDNODE *sub_tree, int32_t level)
void	InsertNodes (KDTREE *tree, KDNODE *nodes)
void	FreeSubTree (KDNODE *sub_tree)

Macro Definition Documentation

Magnitude

#define Magnitude

(

X

)

((X) < 0 ? -(X) : (X))

Definition at line 30 of file kdtree.cpp.

MAXSEARCH

#define MAXSEARCH   FLT_MAX

Definition at line 37 of file kdtree.cpp.

MINSEARCH

#define MINSEARCH   -FLT_MAX

Definition at line 36 of file kdtree.cpp.

NodeFound

#define NodeFound	(		N,
			K,
			D
	)		(((N)->Key == (K)) && ((N)->Data == (D)))

Definition at line 31 of file kdtree.cpp.

Function Documentation

ComputeDistance()

float ComputeDistance	(	int	k,
		PARAM_DESC *	dim,
		float	p1[],
		float	p2[]
	)

Definition at line 450 of file kdtree.cpp.

                                                                      {
  return sqrt(DistanceSquared(k, dim, p1, p2));
}

DistanceSquared()

float DistanceSquared	(	int	k,
		PARAM_DESC *	dim,
		float	p1[],
		float	p2[]
	)

Returns the Euclidean distance squared between p1 and p2 for all essential dimensions.

Parameters

k	keys are in k-space
dim	dimension descriptions (essential, circular, etc)
p1,p2	two different points in K-D space

Definition at line 429 of file kdtree.cpp.

                                                                      {
  float total_distance = 0;

  for (; k > 0; k--, p1++, p2++, dim++) {
    if (dim->NonEssential)
      continue;

    float dimension_distance = *p1 - *p2;

    /* if this dimension is circular - check wraparound distance */
    if (dim->Circular) {
      dimension_distance = Magnitude(dimension_distance);
      float wrap_distance = dim->Max - dim->Min - dimension_distance;
      dimension_distance = std::min(dimension_distance, wrap_distance);
    }

    total_distance += dimension_distance * dimension_distance;
  }
  return total_distance;
}

FreeKDNode()

void FreeKDNode

(

KDNODE *

Node

)

Definition at line 372 of file kdtree.cpp.

{ free(Node); }

FreeKDTree()

void FreeKDTree

(

KDTREE *

Tree

)

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.

Parameters

Tree	tree data structure to be released

Returns

none

Definition at line 333 of file kdtree.cpp.

                              {
  FreeSubTree(Tree->Root.Left);
  free(Tree);
}                                /* FreeKDTree */

FreeSubTree()

void FreeSubTree

(

KDNODE *

sub_tree

)

Free all of the nodes of a sub tree.

Definition at line 534 of file kdtree.cpp.

                                   {
  if (sub_tree != nullptr) {
    FreeSubTree(sub_tree->Left);
    FreeSubTree(sub_tree->Right);
    free(sub_tree);
  }
}

InsertNodes()

void InsertNodes	(	KDTREE *	tree,
		KDNODE *	nodes
	)

Given a subtree nodes, insert all of its elements into tree.

Definition at line 524 of file kdtree.cpp.

                                              {
  if (nodes == nullptr)
    return;

  KDStore(tree, nodes->Key, nodes->Data);
  InsertNodes(tree, nodes->Left);
  InsertNodes(tree, nodes->Right);
}

KDDelete()

void KDDelete	(	KDTREE *	Tree,
		float	Key[],
		void *	Data
	)

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 tree is re-formed by removing the affected subtree and inserting all elements but the root.

Parameters

Tree	K-D tree to delete node from
Key	key of node to be deleted
Data	data contents of node to be deleted

Definition at line 254 of file kdtree.cpp.

                                                  {
  int Level;
  KDNODE *Current;
  KDNODE *Father;

  /* initialize search at root of tree */
  Father = &(Tree->Root);
  Current = Father->Left;
  Level = NextLevel(Tree, -1);

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

    Level = NextLevel(Tree, Level);
  }

  if (Current != nullptr) {         /* if node to be deleted was found */
    if (Current == Father->Left) {
      Father->Left = nullptr;
      Father->LeftBranch = Tree->KeyDesc[Level].Min;
    } else {
      Father->Right = nullptr;
      Father->RightBranch = Tree->KeyDesc[Level].Max;
    }

    InsertNodes(Tree, Current->Left);
    InsertNodes(Tree, Current->Right);
    FreeSubTree(Current);
  }
}                                /* KDDelete */

KDNearestNeighborSearch()

void KDNearestNeighborSearch	(	KDTREE *	Tree,
		float	Query[],
		int	QuerySize,
		float	MaxDistance,
		int *	NumberOfResults,
		void **	NBuffer,
		float	DBuffer[]
	)

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.

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
NumberOfResults	[out] Number of nearest neighbors actually found

Definition at line 306 of file kdtree.cpp.

                                                           {
  KDTreeSearch search(Tree, Query, QuerySize);
  search.Search(NumberOfResults, DBuffer, NBuffer);
}

KDStore()

void KDStore	(	KDTREE *	Tree,
		float *	Key,
		void *	Data
	)

This routine stores Data in the K-D tree specified by Tree using Key as an access key.

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

Definition at line 213 of file kdtree.cpp.

                                                   {
  int Level;
  KDNODE *Node;
  KDNODE **PtrToNode;

  PtrToNode = &(Tree->Root.Left);
  Node = *PtrToNode;
  Level = NextLevel(Tree, -1);
  while (Node != nullptr) {
    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 = NextLevel(Tree, Level);
    Node = *PtrToNode;
  }

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

KDWalk()

void KDWalk	(	KDTREE *	Tree,
		void_proc	action,
		void *	context
	)

Walk a given Tree with action.

Definition at line 316 of file kdtree.cpp.

                                                           {
  if (Tree->Root.Left != nullptr)
    Walk(Tree, action, context, Tree->Root.Left, NextLevel(Tree, -1));
}

MakeKDNode()

KDNODE* MakeKDNode	(	KDTREE *	tree,
		float	Key[],
		void *	Data,
		int	Index
	)

This routine allocates memory for a new K-D tree node and places the specified Key and Data into it. The left and right subtree pointers for the node are initialized to empty subtrees.

Parameters

tree	The tree to create the node for
Key	Access key for new node in KD tree
Data	ptr to data to be stored in new node
Index	index of Key to branch on

Returns

pointer to new K-D tree node

Definition at line 354 of file kdtree.cpp.

                                                                     {
  KDNODE *NewNode;

  NewNode = (KDNODE *) Emalloc (sizeof (KDNODE));

  NewNode->Key = Key;
  NewNode->Data = Data;
  NewNode->BranchPoint = Key[Index];
  NewNode->LeftBranch = tree->KeyDesc[Index].Min;
  NewNode->RightBranch = tree->KeyDesc[Index].Max;
  NewNode->Left = nullptr;
  NewNode->Right = nullptr;

  return NewNode;
}                                /* MakeKDNode */

MakeKDTree()

KDTREE* MakeKDTree	(	int16_t	KeySize,
		const PARAM_DESC	KeyDesc[]
	)

Returns

a new KDTREE based on the specified parameters.

Parameters

KeySize	# of dimensions in the K-D tree
KeyDesc	array of params to describe key dimensions

Definition at line 181 of file kdtree.cpp.

                                                                {
  KDTREE *KDTree = (KDTREE *) Emalloc(
      sizeof(KDTREE) + (KeySize - 1) * sizeof(PARAM_DESC));
  for (int 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 = nullptr;
  KDTree->Root.Right = nullptr;
  return KDTree;
}

Walk()

void Walk	(	KDTREE *	tree,
		void_proc	action,
		void *	context,
		KDNODE *	sub_tree,
		int32_t	level
	)

Walk a tree, calling action once on each node.

Operation: This routine walks through the specified sub_tree and invokes action action at each node as follows: action(context, data, level) data the data contents of the node being visited, level is the level of the node in the tree with the root being level 0.

Parameters

tree	root of the tree being walked.
action	action to be performed at every node
context	action's context
sub_tree	ptr to root of subtree to be walked
level	current level in the tree for this node

Definition at line 514 of file kdtree.cpp.

                                           {
  (*action)(context, sub_tree->Data, level);
  if (sub_tree->Left != nullptr)
    Walk(tree, action, context, sub_tree->Left, NextLevel(tree, level));
  if (sub_tree->Right != nullptr)
    Walk(tree, action, context, sub_tree->Right, NextLevel(tree, level));
}