[RESOLVED] binary_search with return position and predicate

[GNiewerth]

Hello,

I´m wondering if the STL is offering a solution to this problem:

I´m building a chart from a sequence of arbitrary length. To avoid displaying multiple vertexes that share a common position I decided only to display vertexes that differ from every other vertexes by 5%. The brute force approach is to check new vertexes to all existing ones, which is painfully slow for huge numbers of vertexes (of course). After refining the data structure to a sorted container (in my case vector) of vertexes I can use a binary search algorithm on that container. Unfortunately there´s no binary_find_if or binary_search_if for containers that fits my needs, binary_search only returns true/false and lower_bound doesn´t work for reasons I already forgot

However, that´s the solution I came up with:

struct CloudVertex
{
   double  XValue;
   double  YValue;
   
   CloudVertex( double X, double Y ) :
      XValue( X ),
      YValue( Y )
   {
   }

   bool operator<( const CloudVertex& other ) const
   {
       if( XValue == other.XValue )
       {
          return YValue < other.YValue;
       }
       return XValue < other.XValue;
   }
};

struct VertexVicinityComparator
{
   double XTolerance;
   double YTolerance;

   VertexVicinityComparator( double XTol, double YTol ) :
      XTolerance( fabs( XTol ) ),
      YTolerance( fabs( YTol ) )      
   {
   }

   bool operator()( const CloudVertex& op1, const CloudVertex& op2 ) const
   {
      bool bPartX = false;
      bool bPartY = false;

      if( 0 == op1.XValue )
      {
         bPartX = op2.XValue == 0;
      }
      else
      {
         bPartX = fabs( (fabs( op1.XValue - op2.XValue ) / op1.XValue) ) < XTolerance;
      }
      if( 0 == op1.YValue )
      {
         bPartY = op2.YValue == 0;
      }
      else
      {
         bPartY = fabs( (fabs( op1.YValue - op2.YValue ) / op1.YValue) ) < YTolerance;
      }
      return bPartX && bPartY;
   }
};

// binary_search_if function
template<typename IteratorType, typename value, typename Predicate>
IteratorType binary_search_if( IteratorType first, IteratorType last,
                                 const value& val, Predicate pred )
{
   IteratorType end = last;

   int len = distance( first, last );

   while( len > 0 )
   {
      IteratorType mid = first;
      advance( mid, len /2 );

      if( true == pred( *mid, val ) )
      {
         return mid;
      }
      else
      {
         // exclude mid from range
         if( val < *mid )
         {
            // search left interval
            advance( mid, -1 );
            last = mid;
         }
         else
         {
            // search right interval
            advance( mid, 1 );
            first = mid;
         }
         len = distance( first, last );
      }
   }
   if( first != end && true == pred( *first, val ) )
   {
      return first;
   }
   return end;
}

// this is my insertion code
void insert_vertex( double X, double Y )
{
   // both tolerances set to 5%
   VertexVicinityComparator Comparator( 0.05, 0.05 );
   CloudVertex Vertex( X, Y );

   std::vector<CloudVertex>::iterator pos;
   pos  = binary_search_if( AllVertexes.begin(), AllVertexes.end(), Vertex, Comparator );
   if( AllVertexes.end() == pos )
   {
      // Vertex must be inserted 
     pos = lower_bound( AllVertexes.begin(), AllVertexes.end(), Vertex, Comparator );
     AllVertexes.insert( pos, Vertex );
   }
}

I think there´s plenty of room for improvement since vector has to move its elements when there´s an elemented inserted. Unfortunately neither set or map offer a find_if method for lookup and I´m wondering if there´s a better solution to this.

I know this won´t compile, but I think the code helps to explain my problem.

[laserlight]

Unfortunately there´s no binary_find_if or binary_search_if for containers that fits my needs, binary_search only returns true/false and lower_bound doesn´t work for reasons I already forgot

The way I see it, you could use equal_range(), and then traverse backwards and forwards with the iterators returned until you reach elements that do not satisfy your requirement.

[_uj]

I´m wondering if there´s a better solution to this.

A standard solution to check for proximity is to overlay a coarse-grain pixel coordinate system over the vertex coordinate system.

Say the 5% difference is dx, dy in the vertex coordinate system. You can transform any vertex (x, y) to a corresponding pixel (i, j) like,

int i = (int) (x/dx);
int j = (int) (y/dy);

This simple formula transforms any vertex into a corresponding pixel. And if two vertexes are close and lie within the same dx, dy square they transform to the same pixel. Close vertexes have the same pixel, that's the basic idea.

So what you do is that you maintain a map (preferably unordered, that is hash based). For each pixel the map associates a list with all vertexes that transform to that pixel.

When you have a new vertex you transform it to a pixel. Then you check if that pixel is in the map. If it is you get a corresponding vertex-list with vertexes that have the same pixel. So you compare those.

Now a small complication. It's not enougth to check whether the pixel is in the map. You'll also have to check the pixel's 8 closest pixel neighbours. So all in all, when you have a new vertex you need to check the vertex-lists of 9 pixels in the map. Or rather at the most 9 vertex-lists. If a pixel and its 8 neighbours aren't in the map you know the corresponding vertex has no close vertexes.

[GNiewerth]

Thanks to both of you for your responses.

@laserlight:
The algorithm itself wasn´t the problem, I was afraid of performance hits when too many items were inserted into the vector.

@uj
That was my first approach, but it has some drawbacks in my scenario. I´ve got a measurement value that consists of about 20 data items of different ranges. Some range from 1.2 to 5, some from 50-4500 and for some I only can assume a minimum value, the maximum is unknown and can be anything. Given this I need to specify some grain size, depending on the data range, because it doesn´t make sense to apply a grain size of, say, 50 to a data range of 10-50. I wanted to be extraordinary clever and specify only percentaged tolerances to get rid of fixed grain sizes, but I shot myself in the foot:
I didn´t spend attention to the size of buckets I created, the larger the value, the larger the bucket is ( the bucket range for 1 at 10% tolerance is 0.9 - 1.1, the range for 100 at 10% tolerance is 90-110) .

I think I need to spend some more thoughts on that.