IMP  2.1.0
The Integrative Modeling Platform
vector_search.h
Go to the documentation of this file.
1 /**
2  * \file IMP/algebra/vector_search.h \brief Functions to generate vectors.
3  *
4  * Copyright 2007-2013 IMP Inventors. All rights reserved.
5  *
6  */
7 
8 #ifndef IMPALGEBRA_VECTOR_SEARCH_H
9 #define IMPALGEBRA_VECTOR_SEARCH_H
10 
11 #include "VectorD.h"
12 #include <IMP/base/types.h>
13 #include <IMP/base/Object.h>
14 #include <IMP/base/log.h>
15 #include <IMP/base/SetCheckState.h>
16 
17 #include "grid_storages.h"
18 #include "grid_ranges.h"
19 #include "GridD.h"
20 #ifdef IMP_ALGEBRA_USE_IMP_CGAL
21 #include <IMP/cgal/internal/knn.h>
22 #endif
23 #ifdef IMP_ALGEBRA_USE_ANN
24 #include "internal/ann.h"
25 #endif
26 #include "internal/linear_knn.h"
27 #include <fstream>
28 
29 #ifdef IMP_ALGEBRA_USE_ANN
30 #define IMP_KNN_DATA internal::ANNData
31 #elif defined(IMP_ALGEBRA_USE_IMP_CGAL)
32 #define IMP_KNN_DATA IMP::cgal::internal::KNNData
33 #else
34 #define IMP_KNN_DATA internal::LinearKNNData<D>
35 #endif
36 
37 IMPALGEBRA_BEGIN_NAMESPACE
38 
39 /** @name Vector Search
40 
41  These functions classes create various search structures
42  over sets of vectors.
43  @{
44 */
45 
46 /** Build a structure for finding nearest neighbors. Different
47  implementations are used depending on what optional dependencies
48  are available.
49  \uses{class NearestNeighborD, CGAL}
50  \uses{class NearestNeighborD, ANN}
51  */
52 template <int D>
54  IMP_KNN_DATA data_;
55  double eps_;
56 #if IMP_HAS_CHECKS >= IMP_INTERNAL
57  mutable std::ofstream query_log_;
58 #endif
59  template <class It>
60  void instantiate(It b, It e) {
61  if (0) {
62  // compile all of them
63  Ints ret;
64  internal::LinearKNNData<D> linear(b, e);
65  linear.fill_nearest_neighbors(*b, 3U, eps_, ret);
66  }
67  }
68 
69  public:
70  template <class It>
71  NearestNeighborD(It b, It e, double epsilon = 0)
72  : Object("NearestNeighbor%1%"), data_(b, e), eps_(epsilon) {
73  instantiate(b, e);
74  }
75  NearestNeighborD(const base::Vector<VectorD<D> > &vs, double epsilon = 0)
76  : Object("NearestNeighbor%1%"),
77  data_(vs.begin(), vs.end()),
78  eps_(epsilon) {
79  instantiate(vs.begin(), vs.end());
80  }
81  //! Log the points and queries to a file for performance studies
82  void set_query_log(std::string fname) {
85  set_was_used(true);
86 #if IMP_HAS_CHECKS >= IMP_INTERNAL
87  query_log_.open(fname.c_str());
88  for (unsigned int i = 0; i < data_.get_number_of_points(); ++i) {
89  query_log_ << spaces_io(data_.get_point(i)) << std::endl;
90  }
91  query_log_ << std::endl;
92 #endif
93  }
94 
95  unsigned int get_nearest_neighbor(const VectorD<D> &q) const {
97  set_was_used(true);
98 #if IMP_HAS_CHECKS >= IMP_INTERNAL
99  if (query_log_) {
100  query_log_ << spaces_io(q) << " " << 1 << std::endl;
101  }
102 #endif
103  Ints ret(1);
104  data_.fill_nearest_neighbors(q, 1U, eps_, ret);
105  return ret[0];
106  }
107  /** Search using the ith point in the input set. */
108  unsigned int get_nearest_neighbor(unsigned int i) const {
110  set_was_used(true);
111 #if IMP_HAS_CHECKS >= IMP_INTERNAL
112  if (query_log_) {
113  query_log_ << i << " " << 1 << std::endl;
114  }
115 #endif
116  Ints ret(2);
117  data_.fill_nearest_neighbors(data_.get_point(i), 2U, eps_, ret);
118  return ret[1];
119  }
120  /** Search using the ith point in the input set. Return the k
121  nearest neighbors.*/
122  Ints get_nearest_neighbors(unsigned int i, unsigned int k) const {
124  set_was_used(true);
125 #if IMP_HAS_CHECKS >= IMP_INTERNAL
126  if (query_log_) {
127  query_log_ << i << " " << k << std::endl;
128  }
129 #endif
130  Ints ret(k + 1);
131  data_.fill_nearest_neighbors(data_.get_point(i), k + 1, eps_, ret);
132  return Ints(++ret.begin(), ret.end());
133  }
134  Ints get_nearest_neighbors(const algebra::VectorD<D> &v,
135  unsigned int k) const {
137  set_was_used(true);
138 #if IMP_HAS_CHECKS >= IMP_INTERNAL
139  if (query_log_) {
140  query_log_ << v << " " << k << std::endl;
141  }
142 #endif
143  Ints ret(k + 1);
144  data_.fill_nearest_neighbors(v, k, eps_, ret);
145  return Ints(++ret.begin(), ret.end());
146  }
147  /** Find all points within the provided distance. */
148  Ints get_in_ball(unsigned int i, double distance) const {
150  set_was_used(true);
151  Ints ret;
152  data_.fill_nearest_neighbors(data_.get_point(i), distance, eps_, ret);
153  return Ints(++ret.begin(), ret.end());
154  }
155  /** Find all points within the provided distance. */
156  Ints get_in_ball(const VectorD<D> &pt, double distance) const {
158  set_was_used(true);
159  Ints ret;
160  data_.fill_nearest_neighbors(pt, distance, eps_, ret);
161  return ret;
162  }
164 };
165 
166 /** @} */
167 
168 #ifndef IMP_DOXYGEN
169 typedef NearestNeighborD<1> NearestNeighbor1D;
170 typedef NearestNeighborD<2> NearestNeighbor2D;
171 typedef NearestNeighborD<3> NearestNeighbor3D;
172 typedef NearestNeighborD<4> NearestNeighbor4D;
173 typedef NearestNeighborD<5> NearestNeighbor5D;
174 typedef NearestNeighborD<6> NearestNeighbor6D;
175 typedef NearestNeighborD<-1> NearestNeighborKD;
176 #endif
177 
178 /** This class provides an incremental nearest neighbor search function.
179  It's interface and behavior is somewhat different than that of
180  NearestNeighborD, so be aware.
181 
182  Later this can support balls by copying points multiple times.
183 */
184 class IMPALGEBRAEXPORT DynamicNearestNeighbor3D : public base::Object {
187  Grid grid_;
188  typedef Grid::Index Index;
189  typedef Grid::ExtendedIndex EIndex;
190  Vector3Ds coords_;
191  base::Vector<Index> indexes_;
192  void audit() const;
193  void set_coordinates_internal(int id, Vector3D nc);
194 
195  public:
196  DynamicNearestNeighbor3D(const Vector3Ds &vs, double query_estimate = 1);
197  Ints get_in_ball(int id, double distance) const;
198  void set_coordinates(int id, Vector3D nc);
200 };
201 IMPALGEBRA_END_NAMESPACE
202 
203 #endif /* IMPALGEBRA_VECTOR_SEARCH_H */
Basic types used by IMP.
unsigned int get_nearest_neighbor(unsigned int i) const
void set_query_log(std::string fname)
Log the points and queries to a file for performance studies.
Definition: vector_search.h:82
A class to represent a voxel grid.
Represent a real cell in a grid (one within the bounding box)
Definition: grid_indexes.h:136
An index in an infinite grid on space.
Definition: grid_indexes.h:28
A voxel grid in d-dimensional space space.
Definition: GridD.h:78
#define IMP_INTERNAL_CHECK_VARIABLE(variable)
A Cartesian vector in D-dimensions.
Definition: VectorD.h:48
Checkging and error reporting support.
A class to represent a voxel grid.
Simple D vector class.
#define IMP_OBJECT_METHODS(Name)
Define the basic things needed by any Object.
Ints get_in_ball(const VectorD< D > &pt, double distance) const
Common base class for heavy weight IMP objects.
#define IMP_OBJECT_LOG
Set the log level to the object&#39;s log level.
Ints get_nearest_neighbors(unsigned int i, unsigned int k) const
Logging and error reporting support.
A class to represent a voxel grid.
Ints get_in_ball(unsigned int i, double distance) const
A shared base class to help in debugging and things.
IMP::base::Vector< Int > Ints
Standard way to pass a bunch of Int values.
Definition: base/types.h:49