Woolz Image Processing  Version 1.7.0
AlcKDTree

Files

file  AlcKDTree.c
 A general purpose, arbitrary dimension, integer/floating point binary space partition tree (kD-tree).
 

Data Structures

struct  _AlcKDTNode
 A node in a binary space partition tree (kD-tree). Typedef: AlcKDTNode. More...
 
struct  _AlcKDTTree
 A binary space partition tree (kD-tree). Typedef: AlcKDTTree. More...
 

Functions

AlcKDTTreeAlcKDTTreeNew (AlcPointType type, int dim, double tol, size_t nNodes, AlcErrno *dstErr)
 Creates a KD-tree data structure. More...
 
int AlcKDTTreeFacts (AlcKDTTree *tree, FILE *fP)
 Prints facts about the kD-tree structure to a file. More...
 
AlcErrno AlcKDTTreeFree (AlcKDTTree *tree)
 Free's the given KD-tree data structure and any nodes in the tree. More...
 
AlcKDTNodeAlcKDTNodeNew (AlcKDTTree *tree, AlcKDTNode *parent, AlcPointP key, int cmp, AlcErrno *dstErr)
 Allocates a new node and sets it's fields. More...
 
void AlcKDTNodeFree (AlcKDTTree *tree, AlcKDTNode *node)
 Free's the given KD-tree node and all it's child nodes by pushing them onto the stack of available nodes. More...
 
AlcKDTNodeAlcKDTInsert (AlcKDTTree *tree, void *keyVal, AlcKDTNode **dstFndNod, AlcErrno *dstErr)
 Checks for a node in the tree with the given key, if such a node doesn't exist then insert a new one. More...
 
AlcKDTNodeAlcKDTGetMatch (AlcKDTTree *tree, void *keyVal, AlcErrno *dstErr)
 Searches for a node with a matching key to the given key. More...
 
AlcKDTNodeAlcKDTGetLeaf (AlcKDTTree *tree, AlcKDTNode *node, AlcPointP key)
 Searches for the leaf node containing the given key. progressing downwards in the tree. More...
 
AlcKDTNodeAlcKDTGetNN (AlcKDTTree *tree, void *keyVal, double minDist, double *dstNNDist, AlcErrno *dstErr)
 Searches for the nearest neighbour node to the given key within the tree. More...
 

Detailed Description

Function Documentation

AlcKDTTree* AlcKDTTreeNew ( AlcPointType  type,
int  dim,
double  tol,
size_t  nNodes,
AlcErrno dstErr 
)

Creates a KD-tree data structure.

Returns
KD-tree data structure, or NULL on error.
Parameters
typeType of tree node key.
dimDimension of tree (must be >= 1).
tolTollerance for key comparision, only used if the tree has floating point keys. If the tolerance is negative it is set to a default value.
nNodesExpected number of nodes in the tree, 0 if unknown. This can be used to optimise node allocation.
dstErrDestination pointer for error code, may be NULL.

References ALC_ER_ALLOC, ALC_ER_NONE, ALC_ER_PARAM, ALC_POINTTYPE_DBL, ALC_POINTTYPE_INT, AlcCalloc(), _AlcKDTTree::dim, _AlcKDTTree::keySz, _AlcKDTTree::nodeBlockSz, _AlcKDTTree::tol, and _AlcKDTTree::type.

Referenced by AlcKDTGetNN(), WlzPointsFromDomObj(), WlzScalarFeatures2D(), WlzSnapFit(), and WlzVerticesBuildTree().

AlcErrno AlcKDTTreeFree ( AlcKDTTree tree)

Free's the given KD-tree data structure and any nodes in the tree.

Returns
Error code.
Parameters
treeThe KD-tree data structure.

References ALC_ER_NONE, AlcBlockStackFree(), AlcFree(), and _AlcKDTTree::freeStack.

Referenced by AlcKDTGetNN(), WlzDistMetricDirVertex2D(), WlzDistMetricDirVertex3D(), WlzMatchICPCtr(), WlzPointsFromDomObj(), WlzScalarFeatures2D(), and WlzSnapFit().

AlcKDTNode* AlcKDTNodeNew ( AlcKDTTree tree,
AlcKDTNode parent,
AlcPointP  key,
int  cmp,
AlcErrno dstErr 
)

Allocates a new node and sets it's fields.

Returns
New node, NULL on error.
Parameters
treeThe KD-tree data structure.
parentParent node, NULL if this is the first node of the tree.
keyKey values to test agains those of the given node. (int or double) and dimension.
cmpThe sign of cmp indicates which of the parent's children the new node will become:
  • = 0, parent == null
  • > 0, childP
  • < 0, childN
dstErrDestination pointer for error code, may be NULL.

References ALC_ER_NONE, ALC_POINTTYPE_INT, _AlcKDTNode::boundN, _AlcKDTNode::boundP, _AlcKDTNode::childN, _AlcKDTNode::childP, _AlcKDTTree::dim, _AlcKDTNode::idx, _AlcPointP::kD, _AlcKDTNode::key, _AlcPointP::kI, _AlcKDTTree::nNodes, _AlcKDTTree::nodeStack, _AlcKDTNode::parent, _AlcKDTNode::split, and _AlcKDTTree::type.

Referenced by AlcKDTInsert().

void AlcKDTNodeFree ( AlcKDTTree tree,
AlcKDTNode node 
)

Free's the given KD-tree node and all it's child nodes by pushing them onto the stack of available nodes.

Returns
void
Parameters
treeThe KD-tree data structure.
nodeThe KD-tree node data structure.

References _AlcKDTNode::childN, _AlcKDTNode::childP, and _AlcKDTTree::nodeStack.

AlcKDTNode* AlcKDTInsert ( AlcKDTTree tree,
void *  keyVal,
AlcKDTNode **  dstFndNod,
AlcErrno dstErr 
)

Checks for a node in the tree with the given key, if such a node doesn't exist then insert a new one.

Returns
New node added to tree, NULL on error or if key matched in tree.
Parameters
treeGiven tree.
keyValKey values which must be consistent with the tree's node key type and dimension.
dstFndNodDestination pointer for matched node, may be NULL.
dstErrDestination pointer for error code, may be NULL.

References ALC_ER_NONE, ALC_ER_NULLPTR, AlcKDTNodeNew(), _AlcKDTNode::childN, _AlcKDTNode::childP, _AlcPointP::kV, and _AlcKDTTree::root.

Referenced by AlcKDTGetNN(), WlzPointsFromDomObj(), WlzScalarFeatures2D(), WlzSnapFit(), and WlzVerticesBuildTree().

AlcKDTNode* AlcKDTGetMatch ( AlcKDTTree tree,
void *  keyVal,
AlcErrno dstErr 
)

Searches for a node with a matching key to the given key.

Returns
Matched node in tree, NULL on error or if key not matched.
Parameters
treeGiven tree,
keyValKey values which must be consistent with the tree's node key type and dimension.
dstErrDestination pointer for error code, may be NULL.

References ALC_ER_NONE, ALC_ER_NULLPTR, _AlcKDTNode::childN, _AlcKDTNode::childP, _AlcPointP::kV, and _AlcKDTTree::root.

AlcKDTNode* AlcKDTGetLeaf ( AlcKDTTree tree,
AlcKDTNode node,
AlcPointP  key 
)

Searches for the leaf node containing the given key. progressing downwards in the tree.

Returns
Leaf node containing the given
                            key or NULL if tree has no nodes.
Parameters
treeGiven tree,
nodeNode to search from.
keyKey values which must be consistent with the tree's node key type and dimension.

References _AlcKDTNode::childN, and _AlcKDTNode::childP.

Referenced by AlcKDTGetNN().

AlcKDTNode* AlcKDTGetNN ( AlcKDTTree tree,
void *  keyVal,
double  minDist,
double *  dstNNDist,
AlcErrno dstErr 
)

Searches for the nearest neighbour node to the given key within the tree.

Returns
Nearest neighbour node in tree, NULL on error or if
    tree has no nodes.
Parameters
treeGiven tree,
keyValKey values which must be consistent with the tree's node key type and dimension.
minDistMaximum distance between given key and the nearest neighbour, any node at a greater distance is not a nearest neighbour. Confusingly used for the minimum key-node distance found.
dstNNDistDestination pointer for distance to nearest neighbour, may be NULL.
dstErrDestination pointer for error code, may be NULL.

References ALC_ER_NONE, ALC_ER_NULLPTR, ALC_POINTTYPE_DBL, ALC_POINTTYPE_INT, AlcKDTGetLeaf(), AlcKDTInsert(), AlcKDTTreeFacts(), AlcKDTTreeFree(), AlcKDTTreeNew(), _AlcKDTNode::boundN, _AlcKDTNode::boundP, _AlcKDTNode::childN, _AlcKDTNode::childP, _AlcKDTTree::dim, _AlcPointP::kD, _AlcKDTNode::key, _AlcPointP::kI, _AlcPointP::kV, main(), _AlcKDTNode::parent, _AlcKDTTree::root, _AlcKDTNode::split, _AlcKDTTree::tol, and _AlcKDTTree::type.

Referenced by WlzDistMetricDirVertex2D(), WlzDistMetricDirVertex3D(), WlzGeometryTrackUpAndDown_s(), WlzMatchICPWeightMatches(), WlzPointsFromDomObj(), WlzRegICPTreeAndVertices(), WlzRegICPVerticesWSD2D(), WlzScalarFeatures2D(), and WlzSnapFit().