Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members

rsdl_bins< N, CoordType, ValueType > Class Template Reference

#include <rsdl_bins.h>

List of all members.

Detailed Description

template<unsigned N, typename CoordType, typename ValueType>
class rsdl_bins< N, CoordType, ValueType >

N-dimensional bin structure for fast point retrieval.

This data structure stores point locations in larger bins so that neighbourhood queries can be performed efficiently by not having to consider the whole data set.

The points are of type vnl_vector_fixed<CoordType, N>. With every point is associated a value, of type ValueType.

The structure will store any point location, including those outside the range of the underlying bin storage. Such points are stored in the nearest available bin.

Location equality is performed to within a tolerance (see set_distance_tolerance). This affects get_value, for example.

Definition at line 42 of file rsdl_bins.h.

Public Types

typedef CoordType coord_type
typedef ValueType value_type
 The type of data object associated with each location.
typedef vnl_vector_fixed<
CoordType, N > 		point_type
 The location object type.
typedef rsdl_bins_bin_entry_type<
N, CoordType, ValueType > 		bin_entry_type
typedef rsdl_bins_point_dist_entry<
N, CoordType, ValueType > 		point_dist_entry
typedef vcl_vector< bin_entry_type > bin_type
 Data stored at each bin.
typedef bin_type::size_type bin_index_type
 The type of an index into the bins_ storage structure.
typedef vcl_vector< bin_index_type > bin_index_vector
 A vector of indices into the bins_ storage structure.

Public Member Functions

 rsdl_bins (point_type const &min_coord, point_type const &max_coord, point_type const &bin_sizes)
 Construct bins of size bin_sizes with enough bins to span min_coord to max_coord.
void clear ()
 Remove all points from the bins.
void set_distance_tolerance (coord_type const &tol)
 Update the tolerance used in equality checking.
void add_point (point_type const &pt, value_type const &val)
 Adds the point pt with value val.
bool get_value (point_type const &pt, value_type &val) const
 Retrieves the value at pt, if possible.
void n_nearest (point_type const &pt, unsigned n, vcl_vector< value_type > &values) const
 Return the values of the n nearest neighbours.
void n_nearest (point_type const &pt, unsigned n, vcl_vector< point_type > &points, vcl_vector< value_type > &values) const
 Return the values and locations of the n nearest neighbours.
bool is_any_point_within_radius (point_type const &pt, coord_type const &radius) const
 Check if there is at least one point within radius of pt.
void points_within_radius (point_type const &pt, coord_type const &radius, vcl_vector< value_type > &values) const
 Return values of all the points within radius of pt.
void points_within_radius (point_type const &pt, coord_type const &radius, vcl_vector< point_type > &points, vcl_vector< value_type > &values) const
 Return values and locations of all the points within radius of pt.
void points_in_bounding_box (point_type const &min_pt, point_type const &max_pt, vcl_vector< value_type > &values) const
 Return values of all the points within the bounding box.
void points_in_bounding_box (point_type const &min_pt, point_type const &max_pt, vcl_vector< point_type > &points, vcl_vector< value_type > &values) const
 Return values and locations of all the points within the bounding box.
int coord_to_bin (coord_type x, unsigned d) const
 Converts the coordinate x to a bin coordinate for dimension d.
void point_to_bin (point_type const &pt, int ind[N]) const
 Converts the point to a set of bin indices.
bin_index_type bin_index (point_type const &pt) const
 Convert the point into an index into the bin data structure bins_.
bin_index_type bin_index (int bin[N]) const
 Convert the bin coordinates into an index into the bin data structure bins_.
bin_index_vector bin_indices (point_type const &pt) const
 The list of possible bin indices that could hold pt given the current distance tolerance.
void n_nearest_impl (point_type const &pt, unsigned n, vcl_vector< value_type > &values, vcl_vector< point_type > *points) const
 Implementation of n_nearest.
void points_within_radius_impl (point_type const &pt, coord_type const &radius, vcl_vector< value_type > &values, vcl_vector< point_type > *points) const
 Implementation of points_within_radius.
void points_in_bounding_box_impl (point_type const &min_pt, point_type const &max_pt, vcl_vector< value_type > &values, vcl_vector< point_type > *points) const
 Implementation of points_in_bounding_box.
unsigned scan_region (int lo[N], int hi[N], int cur[N], unsigned dim, bin_index_vector &indices) const
 This will scan the dim dimensional region bounded by lo[dim.
unsigned scan_bdy (int lo[N], int hi[N], int cur[N], unsigned dim, bin_index_vector &indices) const
 Similar to scan_region, but will only scan the boundary of the region, not the interior.

Private Attributes

int size_ [N]
 The number of bins along each dimension.
coord_type bin_size_ [N]
 The size of the bins along each dimension.
coord_type min_pt_ [N]
 The offsets for bin(0,0,0).
coord_type dist_tol_
 Distance tolerance used to compare if two points are the same.
vcl_vector< bin_type > bins_
 Storage for all the bins.

Member Typedef Documentation

template<unsigned N, typename CoordType, typename ValueType>
typedef rsdl_bins_bin_entry_type<N,CoordType,ValueType> rsdl_bins< N, CoordType, ValueType >::bin_entry_type
 

Definition at line 146 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
typedef bin_type::size_type rsdl_bins< N, CoordType, ValueType >::bin_index_type
 

The type of an index into the bins_ storage structure.

Definition at line 159 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
typedef vcl_vector< bin_index_type > rsdl_bins< N, CoordType, ValueType >::bin_index_vector
 

A vector of indices into the bins_ storage structure.

Definition at line 164 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
typedef vcl_vector< bin_entry_type > rsdl_bins< N, CoordType, ValueType >::bin_type
 

Data stored at each bin.

Definition at line 154 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
typedef CoordType rsdl_bins< N, CoordType, ValueType >::coord_type
 

Definition at line 46 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
typedef rsdl_bins_point_dist_entry<N,CoordType,ValueType> rsdl_bins< N, CoordType, ValueType >::point_dist_entry
 

Definition at line 149 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
typedef vnl_vector_fixed<CoordType,N> rsdl_bins< N, CoordType, ValueType >::point_type
 

The location object type.

Definition at line 52 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
typedef ValueType rsdl_bins< N, CoordType, ValueType >::value_type
 

The type of data object associated with each location.

Definition at line 49 of file rsdl_bins.h.

Constructor & Destructor Documentation

template<unsigned N, typename C, typename V>
rsdl_bins< N, C, V >::rsdl_bins (  point_type const &  min_coord,
point_type const &  max_coord,
point_type const &  bin_sizes
) 
 

Construct bins of size bin_sizes with enough bins to span min_coord to max_coord.

The equality comparison tolerance is set to 0.

Definition at line 45 of file rsdl_bins.txx.

Member Function Documentation

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::add_point (  point_type const &  pt,
value_type const &  val
) 
 

Adds the point pt with value val.

Definition at line 89 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
rsdl_bins< N, C, V >::bin_index_type rsdl_bins< N, C, V >::bin_index (  int  bin[N]  )  const
 

Convert the bin coordinates into an index into the bin data structure bins_.

Definition at line 264 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
rsdl_bins< N, C, V >::bin_index_type rsdl_bins< N, C, V >::bin_index (  point_type const &  pt  )  const
 

Convert the point into an index into the bin data structure bins_.

Definition at line 241 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
rsdl_bins< N, C, V >::bin_index_vector rsdl_bins< N, C, V >::bin_indices (  point_type const &  pt  )  const
 

The list of possible bin indices that could hold pt given the current distance tolerance.

Definition at line 282 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::clear (   ) 
 

Remove all points from the bins.

Definition at line 76 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
int rsdl_bins< N, C, V >::coord_to_bin (  coord_type  x,
unsigned  d
)  const
 

Converts the coordinate x to a bin coordinate for dimension d.

Requires that min_pt_[d] and bin_size_[d] are initialized. The resulting coordinate is not necessarily within the allocated range.

Definition at line 216 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
bool rsdl_bins< N, C, V >::get_value (  point_type const &  pt,
value_type &  val
)  const
 

Retrieves the value at pt, if possible.

If a point equal to pt, to within the current tolerance, is found, val will be set to the associated value, and the function will return true. Otherwise, the function will return false.

If multiple points compare equal, one will be arbitrarily selected.

Definition at line 98 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
bool rsdl_bins< N, C, V >::is_any_point_within_radius (  point_type const &  pt,
coord_type const &  radius
)  const
 

Check if there is at least one point within radius of pt.

Definition at line 151 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::n_nearest (  point_type const &  pt,
unsigned  n,
vcl_vector< point_type > &  points,
vcl_vector< value_type > &  values
)  const
 

Return the values and locations of the n nearest neighbours.

If the structure has fewer than n points, it will return all the points stored.

Definition at line 139 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::n_nearest (  point_type const &  pt,
unsigned  n,
vcl_vector< value_type > &  values
)  const
 

Return the values of the n nearest neighbours.

If the structure has fewer than n points, it will return all the values stored.

Definition at line 128 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::n_nearest_impl (  point_type const &  pt,
unsigned  n,
vcl_vector< value_type > &  values,
vcl_vector< point_type > *  points
)  const
 

Implementation of n_nearest.

See the documentation for that.

This version will add the results to values, and, if points is not null, to points.

Definition at line 304 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::point_to_bin (  point_type const &  pt,
int  ind[N]
)  const
 

Converts the point to a set of bin indices.

Definition at line 225 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::points_in_bounding_box (  point_type const &  min_pt,
point_type const &  max_pt,
vcl_vector< point_type > &  points,
vcl_vector< value_type > &  values
)  const
 

Return values and locations of all the points within the bounding box.

The boundaries of the bounding box are included in the region searched.

Definition at line 201 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::points_in_bounding_box (  point_type const &  min_pt,
point_type const &  max_pt,
vcl_vector< value_type > &  values
)  const
 

Return values of all the points within the bounding box.

The boundaries of the bounding box are included in the region searched.

Definition at line 190 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::points_in_bounding_box_impl (  point_type const &  min_pt,
point_type const &  max_pt,
vcl_vector< value_type > &  values,
vcl_vector< point_type > *  points
)  const
 

Implementation of points_in_bounding_box.

See the documentation for that.

This version will add the results to values, and, if points is not null, to points.

Definition at line 528 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::points_within_radius (  point_type const &  pt,
coord_type const &  radius,
vcl_vector< point_type > &  points,
vcl_vector< value_type > &  values
)  const
 

Return values and locations of all the points within radius of pt.

Definition at line 178 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::points_within_radius (  point_type const &  pt,
coord_type const &  radius,
vcl_vector< value_type > &  values
)  const
 

Return values of all the points within radius of pt.

Definition at line 167 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::points_within_radius_impl (  point_type const &  pt,
coord_type const &  radius,
vcl_vector< value_type > &  values,
vcl_vector< point_type > *  points
)  const
 

Implementation of points_within_radius.

See the documentation for that.

This version will add the results to values, and, if points is not null, to points.

Definition at line 480 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
unsigned rsdl_bins< N, C, V >::scan_bdy (  int  lo[N],
int  hi[N],
int  cur[N],
unsigned  dim,
bin_index_vector &  indices
)  const
 

Similar to scan_region, but will only scan the boundary of the region, not the interior.

That is, it will scan the dim dimensional equivalent of 

      |           |
      |  +-----+  |
      |  |     |  |
      |  |     |  |
      |  +-----+  |
      |           |

Definition at line 641 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
unsigned rsdl_bins< N, C, V >::scan_region (  int  lo[N],
int  hi[N],
int  cur[N],
unsigned  dim,
bin_index_vector &  indices
)  const
 

This will scan the dim dimensional region bounded by lo[dim.

.N-1] and hi[dim..N-1], boundary points inclusive. It will return the indices of the bins that fall within the scanned region. The coordinates for the first dim-1 dimensions are given in cur.

It will add the append the bins to indices. The return value is the total number of points in the bins that were appended.

The routine will scan the dim dimensional equivalent of 

      |           |
      |           |
      |           |
      |           |
      |           |
      |           |

Definition at line 601 of file rsdl_bins.txx.

template<unsigned N, typename C, typename V>
void rsdl_bins< N, C, V >::set_distance_tolerance (  coord_type const &  tol  ) 
 

Update the tolerance used in equality checking.

Two points with Euclidean distance <= tol will compare equal.

Definition at line 67 of file rsdl_bins.txx.

Member Data Documentation

template<unsigned N, typename CoordType, typename ValueType>
coord_type rsdl_bins< N, CoordType, ValueType >::bin_size_[N] [private]
 

The size of the bins along each dimension.

Definition at line 251 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
vcl_vector< bin_type > rsdl_bins< N, CoordType, ValueType >::bins_ [private]
 

Storage for all the bins.

Definition at line 264 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
coord_type rsdl_bins< N, CoordType, ValueType >::dist_tol_ [private]
 

Distance tolerance used to compare if two points are the same.

Definition at line 260 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
coord_type rsdl_bins< N, CoordType, ValueType >::min_pt_[N] [private]
 

The offsets for bin(0,0,0).

Definition at line 255 of file rsdl_bins.h.

template<unsigned N, typename CoordType, typename ValueType>
int rsdl_bins< N, CoordType, ValueType >::size_[N] [private]
 

The number of bins along each dimension.

The numbers are ints and not unsigned ints because the logic for off-the-bottom is easier if we allow -ve indices.

Definition at line 246 of file rsdl_bins.h.

The documentation for this class was generated from the following files:
Generated on Thu Jan 10 14:49:34 2008 for contrib/rpl/rsdl by  doxygen 1.4.4