Class to record clusters of data, for faster neighbour finding. More...
#include <mbl_clusters.h>
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. |
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.
mbl_clusters< T, D >::mbl_clusters | ( | ) |
Default constructor.
Definition at line 21 of file mbl_clusters.txx.
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.
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.
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.
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.
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.
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.
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.
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.
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.
const vcl_vector<T>& mbl_clusters< T, D >::data | ( | ) | const [inline] |
External list of objects.
Definition at line 67 of file mbl_clusters.h.
void mbl_clusters< T, D >::empty | ( | ) |
Empty clusters.
Definition at line 35 of file mbl_clusters.txx.
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.
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.
double mbl_clusters< T, D >::max_r | ( | ) | const [inline] |
Maximum radius for any cluster.
Definition at line 70 of file mbl_clusters.h.
unsigned mbl_clusters< T, D >::n_clusters | ( | ) | const [inline] |
Number of clusters.
Definition at line 76 of file mbl_clusters.h.
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.
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.
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.
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.
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.
const vcl_vector<T>& mbl_clusters< T, D >::p | ( | ) | const [inline] |
Cluster key points.
Definition at line 73 of file mbl_clusters.h.
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.
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.
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.
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.
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.
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.
void mbl_clusters< T, D >::set_r | ( | unsigned | i, |
double | r | ||
) | [inline] |
Set given radius.
Definition at line 86 of file mbl_clusters.h.
short mbl_clusters< T, D >::version_no | ( | ) | const |
Version number for I/O.
Definition at line 394 of file mbl_clusters.txx.
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.
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.
double mbl_clusters< T, D >::max_r_ [private] |
Maximum radius for any cluster.
Definition at line 38 of file mbl_clusters.h.
vcl_vector<T> mbl_clusters< T, D >::p_ [private] |
Cluster key point.
Definition at line 35 of file mbl_clusters.h.
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.