mtree.h File Reference

Support for M-trees. More...

#include "../voxvision.h"

Go to the source code of this file.

Data Structures
struct	vox_sphere
	Sphere structure. More...

Functions
VOX_EXPORT int	vox_mtree_add_sphere (struct vox_mtree_node **nodeptr, const struct vox_sphere *s)
	Add a sphere to an M-tree. More...
VOX_EXPORT int	vox_mtree_remove_sphere (struct vox_mtree_node **nodeptr, const struct vox_sphere *s)
	Remove sphere from a tree. More...
VOX_EXPORT void	vox_mtree_destroy (struct vox_mtree_node *node)
	Destroy a tree, freeing all used space.
VOX_EXPORT void	vox_mtree_dump (const struct vox_mtree_node *node)
	Dump a tree to stdout. More...
VOX_EXPORT unsigned int	vox_mtree_items (const struct vox_mtree_node *node)
	Get a number of items (spheres) in M-tree.
VOX_EXPORT const struct vox_mtree_node *	vox_mtree_contains_sphere (const struct vox_mtree_node *node, const struct vox_sphere *s)
	Check if a sphere is in a tree. More...
VOX_EXPORT void	vox_mtree_spheres_containing (const struct vox_mtree_node *node, const vox_dot dot, void(^block)(const struct vox_sphere *s))
	Do a job for all spheres which contain a specific dot. More...
VOX_EXPORT void	vox_mtree_spheres_containing_f (const struct vox_mtree_node *node, const vox_dot dot, void(*callback)(const struct vox_sphere *s, void *arg), void *thunk)
	Callback-styled version of vox_mtree_spheres_containing(). More...

Detailed Description

Support for M-trees.

I decided to expose the M-tree related header to user, but it is not useful for anything now.

Function Documentation

vox_mtree_add_sphere()

VOX_EXPORT int vox_mtree_add_sphere	(	struct vox_mtree_node **	nodeptr,
		const struct vox_sphere *	s
	)

Add a sphere to an M-tree.

Inserts a sphere to an M-tree. If the new root is created for that tree, it will be set to a place nodeptr points to. Note that implementation cannot handle cases with different spheres having the same center.

Parameters

nodeptr	Pointer to a root node
s	Sphere to be inserted. Once sphere is added to a tree, it is no more needed by the library, so you can reclaim space used by it (or allocate sphere on stack).

Returns

1 On success (sphere was not in a tree) or 0 otherwise.

vox_mtree_contains_sphere()

VOX_EXPORT const struct vox_mtree_node* vox_mtree_contains_sphere	(	const struct vox_mtree_node *	node,
		const struct vox_sphere *	s
	)

Check if a sphere is in a tree.

Note that only center and radius fields are used for the check.

Returns

A leaf of the tree in which sphere is contained.

vox_mtree_dump()

VOX_EXPORT void vox_mtree_dump

(

const struct vox_mtree_node *

node

)

Dump a tree to stdout.

Use carefully as it may produce very long output.

vox_mtree_remove_sphere()

VOX_EXPORT int vox_mtree_remove_sphere	(	struct vox_mtree_node **	nodeptr,
		const struct vox_sphere *	s
	)

Remove sphere from a tree.

Removes a sphere from a tree, possibly leaving the tree unbalanced. If the resulting tree is empty, NULL is stored to a place nodeptr points to.

Parameters

nodeptr	Pointer to a root node
s	Sphere to be inserted. Once sphere is added to a tree, it is no more needed by the library, so you can reclaim space used by it (or allocate sphere on stack).

Returns

1 On success (sphere was in a tree) or 0 otherwise.

vox_mtree_spheres_containing()

VOX_EXPORT void vox_mtree_spheres_containing	(	const struct vox_mtree_node *	node,
		const vox_dot	dot,
		void(^)(const struct vox_sphere *s)	block
	)

Do a job for all spheres which contain a specific dot.

Parameters

node	A pointer to an M-tree root node.
dot	A dot for which search is performed.
block	A piece of work to do given as a C block. This block accepts a sphere to which the dot belongs to.

vox_mtree_spheres_containing_f()

VOX_EXPORT void vox_mtree_spheres_containing_f	(	const struct vox_mtree_node *	node,
		const vox_dot	dot,
		void(*)(const struct vox_sphere *s, void *arg)	callback,
		void *	thunk
	)

Callback-styled version of vox_mtree_spheres_containing().

In this version, instead of a block, a callback must be supplied. The callback accepts a sphere as the first argument (with the same meaning as for vox_mtree_spheres_containing()). Also it accepts a second argument, arg which can hold arbitrary user-defined data.

Parameters

node	A pointer to an M-tree root node.
dot	A dot for which search is performed.
callback	A piece of work to do given as a callback.
thunk	Some arbitrary userdata which is passed to the callback as the second argument, unchanged.