#include <KDGrid_fwd.hpp>

Detailed Description

template<typename vec_t>
class mm::KDGrid< vec_t >

Search structure over given d-dimensional box with given cell size.

At most one point per cell can be stored. This is often a faster and more memory hungry substitute for KDTree.

Usage example:

    KDGrid<Vec2d> search(0, 1, 0.1);
    search.insert(Vec2d(0, 0));
    if (search.existsPointInSphere(0.0, 1.0)) {
        // do sth ...
    }
    std::cout << search << std::endl;

See also: GeneralFill, KDTreeMutable

Definition at line 29 of file KDGrid_fwd.hpp.

Collaboration diagram for mm::KDGrid< vec_t >:

Public Member Functions
	KDGrid (const vec_t &bot, const vec_t &top, scalar_t cell_size)
	Construct a search grid from `bot` to `top` with given `cell_size`. More...

const vec_t &	bottom () const
	Get bottom bound. More...

const vec_t &	top () const
	Get top bound. More...

scalar_t	cellSize () const
	Get cell size. More...

const Grid< int, dim > &	grid () const
	Get access to underlying grid of point indices. More...

const std::vector< vec_t > &	points () const
	Get access to array of stored points. More...

const vec_t &	point (int idx) const
	Get point by its sequential index. More...

int	size () const
	Get number of points stored in the structure. More...

int	insert (const vec_t &p)
	Insert a new point in the structure. More...

void	insert (const std::vector< vec_t > &pts)
	Vectorised version of insert. More...

bool	existsPointInSphere (const vec_t &p, scalar_t r)
	Check if any point exists in sphere centered at `p` with radius `r`. More...

Public Types
enum	{ dim = vec_t::dim }
	Store dimension of the space. More...

typedef vec_t	vector_t
	Vector type used. More...

typedef vector_t::scalar_t	scalar_t
	Scalar type used. More...

Friends
template<typename V >
std::ostream &	operator<< (std::ostream &os, const KDGrid< V > &search)
	Output some information about the search grid. More...

Private Types
typedef Grid< int, dim >::IndexArray	IndexArray
	Multi-index type. More...

Private Member Functions
IndexArray	compute_index (const vec_t &p)
	Compute point multi-index. More...

bool	existsPointInSphere (const vec_t &p, scalar_t r, const IndexArray &index)
	Implementation of existsPointInSphere. More...

int	insert (const vec_t &p, const IndexArray &index)
	Implementation of insert. More...

bool	increment (IndexArray &cur, int span, const IndexArray &ref)
	Increment a dim-ary counter. More...

Static Private Member Functions
static IndexArray	compute_size (const vec_t &bot, const vec_t &top, scalar_t cell_size)
	Compute the sizes of the rid along each dimension. More...

Private Attributes
vec_t	bot_
	Lower bound of the box. More...

vec_t	top_
	Upper bound of the box. More...

scalar_t	cell_size_
	Size of a single cell. More...

Grid< int, dim >	grid_
	Background grid of cells pointing to sequential point indices. More...

std::vector< vec_t >	points_
	List of inserted points. More...

Member Enumeration Documentation

◆ anonymous enum

template<typename vec_t >

anonymous enum

Store dimension of the space.

Enumerator
dim	Dimensionality of the space.

Definition at line 34 of file KDGrid_fwd.hpp.

Constructor & Destructor Documentation

◆ KDGrid()

template<typename vec_t >

mm::KDGrid< vec_t >::KDGrid	(	const vec_t &	bot,
		const vec_t &	top,
		scalar_t	cell_size
	)

inline

Construct a search grid from bot to top with given cell_size.

Definition at line 46 of file KDGrid_fwd.hpp.

Member Function Documentation

◆ bottom()

template<typename vec_t >

const vec_t& mm::KDGrid< vec_t >::bottom ( ) const

inline

Get bottom bound.

Definition at line 52 of file KDGrid_fwd.hpp.

◆ cellSize()

template<typename vec_t >

scalar_t mm::KDGrid< vec_t >::cellSize ( ) const

inline

Get cell size.

Definition at line 56 of file KDGrid_fwd.hpp.

◆ compute_index()

template<typename vec_t >

KDGrid< vec_t >::IndexArray mm::KDGrid< vec_t >::compute_index ( const vec_t & p )

private

Compute point multi-index.

Definition at line 70 of file KDGrid.hpp.

◆ compute_size()

template<typename vec_t >

KDGrid< vec_t >::IndexArray mm::KDGrid< vec_t >::compute_size	(	const vec_t &	bot,
		const vec_t &	top,
		scalar_t	cell_size
	)

staticprivate

Compute the sizes of the rid along each dimension.

Definition at line 19 of file KDGrid.hpp.

◆ existsPointInSphere() [1/2]

template<typename vec_t >

bool mm::KDGrid< vec_t >::existsPointInSphere	(	const vec_t &	p,
		scalar_t	r
	)

inline

Check if any point exists in sphere centered at p with radius r.

Definition at line 81 of file KDGrid_fwd.hpp.

◆ existsPointInSphere() [2/2]

template<typename vec_t >

bool mm::KDGrid< vec_t >::existsPointInSphere	(	const vec_t &	p,
		scalar_t	r,
		const IndexArray &	index
	)

private

Implementation of existsPointInSphere.

Definition at line 53 of file KDGrid.hpp.

◆ grid()

template<typename vec_t >

const Grid<int, dim>& mm::KDGrid< vec_t >::grid ( ) const

inline

Get access to underlying grid of point indices.

Definition at line 58 of file KDGrid_fwd.hpp.

◆ increment()

template<typename vec_t >

bool mm::KDGrid< vec_t >::increment	(	KDGrid< vec_t >::IndexArray &	cur,
		int	span,
		const IndexArray &	ref
	)

private

Increment a dim-ary counter.

Definition at line 29 of file KDGrid.hpp.

◆ insert() [1/3]

template<typename vec_t >

void mm::KDGrid< vec_t >::insert ( const std::vector< vec_t > & pts )

inline

Vectorised version of insert.

Definition at line 76 of file KDGrid_fwd.hpp.

◆ insert() [2/3]

template<typename vec_t >

int mm::KDGrid< vec_t >::insert ( const vec_t & p )

inline

Insert a new point in the structure.

Parameters

p	The point to insert.

Returns: Sequential index of the point.

Exceptions

Assertion fails if there is also point in this cell or if the point is out of range.

Definition at line 73 of file KDGrid_fwd.hpp.

◆ insert() [3/3]

template<typename vec_t >

int mm::KDGrid< vec_t >::insert	(	const vec_t &	p,
		const IndexArray &	index
	)

private

Implementation of insert.

Definition at line 42 of file KDGrid.hpp.

◆ point()

template<typename vec_t >

const vec_t& mm::KDGrid< vec_t >::point ( int idx ) const

inline

Get point by its sequential index.

Definition at line 62 of file KDGrid_fwd.hpp.

◆ points()

template<typename vec_t >

const std::vector<vec_t>& mm::KDGrid< vec_t >::points ( ) const

inline

Get access to array of stored points.

Definition at line 60 of file KDGrid_fwd.hpp.

◆ size()

template<typename vec_t >

int mm::KDGrid< vec_t >::size ( ) const

inline

Get number of points stored in the structure.

Definition at line 65 of file KDGrid_fwd.hpp.

◆ top()

template<typename vec_t >

const vec_t& mm::KDGrid< vec_t >::top ( ) const

inline

Get top bound.

Definition at line 54 of file KDGrid_fwd.hpp.

Friends And Related Function Documentation

◆ operator<<

template<typename vec_t >

template<typename V >

std::ostream& operator<<	(	std::ostream &	os,
		const KDGrid< V > &	search
	)

friend

Output some information about the search grid.

Member Data Documentation

◆ bot_

template<typename vec_t >

vec_t mm::KDGrid< vec_t >::bot_

private

Lower bound of the box.

Definition at line 37 of file KDGrid_fwd.hpp.

◆ cell_size_

template<typename vec_t >

scalar_t mm::KDGrid< vec_t >::cell_size_

private

Size of a single cell.

Definition at line 39 of file KDGrid_fwd.hpp.

◆ grid_

template<typename vec_t >

Grid<int, dim> mm::KDGrid< vec_t >::grid_

private

Background grid of cells pointing to sequential point indices.

Definition at line 40 of file KDGrid_fwd.hpp.

◆ points_

template<typename vec_t >

std::vector<vec_t> mm::KDGrid< vec_t >::points_

private

List of inserted points.

Definition at line 41 of file KDGrid_fwd.hpp.

◆ top_

template<typename vec_t >

vec_t mm::KDGrid< vec_t >::top_

private

Upper bound of the box.

Definition at line 38 of file KDGrid_fwd.hpp.

The documentation for this class was generated from the following files:

include/medusa/bits/spatial_search/KDGrid_fwd.hpp
include/medusa/bits/spatial_search/KDGrid.hpp

Detailed Description

template<typename vec_t> class mm::KDGrid< vec_t >

Public Member Functions

Public Types

Friends

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ KDGrid()

Member Function Documentation

◆ bottom()

◆ cellSize()

◆ compute_index()

◆ compute_size()

◆ existsPointInSphere() [1/2]

◆ existsPointInSphere() [2/2]

◆ grid()

◆ increment()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ point()

◆ points()

◆ size()

◆ top()

Friends And Related Function Documentation

◆ operator<<

Member Data Documentation

◆ bot_

◆ cell_size_

◆ grid_

◆ points_

◆ top_

template<typename vec_t>
class mm::KDGrid< vec_t >