kd_tree.h File Reference

Detailed Description

Author

hacatu

Version

0.3.0 KD trees are a way to store spatially organized data (tagged points on a sphere, tagged points in a 2D rectangle, tagged points in a 3D cuboid, etc).

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

Definition in file kd_tree.h.

Go to the source code of this file.

Data Structures
struct	cr8r_kd_ft
	Function table for kd tree, see cr8r_kd_ft. More...
struct	cr8r_kdwin_s2i64
	Concrete bounds object for spherical and cuboid kd trees with 3 i64 coords. More...
struct	cr8r_kd_k_closest_state
	Additional state for . More...

Typedefs
typedef cr8r_walk_decision(*	cr8r_kdvisitor) (cr8r_kd_ft *ft, const void *win, void *ent, void *data)
	Type of a visitor callback for a kd tree traversal. More...

Functions
bool	cr8r_kdwin_init_s2i64 (cr8r_kdwin_s2i64 *, const int64_t bl[3], const int64_t tr[3])
	Initialize a i64x3 bounds object with a given "bottom left" and "top right" point.
bool	cr8r_kdwin_init_c3i64 (cr8r_kdwin_s2i64 *, const int64_t bl[3], const int64_t tr[3])
	Initialize a i64x3 bounds object with a given "bottom left" and "top right" point.
bool	cr8r_kdwin_bounding_i64x3 (cr8r_kdwin_s2i64 *, const cr8r_vec *ents, const cr8r_kd_ft *ft)
	Initialize a i64x3 bounds object with the "bottom left" and "top right" points bounding a list of points.
bool	cr8r_kd_ify (cr8r_vec *, cr8r_kd_ft *ft, uint64_t a, uint64_t b)
	Rearrange a vector of points into a kd tree. More...
void	cr8r_kd_walk (cr8r_vec *, const cr8r_kd_ft *ft, const void *bounds, cr8r_kdvisitor visitor, void *data)
	Perform a preorder traversal of the points in a kd tree and call a visitor callback on each. More...
bool	cr8r_kd_k_closest (cr8r_vec *, cr8r_kd_ft *ft, const void *bounds, const void *pt, uint64_t k, cr8r_vec *out)
	Find the k closest points to a given point. More...
int	cr8r_default_cmp_kd_kcs_pt_dist (const cr8r_base_ft *_ft, const void *a, const void *b)
	Comparison function that compares two kd tree points based on their distance from a fixed point. More...

Variables
cr8r_kd_ft	cr8r_kdft_s2i64
	kdft implementation for spherical kd trees in 3 dimensions with i64 coordinates
cr8r_kd_ft	cr8r_kdft_c3i64
	kdft implementation for cuboid kd trees in 3 dimensions with i64 coordintates

Typedef Documentation

cr8r_kdvisitor

typedef cr8r_walk_decision(* cr8r_kdvisitor) (cr8r_kd_ft *ft, const void *win, void *ent, void *data)

Type of a visitor callback for a kd tree traversal.

f(cr8r_kd_ft *ft, const void *win, void *ent, void *data) where the arguments are the kd tree function table, bounds of the subtree rooted at ent, current node, and reentrant data respectively

Definition at line 111 of file kd_tree.h.

Function Documentation

cr8r_kd_ify()

bool cr8r_kd_ify	(	cr8r_vec *	,
		cr8r_kd_ft *	ft,
		uint64_t	a,
		uint64_t	b
	)

Rearrange a vector of points into a kd tree.

The middle point in the array will be the median in the first dimension, with all points to the left being to the "left" in the first dimension and all points to the right being to the "right" in the first dimension. Then within the left/right subarray (subtree), the middle point is the median in the second dimension and so on.

Parameters

[in]	ft	(uint64_t)ft->super.base.data is interpreted as the depth of the current subarray, and so should be zero when calling this function generally on the whole vector
[in]	a,b	the start (inclusive) and end (exclusive) indices of the subarray to process. Should be 0, self->len to treeify the entire vector.

cr8r_kd_walk()

void cr8r_kd_walk	(	cr8r_vec *	,
		const cr8r_kd_ft *	ft,
		const void *	bounds,
		cr8r_kdvisitor	visitor,
		void *	data
	)

Perform a preorder traversal of the points in a kd tree and call a visitor callback on each.

Parameters

[in]	ft	(uint64_t)ft->super.base.data is interpreted as the depth of the current subarray, and so should be zero when calling this function generally on the whole vector
[in]	bounds	the bounds of the tree
[in]	visitor	function to call at each entry in the tree
[in,out]	data	passed to visitor to facillitate input/output

cr8r_kd_k_closest()

bool cr8r_kd_k_closest	(	cr8r_vec *	,
		cr8r_kd_ft *	ft,
		const void *	bounds,
		const void *	pt,
		uint64_t	k,
		cr8r_vec *	out
	)

Find the k closest points to a given point.

The output vec MUST be initialized (cr8r_vec_init), but will be cr8r_vec_clear'd.

Parameters

[in]	ft	(uint64_t)_ft->super.base.data is interpreted as the depth of the current subarray, and so should be zero when calling this function generally on the whole vector
[in]	bounds	the bounds of the tree
[in]	pt	point to find k closest points to. Note that if pt is in the tree, it will be returned. If there is a tie for the kth closest point, the list of the k closest points may contain any of the tied points, but will always contain exactly k unless there are fewer than k entries in the tree.
[in]	k	the number of points to find
[out]	out	vector where the k closest points will be stored. Must be allocated but will be cleared before use. The output is in no specified order (the current implementation unsurprisingly places them in a minmax heap order

Returns

true on success, false on (allocation) failure. Will not allocate if out->cap >= k + 1 already, but may return fewer than k points if fewer than k are available

cr8r_default_cmp_kd_kcs_pt_dist()

int cr8r_default_cmp_kd_kcs_pt_dist	(	const cr8r_base_ft *	_ft,
		const void *	a,
		const void *	b
	)

Comparison function that compares two kd tree points based on their distance from a fixed point.

This function MUST be called with _ft pointing at a cr8r_base_ft WITHIN cr8r_kd_k_closest_state. See the implementation of cr8r_kd_k_closest for more details. This function will only read from the pt field of the cr8r_kd_k_closest_state struct.