IMP  2.0.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 
38 IMPALGEBRA_BEGIN_NAMESPACE
39 
40 /** @name Vector Search
41 
42  These functions classes create various search structures
43  over sets of vectors.
44  @{
45 */
46 
47 /** Build a structure for finding nearest neighbors. Different
48  implementations are used depending on what optional dependencies
49  are available.
50  \uses{class NearestNeighborD, CGAL}
51  \uses{class NearestNeighborD, ANN}
52  */
53 template <int D>
55  IMP_KNN_DATA data_;
56  double eps_;
57 #if IMP_HAS_CHECKS >= IMP_INTERNAL
58  mutable std::ofstream query_log_;
59 #endif
60  template <class It>
61  void instantiate(It b, It e) {
62  if (0) {
63  // compile all of them
64  Ints ret;
65  internal::LinearKNNData<D> linear(b,e);
66  linear.fill_nearest_neighbors(*b, 3U, eps_, ret);
67  }
68  }
69 public:
70  template <class It>
71  NearestNeighborD(It b, It e, double epsilon=0):
72  Object("NearestNeighbor%1%"),
73  data_(b,e), eps_(epsilon){
74  instantiate(b,e);
75  }
77  double epsilon=0):
78  Object("NearestNeighbor%1%"),
79  data_(vs.begin(), vs.end()),
80  eps_(epsilon) {
81  instantiate(vs.begin(), vs.end());
82  }
83  //! Log the points and queries to a file for performance studies
84  void set_query_log(std::string fname) {
87  set_was_used(true);
88 #if IMP_HAS_CHECKS >= IMP_INTERNAL
89  query_log_.open(fname.c_str());
90  for (unsigned int i=0; i< data_.get_number_of_points(); ++i) {
91  query_log_ << spaces_io(data_.get_point(i)) << std::endl;
92  }
93  query_log_ << std::endl;
94 #endif
95  }
96 
97  unsigned int get_nearest_neighbor(const VectorD<D> &q) const {
99  set_was_used(true);
100 #if IMP_HAS_CHECKS >= IMP_INTERNAL
101  if (query_log_) {
102  query_log_ << spaces_io(q) << " " << 1 << std::endl;
103  }
104 #endif
105  Ints ret(1);
106  data_.fill_nearest_neighbors(q, 1U, eps_, ret);
107  return ret[0];
108  }
109  /** Search using the ith point in the input set. */
110  unsigned int get_nearest_neighbor(unsigned int i) const {
112  set_was_used(true);
113 #if IMP_HAS_CHECKS >= IMP_INTERNAL
114  if (query_log_) {
115  query_log_ << i << " " << 1 << std::endl;
116  }
117 #endif
118  Ints ret(2);
119  data_.fill_nearest_neighbors(data_.get_point(i), 2U, eps_, ret);
120  return ret[1];
121  }
122  /** Search using the ith point in the input set. Return the k
123  nearest neighbors.*/
124  Ints get_nearest_neighbors(unsigned int i, unsigned int k) const {
126  set_was_used(true);
127 #if IMP_HAS_CHECKS >= IMP_INTERNAL
128  if (query_log_) {
129  query_log_ << i << " " << k << std::endl;
130  }
131 #endif
132  Ints ret(k+1);
133  data_.fill_nearest_neighbors(data_.get_point(i), k+1, eps_, ret);
134  return Ints(++ret.begin(), ret.end());
135  }
136  Ints get_nearest_neighbors(const algebra::VectorD<D> &v,
137  unsigned int k) const {
139  set_was_used(true);
140 #if IMP_HAS_CHECKS >= IMP_INTERNAL
141  if (query_log_) {
142  query_log_ << v << " " << k << std::endl;
143  }
144 #endif
145  Ints ret(k+1);
146  data_.fill_nearest_neighbors(v, k, eps_, ret);
147  return Ints(++ret.begin(), ret.end());
148  }
149  /** Find all points within the provided distance. */
150  Ints get_in_ball(unsigned int i, double distance) const {
152  set_was_used(true);
153  Ints ret;
154  data_.fill_nearest_neighbors(data_.get_point(i), distance, eps_, ret);
155  return Ints(++ret.begin(), ret.end());
156  }
157  /** Find all points within the provided distance. */
158  Ints get_in_ball(const VectorD<D> &pt, double distance) const {
160  set_was_used(true);
161  Ints ret;
162  data_.fill_nearest_neighbors(pt, distance, eps_, ret);
163  return ret;
164  }
166 };
167 
168 /** @} */
169 
170 #ifndef IMP_DOXYGEN
171 typedef NearestNeighborD<1> NearestNeighbor1D;
172 typedef NearestNeighborD<2> NearestNeighbor2D;
173 typedef NearestNeighborD<3> NearestNeighbor3D;
174 typedef NearestNeighborD<4> NearestNeighbor4D;
175 typedef NearestNeighborD<5> NearestNeighbor5D;
176 typedef NearestNeighborD<6> NearestNeighbor6D;
177 typedef NearestNeighborD<-1> NearestNeighborKD;
178 #endif
179 
180 
181 
182 /** This class provides an incremental nearest neighbor search function.
183  It's interface and behavior is somewhat different than that of
184  NearestNeighborD, so be aware.
185 
186  Later this can support balls by copying points multiple times.
187 */
188 class IMPALGEBRAEXPORT DynamicNearestNeighbor3D: public base::Object {
189  typedef GridD<3, SparseGridStorageD<3, Ints,
192  Grid grid_;
193  typedef Grid::Index Index;
194  typedef Grid::ExtendedIndex EIndex;
195  Vector3Ds coords_;
196  base::Vector<Index> indexes_;
197  void audit() const;
198  void set_coordinates_internal(int id, Vector3D nc);
199  public:
201  double query_estimate=1);
202  Ints get_in_ball(int id, double distance) const;
203  void set_coordinates(int id, Vector3D nc);
205 };
206 IMPALGEBRA_END_NAMESPACE
207 
208 #endif /* IMPALGEBRA_VECTOR_SEARCH_H */