Space-efficient geometric algorithms and data structures By Ilya Katz and Hervé Brönnimann

inplaceds Namespace Reference

Data Structures
class	kd_tree
class	explicit_tree_node
class	explicit_tree_heap
Functions
template<class RandomAccessIterator, class AxisAlignedGeometry>
void	build_static_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom)
	Builds a static kd-tree by reordering points in the range [first,last).
template<class Box, class RandomAccessIterator, class OutputIterator, class AxisAlignedGeometry>
OutputIterator	window_query_static_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, Box Q, OutputIterator result)
	Returns iterator to a collection of points within box Q.
template<class Halfplane, class RandomAccessIterator, class OutputIterator, class AxisAlignedGeometry>
OutputIterator	halfplane_query_static_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, Halfplane H, OutputIterator result)
	Returns iterator to a collection of points that lie in halfplane H.
template<class Box, class RandomAccessIterator, class OutputIterator, class AxisAlignedGeometry>
OutputIterator	closed_triangle_query_static_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, Box Q, OutputIterator result)
	Returns iterator to a collection of points within closed triangle T.
template<class RandomAccessIterator, class AxisAlignedGeometry>
void	build_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, size_t dimensions)
template<class RandomAccessIterator, class AxisAlignedGeometry>
void	build_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, size_t dimensions, size_t pointDimension)
	Builds a static multi dimentional kd-tree by reordering points in the range [first,last).
template<class RandomAccessIterator, class AxisAlignedGeometry>
void	build_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom)
	Returns true if [first, last) is a valid kd-tree data structure.
template<class RandomAccessIterator, class AxisAlignedGeometry>
void	insert_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom)
	Adds an element to the kd-tree and preserves kd-tree property. The element to be added to the kd-tree is at iterator (last-1) .
template<class Box, class RandomAccessIterator, class OutputIterator, class AxisAlignedGeometry>
OutputIterator	window_query_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, Box Q, OutputIterator result)
	Queries a kd-tree with a box query.
template<class Halfplane, class RandomAccessIterator, class OutputIterator, class AxisAlignedGeometry>
OutputIterator	halfplane_query_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator last, AxisAlignedGeometry geom, Halfplane Q, OutputIterator result)
template<class RandomAccessIterator, class AxisAlignedGeometry>
void	remove_dynamic_kdtree (RandomAccessIterator first, RandomAccessIterator pos, RandomAccessIterator last, AxisAlignedGeometry geom)
	Removes an element from the kd-tree.
template<typename Geometry>
std::ostream &	operator<< (std::ostream &os, inplaceds::explicit_tree_node< Geometry > &node)

---

Code Documentation generated Using Doxygen

Copyright © Ilya Katz and Hervé Brönnimann, 2005, 2006.