implements a kd-tree, a multidimensional search tree for points More...

Namespaces
	blocks

	euclidean
	search implementations for a euclean metric space, distance is euclidean distance, ball is a euclidean ball

	r2_s1
	search implementations for the manifold {R}^2 S^1 , representing rigid bodies in 2d under translation and rotation

Classes
struct	ListBuilder
	Enumerates an entire subtree, building a list of nodes along with the hyperectangle bounding the subtree at that node. More...

struct	ListPair
	pairs nodes of the Kd tree along with a hyperrectangle that is the bounding volume for the subtree rooted at that node More...

class	NearestSearchIface
	Interface for nearest node type searches. More...

class	Node
	Base class for nodes in the kd tree. More...

class	RangeSearchIface

class	Traits
	example traits class, can also be used as a default if you're lazy and your problem happens to be 2d More...

class	Tree
	a simple KDtree class More...

Detailed Description

implements a kd-tree, a multidimensional search tree for points

A kd-tree is a binary space partition where each point in the tree also defines a split plane. Each split plane is axis aligned, and if a node at depth $ d $ splits along the $ i $ 'th dimension, then the nodes at depth $ d + 1 $ split along the $(i+1) \% k$ dimension.

Namespaces

Classes

Detailed Description