comparing object to a growing set of other objects

Hello to all,

In my program I have a set of N vectors (I mean cartesian 3D vectors, represented by C++ vector containers of properly defined structs that I called vectorType). These 3D vectors are ordered according to their length, shortest first.

I start with the shortest, and then go over all of them keeping only those which have an angular separation with each of the already kept ones that is bigger than a certain value. This comparison part is what I do not know how to do.

In pseudocode (V are the 3D vectors, V.at(0) being the shortest:

Code:

std::vector< vectorType > W;

W.push_back( V.at(0) );

for ( k=1; k<N; k++)
{
      if ( angle(&V.at(k), &W.at(0)) > theta )
      and
      if ( angle(&V.at(k), &W.at(1)) > theta )
      and
      ...
      if ( angle(&V.at(k), &W.at(L)) > theta )               // L is current W.size()

              then W.push_back( V.at(k) )
}

The part I don't know how to write is the multiple if statements (or whatever is better) for a growing number of elements to compare with.

If anyone could give me a hint of how to do that, it would be most appreciated.

Thanks,

mc61

An inner loop (function) which reports whether all conditions are true (or breaks early)?

Code:

	for (int k = 0; k < V.size(); k++)
	{
		  for (int inner; inner < W.size(); inner++)
		  {
			  if ( angle(&V.at(k), &W.at(inner)) > theta )
			  {
				  W.push_back(V.at(k));
				  break; // if you only need V.at(k) once.
			  }
		  }
	}

keira's code has the conditions connected the wrong way (it succeeds if the condition is true for any, when it needs to be true for all).

Here's one way:

Code:

for(int k = 0; k < V.size(); ++k) {
  bool larger = true;
  for(int inner = 0; larger && inner < W.size(); ++inner) {
    larger = (angle(&V[k], &W[inner]) > theta);
  }
  if(larger) {
    W.push_back(V[k]);
  }
}

Note that using the checked at() for a trivial index loop is a waste of time.

Here's another way to write this:

Code:

#include <boost/lambda.hpp>
namespace ll = boost::lambda;

// Returns true if Predicate is true for all elements in the range [first,last).
template <typename InputIterator, typename Predicate>
bool all(InputIterator first, InputIterator last, Predicate p)
{
  for( ; first != last; ++first) {
    if(!p(*first)) {
      return false;
    }
  }
  return true;
}

for(std::vector<vectorType>::const_iterator it = V.begin(); it != V.end(); ++it) {
  if(all(W.begin(), W.end(), ll::bind(&angle, &*it, &ll::_1) > theta)) {
    W.push_back(*it);
  }
}

Could be made even shorter by writing a copy_if and using that, but then it starts to get unreadable.

Thanks to all for your help!

CornedBee: I understand your first method, and I can see how it solves my problem completely! Your second method is a little too much for my elementary level of C++, so I am going to have to stare at it for a while until it clicks in my head :-)

I thank you so much for this.

mc61

Basically, the second method extracts the inner loop into a separate function. The body for the inner loop is supplied to the function as a parameter, which is somewhat tricky, because functions aren't first-class objects in C++. However, the excellent Boost.Lambda library does a good job at pretending that they are.