IMP logo
IMP Reference Guide  develop.2640aaee5c,2019/11/13
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 search over vectors.
3  *
4  * Copyright 2007-2019 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/types.h>
13 #include <IMP/Object.h>
14 #include <IMP/log.h>
15 #include <IMP/log_macros.h>
16 #include <IMP/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 and classes create various search structures
43  over sets of vectors.
44  @{
45 */
46 
47 //! Build a structure for finding nearest neighbors.
48 /** Different 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>
54 class NearestNeighborD : public IMP::Object {
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 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 //! Provide an incremental nearest neighbor search function.
180 /** The 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 Object {
188  Grid grid_;
189  typedef Grid::Index Index;
190  typedef Grid::ExtendedIndex EIndex;
191  Vector3Ds coords_;
192  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
Search using the ith point in the input set.
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:195
An index in an infinite grid on space.
Definition: grid_indexes.h:30
A voxel grid in d-dimensional space.
Definition: GridD.h:79
Provide an incremental nearest neighbor search function.
A Cartesian vector in D-dimensions.
Definition: VectorD.h:52
Common base class for heavy weight IMP objects.
Definition: Object.h:106
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
Find all points within the provided distance.
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:421
A class to represent a voxel grid.
Ints get_in_ball(unsigned int i, double distance) const
Find all points within the provided distance.
IMP::Vector< Int > Ints
Standard way to pass a bunch of Int values.
Definition: types.h:49
Logging and error reporting support.
Build a structure for finding nearest neighbors.
Definition: vector_search.h:54