Re: [Boost-users] boost::minmax_element 2D points bounding box

From: François Duranleau (duranlef_at_[hidden])
Date: 2006-07-20 11:49:55

On Thu, 20 Jul 2006, Tomas Rapkauskas wrote:

> Hello,
> I am newbie using boost library.
> I have tried to use boost::minmax_element to calculate bounding box of
> 2D Points,
> but I failed...
>
> Here is some code:
> struct S2DPoint  { int x; int y; };
> typedef std::vector<S2DPoint > Poly;
> Poly vect;
> ...
>
> std::pair<iterator, iterator> result =
> boost::minmax_element(poly.begin(), poly.end());
[snip]

I don't think you can compute the bounding box like that, essentially 
because boost::minmax_element returns a pair of iterators from the input 
range, one indicating the minimum, the other, the max. But in the case of 
a bounding box, only rarely the coordinates of both lower and higher 
bounds are points from the input set.

What you need is something like std::for_each with a functor like this 
(uing your S2DPoint):

struct update_min_max_points
{
     S2DPoint ptMin ;
     S2DPoint ptMax ;

     update_min_max_points( const S2DPoint& first_pt )
         : ptMin( first_pt ) ,
           ptMax( first_pt )
     {
     }

     void operator () ( const S2DPoint& pt ) const
     {
         if ( ptMin.x > pt.x )
         {
             ptMin.x = pt.x ;
         }
         if ( ptMax.x < pt.x )
         {
             ptMax.x = pt.x ;
         }
         if ( ptMin.y > pt.y )
         {
             ptMin.y = pt.y ;
         }
         if ( ptMax.y < pt.y )
         {
            ptMax.y = pt.y ;
         }
     }
} ;

And then you can use it like this:

update_min_max_points result
     = std::for_each( poly.begin() + 1 ,
                      poly.end() ,
                      update_min_max_points( poly[ 0 ] ) ) ;

And your result is in result.ptMin and result.ptMax.

-- 
François Duranleau
LIGUM, Université de Montréal
"There are as many truths as there are people."
                                           - from _Neon Genesis Evangelion_