comparing object to a growing set of other objects

This is a discussion on comparing object to a growing set of other objects within the C++ Programming forums, part of the General Programming Boards category; Hello to all, In my program I have a set of N vectors (I mean cartesian 3D vectors, represented by ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    31

    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

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    An inner loop (function) which reports whether all conditions are true (or breaks early)?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Aug 2007
    Posts
    81
    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.
    			  }
    		  }
    	}

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    31
    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

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. OOP Question DB Access Wrapper Classes
    By digioz in forum C# Programming
    Replies: 2
    Last Post: 09-07-2008, 05:30 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 09:38 PM
  3. Include Problems
    By loopshot in forum Game Programming
    Replies: 13
    Last Post: 02-17-2006, 03:22 PM
  4. Replies: 60
    Last Post: 12-20-2005, 11:36 PM
  5. My graphics library
    By stupid_mutt in forum C Programming
    Replies: 3
    Last Post: 11-26-2001, 06:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21