lundi 25 juillet 2016

Is there an STL algorithm to find if an element is present in a container based on some tolerance?

The problem I am trying to solve is a following: I have a container of floating points (vector of double vectors):

std::vector<std::vector<double>> dv { {0.0, 0.0}, {1.0, 0.0}, {0.0, 1.0}, {1.0, 1.0} };

Then, assume I have a new point (double vector):

std::vector<double> v1 {0.0001, 1.0};

I want to check if a point v1 is present in dv container based on some tollerance. The distance between two vectors is calculated as Euclidean distance.

I have looked to the relevant questions and answers:

and was also trying to use std::find_if() without any success, as it accepts only unary predicate.

At the moment I came up with a temporary solution. First, I created a generic function to find the Euclidean distance between two vectors:

template <typename InputIt1, typename InputIt2>
double EuclideanDistance(InputIt1 beg1, InputIt1 end1, InputIt2 beg2) {
  double val = 0.0;
  while (beg1 != end1) {
    double dist = (*beg1++) - (*beg2++);
    val += dist*dist;
  }
  return val > 0.0? sqrt(val) : 0.0;
}

Second, I created check_if function to check if an element is presented in a container based on the tolerance (Epsilon):

template <typename Container, typename Element>
bool check_if(const Container& c, const Element& el,
              const double Epsilon = 0.001) {
  auto pos = c.begin();
  for (; pos != c.end(); ++pos) {
    if (EuclideanDistance(pos->begin(), pos->end(), el.begin()) < Epsilon) {
      return true;
    }
  }
  return false;
}

And then I can use my code in a context like this:

// Check if container contains v1 using check_if()
if (check_if(dv, v1)) {
  std::cout << "Using check_if() - Container contains v1\n";
}

So my questions are following:

  1. Is there in-house an STL algorithm to achieve the same goal? If no, how could I improve my code? For example, I'm not sure how could I use any distance function in check_in() instead of EuclideanDistance()?
  2. I wonder if AshleysBrain suggestion (http://ift.tt/2alsZdH) to use std::set instead of std::vector could make any difference having a container of floating points?

Aucun commentaire:

Enregistrer un commentaire