Public Member Functions | Private Attributes
mbl_clusters< T, D > Class Template Reference

Class to record clusters of data, for faster neighbour finding. More...

#include <mbl_clusters.h>

List of all members.

Public Member Functions

 mbl_clusters ()
 Default constructor.
void empty ()
 Empty clusters.
void set_max_r (double r)
 Define maximum radius for each cluster.
void set_data (const vcl_vector< T > &data)
 Define external data array (pointer retained).
void set_data_ptr (const vcl_vector< T > &data)
 Define external data array (pointer retained).
const vcl_vector< T > & data () const
 External list of objects.
double max_r () const
 Maximum radius for any cluster.
const vcl_vector< T > & p () const
 Cluster key points.
unsigned n_clusters () const
 Number of clusters.
const vcl_vector< double > & r () const
 Furthest distance of a cluster object from key point for cluster.
const vcl_vector< vcl_vector
< unsigned > > & 
index () const
 Indices of objects associated with each cluster.
void set_r (unsigned i, double r)
 Set given radius.
unsigned nearest (const T &t, double &d) const
 Return index of nearest object in data() to t.
unsigned nearest (const T &t, double &d, const vcl_vector< unsigned > &c_list) const
 Return index of nearest object in data() to t.
unsigned nearest_cluster (const T &t, double &d) const
 Return index of nearest cluster in data() to t.
void nearest_clusters (const T &t, double &max_d, vcl_vector< unsigned > &near_c) const
 Return indices of clusters which may contain nearest point to t.
void nearest_clusters (const T &t, double &max_d, const vcl_vector< unsigned > &c_list, vcl_vector< unsigned > &near_c) const
 Return indices of clusters which may contain nearest point to t.
unsigned add_object (unsigned i, double r=0.0)
 Append new object with index i and assign to a cluster.
unsigned create_cluster (unsigned i, double r=0.0)
 Create a new cluster around point data()[i].
void assign_to_cluster (unsigned i, unsigned ci, double r)
 Assign object data()[i] to cluster ci, knowing distance r.
unsigned clusters_within_d (const T &t, double d, vcl_vector< unsigned > &c_list, unsigned &nearest_c, double &min_d)
 Finds list of clusters whose keypoint is within d of t.
unsigned clusters_within_max_r (const T &t, vcl_vector< unsigned > &c_list, unsigned &nearest_c, double &min_d)
 Finds list of clusters whose keypoint is within max_r of t.
unsigned clusters_within_d (const T &t, double d, const vcl_vector< unsigned > &in_list, vcl_vector< unsigned > &c_list, unsigned &nearest_c, double &min_d)
 Finds list of clusters whose keypoint is within d of t.
unsigned clusters_within_max_r (const T &t, const vcl_vector< unsigned > &in_list, vcl_vector< unsigned > &c_list, unsigned &nearest_c, double &min_d)
 Finds list of clusters whose keypoint is within max_r of t.
void in_clusters (const vcl_vector< unsigned > &c_list, vcl_vector< unsigned > &o_list) const
 Create list of object indices in listed clusters.
void print_cluster_sets (vcl_ostream &os) const
 Write out list of elements in each cluster.
short version_no () const
 Version number for I/O.
void print_summary (vcl_ostream &os) const
 Print class to os.
void b_write (vsl_b_ostream &bfs) const
 Save class to binary file stream.
void b_read (vsl_b_istream &bfs)
 Load class from binary file stream.

Private Attributes

const vcl_vector< T > * data_
 Pointer to external list of objects.
vcl_vector< T > p_
 Cluster key point.
double max_r_
 Maximum radius for any cluster.
vcl_vector< vcl_vector
< unsigned > > 
index_
 Indices of objects associated with each cluster.
vcl_vector< double > r_
 Furthest distance of a cluster object from key point for cluster.

Detailed Description

template<class T, class D>
class mbl_clusters< T, D >

Class to record clusters of data, for faster neighbour finding.

Used to record clusters of objects of type T. D::d(T t1, T t2) is a measure of distance between two objects. It must obey the triangle inequality: D::d(t1,t2)<=D::d(t1,t3)+D::d(t2,t3).

Pointer retained to an external vector of objects. The class is designed to allow fast location of the nearest of the external objects to a given new object. It represents the data as a set of key point positions, together with a list of indices into the external data for each cluster.

Thus to find the nearest neighbour, we first check for proximity to the keypoints, and only consider objects in the clusters which are sufficiently close.

Definition at line 28 of file mbl_clusters.h.


Constructor & Destructor Documentation

template<class T , class D >
mbl_clusters< T, D >::mbl_clusters ( )

Default constructor.

Definition at line 21 of file mbl_clusters.txx.


Member Function Documentation

template<class T , class D >
unsigned mbl_clusters< T, D >::add_object ( unsigned  new_i,
double  r = 0.0 
)

Append new object with index i and assign to a cluster.

Assumes that new object data()[i] is available. Deduce which cluster it belongs to and add it. Create new cluster if further than max_r() from any. r is the radius associated with data()[i], which is zero for a single point, but non-zero when the point is itself a key point for a cluster (eg in mbl_cluster_tree) Return index of cluster it is assigned to

Assumes that new object data()[i] is available. Deduce which cluster it belongs to and add it. Create new cluster if further than max_r() from any. Return index of cluster it is assigned to

Definition at line 245 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::assign_to_cluster ( unsigned  i,
unsigned  ci,
double  r 
)

Assign object data()[i] to cluster ci, knowing distance r.

r is the distance D::d(data()[i],p()[ci])

Definition at line 270 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::b_read ( vsl_b_istream bfs)

Load class from binary file stream.

Warning: Does not load or link external data - that must be recorded separately, then connected using set_data_ptr()

Definition at line 410 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::b_write ( vsl_b_ostream bfs) const

Save class to binary file stream.

Warning: Does not save external data - that must be recorded separately.

Definition at line 400 of file mbl_clusters.txx.

template<class T , class D >
unsigned mbl_clusters< T, D >::clusters_within_d ( const T &  t,
double  d,
vcl_vector< unsigned > &  c_list,
unsigned &  nearest_c,
double &  min_d 
)

Finds list of clusters whose keypoint is within d of t.

Returns number of such clusters. If >0, then nearest_c gives index of cluster with centre nearest to t

Definition at line 288 of file mbl_clusters.txx.

template<class T , class D >
unsigned mbl_clusters< T, D >::clusters_within_d ( const T &  t,
double  d,
const vcl_vector< unsigned > &  in_list,
vcl_vector< unsigned > &  c_list,
unsigned &  nearest_c,
double &  min_d 
)

Finds list of clusters whose keypoint is within d of t.

Only considers subset of clusters listed in in_list Returns number of such clusters. If >0, then nearest_c gives index of cluster with centre nearest to t

Returns number of such clusters. If >0, then nearest_c gives index of cluster with centre nearest to t

Definition at line 312 of file mbl_clusters.txx.

template<class T , class D >
unsigned mbl_clusters< T, D >::clusters_within_max_r ( const T &  t,
vcl_vector< unsigned > &  c_list,
unsigned &  nearest_c,
double &  min_d 
)

Finds list of clusters whose keypoint is within max_r of t.

Finds list of clusters whose keypoint is within max_r() of t.

Returns number of such clusters. If >0, then nearest_c gives index of cluster with centre nearest to t

Definition at line 339 of file mbl_clusters.txx.

template<class T , class D >
unsigned mbl_clusters< T, D >::clusters_within_max_r ( const T &  t,
const vcl_vector< unsigned > &  in_list,
vcl_vector< unsigned > &  c_list,
unsigned &  nearest_c,
double &  min_d 
)

Finds list of clusters whose keypoint is within max_r of t.

Finds list of clusters whose keypoint is within max_r() of t.

Only considers subset of clusters listed in index Returns number of such clusters. If >0, then nearest_c gives index of cluster with centre nearest to t

Definition at line 349 of file mbl_clusters.txx.

template<class T , class D >
unsigned mbl_clusters< T, D >::create_cluster ( unsigned  new_i,
double  r = 0.0 
)

Create a new cluster around point data()[i].

Create a new cluster around point index i.

Assumes that new object data()[i] is available. Return index of cluster

Return index of cluster

Definition at line 228 of file mbl_clusters.txx.

template<class T, class D>
const vcl_vector<T>& mbl_clusters< T, D >::data ( ) const [inline]

External list of objects.

Definition at line 67 of file mbl_clusters.h.

template<class T , class D >
void mbl_clusters< T, D >::empty ( )

Empty clusters.

Definition at line 35 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::in_clusters ( const vcl_vector< unsigned > &  c_list,
vcl_vector< unsigned > &  o_list 
) const

Create list of object indices in listed clusters.

Concatenates lists of indices for each cluster in c_list

Definition at line 361 of file mbl_clusters.txx.

template<class T, class D>
const vcl_vector<vcl_vector<unsigned> >& mbl_clusters< T, D >::index ( ) const [inline]

Indices of objects associated with each cluster.

Definition at line 82 of file mbl_clusters.h.

template<class T, class D>
double mbl_clusters< T, D >::max_r ( ) const [inline]

Maximum radius for any cluster.

Definition at line 70 of file mbl_clusters.h.

template<class T, class D>
unsigned mbl_clusters< T, D >::n_clusters ( ) const [inline]

Number of clusters.

Definition at line 76 of file mbl_clusters.h.

template<class T , class D >
unsigned mbl_clusters< T, D >::nearest ( const T &  t,
double &  d 
) const

Return index of nearest object in data() to t.

Nearest object in data() to t is given by data()[nearest(t,d)]; The distance to the point is d

Definition at line 68 of file mbl_clusters.txx.

template<class T , class D >
unsigned mbl_clusters< T, D >::nearest ( const T &  t,
double &  d,
const vcl_vector< unsigned > &  c_list 
) const

Return index of nearest object in data() to t.

Consider only objects in clusters given in c_list Nearest object in data() to t is given by data()[nearest(t,d)]; The distance to the point is d

Definition at line 101 of file mbl_clusters.txx.

template<class T , class D >
unsigned mbl_clusters< T, D >::nearest_cluster ( const T &  t,
double &  d 
) const

Return index of nearest cluster in data() to t.

Finds nearest cluster key point to t The distance to the point is d

Definition at line 136 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::nearest_clusters ( const T &  t,
double &  max_d,
vcl_vector< unsigned > &  near_c 
) const

Return indices of clusters which may contain nearest point to t.

Searches through all the clusters, returning list in near_c

Searches through all the clusters

Definition at line 156 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::nearest_clusters ( const T &  t,
double &  max_d,
const vcl_vector< unsigned > &  c_list,
vcl_vector< unsigned > &  near_c 
) const

Return indices of clusters which may contain nearest point to t.

Searches through clusters listed in c_list. On input, max_d gives initial limit on distance. On exit, max_d gives the revised limit on the distance

Definition at line 194 of file mbl_clusters.txx.

template<class T, class D>
const vcl_vector<T>& mbl_clusters< T, D >::p ( ) const [inline]

Cluster key points.

Definition at line 73 of file mbl_clusters.h.

template<class T , class D >
void mbl_clusters< T, D >::print_cluster_sets ( vcl_ostream &  os) const

Write out list of elements in each cluster.

Definition at line 375 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::print_summary ( vcl_ostream &  os) const

Print class to os.

Write out list of elements in each cluster.

Definition at line 388 of file mbl_clusters.txx.

template<class T, class D>
const vcl_vector<double>& mbl_clusters< T, D >::r ( ) const [inline]

Furthest distance of a cluster object from key point for cluster.

Definition at line 79 of file mbl_clusters.h.

template<class T , class D >
void mbl_clusters< T, D >::set_data ( const vcl_vector< T > &  data)

Define external data array (pointer retained).

Empty existing clusters, then process every element of data to create clusters, by calling add_object()

Definition at line 46 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::set_data_ptr ( const vcl_vector< T > &  data)

Define external data array (pointer retained).

Use carefully! This sets the internal pointer to point to data. Really only to be used after loading internals using b_read(bfs).

Definition at line 59 of file mbl_clusters.txx.

template<class T , class D >
void mbl_clusters< T, D >::set_max_r ( double  r)

Define maximum radius for each cluster.

Definition at line 28 of file mbl_clusters.txx.

template<class T, class D>
void mbl_clusters< T, D >::set_r ( unsigned  i,
double  r 
) [inline]

Set given radius.

Definition at line 86 of file mbl_clusters.h.

template<class T , class D >
short mbl_clusters< T, D >::version_no ( ) const

Version number for I/O.

Definition at line 394 of file mbl_clusters.txx.


Member Data Documentation

template<class T, class D>
const vcl_vector<T>* mbl_clusters< T, D >::data_ [private]

Pointer to external list of objects.

Definition at line 32 of file mbl_clusters.h.

template<class T, class D>
vcl_vector<vcl_vector<unsigned> > mbl_clusters< T, D >::index_ [private]

Indices of objects associated with each cluster.

Definition at line 41 of file mbl_clusters.h.

template<class T, class D>
double mbl_clusters< T, D >::max_r_ [private]

Maximum radius for any cluster.

Definition at line 38 of file mbl_clusters.h.

template<class T, class D>
vcl_vector<T> mbl_clusters< T, D >::p_ [private]

Cluster key point.

Definition at line 35 of file mbl_clusters.h.

template<class T, class D>
vcl_vector<double> mbl_clusters< T, D >::r_ [private]

Furthest distance of a cluster object from key point for cluster.

Definition at line 44 of file mbl_clusters.h.


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