IMP  2.3.1
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-2014 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/log_macros.h>
16 #include <IMP/base/SetCheckState.h>
17 
18 #include "grid_storages.h"
19 #include "grid_ranges.h"
20 #include "GridD.h"
21 #ifdef IMP_ALGEBRA_USE_IMP_CGAL
22 #include <IMP/cgal/internal/knn.h>
23 #endif
24 #ifdef IMP_ALGEBRA_USE_ANN
25 #include "internal/ann.h"
26 #endif
27 #include "internal/linear_knn.h"
28 #include <fstream>
29 
30 #ifdef IMP_ALGEBRA_USE_ANN
31 #define IMP_KNN_DATA internal::ANNData
32 #elif defined(IMP_ALGEBRA_USE_IMP_CGAL)
33 #define IMP_KNN_DATA IMP::cgal::internal::KNNData
34 #else
35 #define IMP_KNN_DATA internal::LinearKNNData<D>
36 #endif
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 
70  public:
71  template <class It>
72  NearestNeighborD(It b, It e, double epsilon = 0)
73  : Object("NearestNeighbor%1%"), data_(b, e), eps_(epsilon) {
74  instantiate(b, e);
75  }
76  NearestNeighborD(const base::Vector<VectorD<D> > &vs, double epsilon = 0)
77  : Object("NearestNeighbor%1%"),
78  data_(vs.begin(), vs.end()),
79  eps_(epsilon) {
80  instantiate(vs.begin(), vs.end());
81  }
82  //! Log the points and queries to a file for performance studies
83  void set_query_log(std::string fname) {
86  set_was_used(true);
87 #if IMP_HAS_CHECKS >= IMP_INTERNAL
88  query_log_.open(fname.c_str());
89  for (unsigned int i = 0; i < data_.get_number_of_points(); ++i) {
90  query_log_ << spaces_io(data_.get_point(i)) << std::endl;
91  }
92  query_log_ << std::endl;
93 #endif
94  }
95 
96  unsigned int get_nearest_neighbor(const VectorD<D> &q) const {
98  set_was_used(true);
99 #if IMP_HAS_CHECKS >= IMP_INTERNAL
100  if (query_log_) {
101  query_log_ << spaces_io(q) << " " << 1 << std::endl;
102  }
103 #endif
104  Ints ret(1);
105  data_.fill_nearest_neighbors(q, 1U, eps_, ret);
106  return ret[0];
107  }
108  /** Search using the ith point in the input set. */
109  unsigned int get_nearest_neighbor(unsigned int i) const {
111  set_was_used(true);
112 #if IMP_HAS_CHECKS >= IMP_INTERNAL
113  if (query_log_) {
114  query_log_ << i << " " << 1 << std::endl;
115  }
116 #endif
117  Ints ret(2);
118  data_.fill_nearest_neighbors(data_.get_point(i), 2U, eps_, ret);
119  return ret[1];
120  }
121  //! Search using the ith point in the input set.
122  /** \return the k nearest neighbors. */
123  Ints get_nearest_neighbors(unsigned int i, unsigned int k) const {
125  set_was_used(true);
126 #if IMP_HAS_CHECKS >= IMP_INTERNAL
127  if (query_log_) {
128  query_log_ << i << " " << k << std::endl;
129  }
130 #endif
131  Ints ret(k + 1);
132  data_.fill_nearest_neighbors(data_.get_point(i), k + 1, eps_, ret);
133  return Ints(++ret.begin(), ret.end());
134  }
135  Ints get_nearest_neighbors(const algebra::VectorD<D> &v,
136  unsigned int k) const {
138  set_was_used(true);
139 #if IMP_HAS_CHECKS >= IMP_INTERNAL
140  if (query_log_) {
141  query_log_ << v << " " << k << std::endl;
142  }
143 #endif
144  Ints ret(k + 1);
145  data_.fill_nearest_neighbors(v, k, eps_, ret);
146  return Ints(++ret.begin(), ret.end());
147  }
148  /** Find all points within the provided distance. */
149  Ints get_in_ball(unsigned int i, double distance) const {
151  set_was_used(true);
152  Ints ret;
153  data_.fill_nearest_neighbors(data_.get_point(i), distance, eps_, ret);
154  return Ints(++ret.begin(), ret.end());
155  }
156  /** Find all points within the provided distance. */
157  Ints get_in_ball(const VectorD<D> &pt, double distance) const {
159  set_was_used(true);
160  Ints ret;
161  data_.fill_nearest_neighbors(pt, distance, eps_, ret);
162  return ret;
163  }
165 };
166 
167 /** @} */
168 
169 #ifndef IMP_DOXYGEN
170 typedef NearestNeighborD<1> NearestNeighbor1D;
171 typedef NearestNeighborD<2> NearestNeighbor2D;
172 typedef NearestNeighborD<3> NearestNeighbor3D;
173 typedef NearestNeighborD<4> NearestNeighbor4D;
174 typedef NearestNeighborD<5> NearestNeighbor5D;
175 typedef NearestNeighborD<6> NearestNeighbor6D;
176 typedef NearestNeighborD<-1> NearestNeighborKD;
177 #endif
178 
179 /** This class provides an incremental nearest neighbor search function.
180  It's interface and behavior is somewhat different than that of
181  NearestNeighborD, so be aware.
182 
183  Later this can support balls by copying points multiple times.
184 */
185 class IMPALGEBRAEXPORT DynamicNearestNeighbor3D : public base::Object {
188  Grid grid_;
189  typedef Grid::Index Index;
190  typedef Grid::ExtendedIndex EIndex;
191  Vector3Ds coords_;
192  base::Vector<Index> indexes_;
193  void audit() const;
194  void set_coordinates_internal(int id, Vector3D nc);
195 
196  public:
197  DynamicNearestNeighbor3D(const Vector3Ds &vs, double query_estimate = 1);
198  Ints get_in_ball(int id, double distance) const;
199  void set_coordinates(int id, Vector3D nc);
201 };
202 IMPALGEBRA_END_NAMESPACE
203 
204 #endif /* IMPALGEBRA_VECTOR_SEARCH_H */
unsigned int get_nearest_neighbor(unsigned int i) const
Basic types used by IMP.
void set_query_log(std::string fname)
Log the points and queries to a file for performance studies.
Definition: vector_search.h:83
A class to represent a voxel grid.
Represent a real cell in a grid (one within the bounding box)
Definition: grid_indexes.h:162
#define IMP_OBJECT_METHODS(Name)
Define the basic things needed by any Object.
Definition: object_macros.h:25
#define IMP_OBJECT_LOG
Set the log level to the object's log level.
Definition: log_macros.h:297
#define IMP_INTERNAL_CHECK_VARIABLE(variable)
Definition: check_macros.h:197
An index in an infinite grid on space.
Definition: grid_indexes.h:30
A voxel grid in d-dimensional space space.
Definition: GridD.h:79
A Cartesian vector in D-dimensions.
Definition: VectorD.h:52
Logging and error reporting support.
A class to represent a voxel grid.
Simple D vector class.
Ints get_in_ball(const VectorD< D > &pt, double distance) const
Common base class for heavy weight IMP objects.
Definition: Object.h:106
Checking and error reporting support.
Ints get_nearest_neighbors(unsigned int i, unsigned int k) const
Search using the ith point in the input set.
A shared base class to help in debugging and things.
VectorD< 3 > Vector3D
Definition: VectorD.h:395
A class to represent a voxel grid.
Ints get_in_ball(unsigned int i, double distance) const
Logging and error reporting support.
IMP::base::Vector< Int > Ints
Standard way to pass a bunch of Int values.
Definition: types.h:49