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
AlcKDTTree *	AlcKDTTreeNew (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...

AlcKDTNode *	AlcKDTNodeNew (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...

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. More...

AlcKDTNode *	AlcKDTGetMatch (AlcKDTTree tree, void keyVal, AlcErrno *dstErr)
	Searches for a node with a matching key to the given key. More...

AlcKDTNode *	AlcKDTGetLeaf (AlcKDTTree tree, AlcKDTNode node, AlcPointP key)
	Searches for the leaf node containing the given key. progressing downwards in the tree. More...

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. 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

type	Type of tree node key.
dim	Dimension of tree (must be >= 1).
tol	Tollerance for key comparision, only used if the tree has floating point keys. If the tolerance is negative it is set to a default value.
nNodes	Expected number of nodes in the tree, 0 if unknown. This can be used to optimise node allocation.
dstErr	Destination 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().

int AlcKDTTreeFacts	(	AlcKDTTree *	tree,
		FILE *	fP
	)

Prints facts about the kD-tree structure to a file.

Returns: Number of nodes.

Parameters

tree	The KD-tree tree
fP	Output file stream.

References ALC_ER_NONE, ALC_ER_NULLPTR, ALC_POINTTYPE_INT, AlcBlockStackNew(), _AlcKDTNode::boundN, _AlcKDTNode::boundP, _AlcKDTNode::childN, _AlcKDTNode::childP, _AlcKDTTree::dim, _AlcBlockStack::elements, _AlcBlockStack::elmCnt, _AlcKDTTree::freeStack, _AlcKDTNode::idx, _AlcPointP::kD, _AlcKDTNode::key, _AlcKDTTree::keySz, _AlcPointP::kI, _AlcPointP::kV, _AlcBlockStack::maxElm, _AlcKDTTree::nNodes, _AlcKDTTree::nodeBlockSz, _AlcKDTTree::nodeStack, _AlcKDTNode::parent, _AlcKDTTree::root, _AlcKDTNode::split, _AlcKDTTree::tol, and _AlcKDTTree::type.

Referenced by AlcKDTGetNN(), and WlzGeometryTrackUpAndDown_s().

AlcErrno AlcKDTTreeFree ( AlcKDTTree * tree )

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

Returns: Error code.

Parameters

tree	The 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

tree	The KD-tree data structure.
parent	Parent node, NULL if this is the first node of the tree.
key	Key values to test agains those of the given node. (int or double) and dimension.
cmp	The sign of cmp indicates which of the parent's children the new node will become: = 0, parent == null > 0, childP < 0, childN
dstErr	Destination 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

tree	The KD-tree data structure.
node	The 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

tree	Given tree.
keyVal	Key values which must be consistent with the tree's node key type and dimension.
dstFndNod	Destination pointer for matched node, may be NULL.
dstErr	Destination 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

tree	Given tree,
keyVal	Key values which must be consistent with the tree's node key type and dimension.
dstErr	Destination 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

tree	Given tree,
node	Node to search from.
key	Key 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

tree	Given tree,
keyVal	Key values which must be consistent with the tree's node key type and dimension.
minDist	Maximum 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.
dstNNDist	Destination pointer for distance to nearest neighbour, may be NULL.
dstErr	Destination 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().

Files

Data Structures

Functions

Detailed Description

Function Documentation