How can I find a box that encompasses all given boxes?

Question

I have a sequence of boost geometry box types and wish to find the dimensions of a box that encompasses all of those objects.

I've noticed that boost geometry provides the encompass function, which seems to do what I'm asking for general geometry concepts, but I don't know how to do this for a sequence of boxes.

Basically I've just had to roll my own, but I was wondering if it was possible to simply turn a sequence of boxes into a "geometry" so that I can simply apply the envelope function. Here's what I've currently written:

// elsewhere in my code:
using Location = boost::geometry::model::d2::point_xy<double>;
using Box = boost::geometry::model::box<Location>;

// calculate the smallest box that fully encompasses all provided boxes            
template <template <typename...> class IterableContainer>                          
Box Envelope(const IterableContainer<Box>& sequence)                               
{                                                                                  
    Location minCorner(                                                            
        std::numeric_limits<double>::max(),                                        
        std::numeric_limits<double>::max());                                       

    Location maxCorner(                                                            
        std::numeric_limits<double>::lowest(),                                        
        std::numeric_limits<double>::lowest());                                       

    for (auto& box : sequence)                                                     
    {                                                                              
        if (box.min_corner().x() < minCorner.x())                                  
            minCorner.x() == box.min_corner().x();                                 

        if (box.min_corner().y() < minCorner.y())                                  
            minCorner.y() == box.min_corner().y();                                 

        if (box.max_corner().x() > maxCorner.x())                                  
            maxCorner.x() == box.max_corner().x();                                 

        if (box.max_corner().y() > maxCorner.y())                                  
            maxCorner.y() == box.max_corner().y();                                 
    }                                                                              

    return Box(minCorner, maxCorner);                                              
}                                                                                  

Answer 1

The function you are looking for is called std::accumulate. You need to feed it a box-union function.

using Location = boost::geometry::model::d2::point_xy<double>;
using Box = boost::geometry::model::box<Location>;
double pinfi = std::numeric_limits<double>::max();
double ninfi = std::numeric_limits<double>::lowest();

Box u = std::accumulate(container.begin(), container.end(), 
                        Box(Location(pinfi,pinfi), Location(ninfi,ninfi)),
                        [](const Box& a, const Box& b) { 
                            return Box(
                                    Location(
                                     std::min(a.min_corner().x(),b.min_corner().x()),
                                     std::min(a.min_corner().y(),b.min_corner().y())),
                                    Location(
                                     std::max(a.max_corner().x(),b.max_corner().x()),
                                     std::min(a.max_corner().y(),b.max_corner().y())));

                        });

Update: the building blocks of this function already exist in boost::geometry. Here's complete tested code:

template <typename T>
Box box_encompass (T beg, T end)
{
    return std::accumulate(beg, end, boost::geometry::make_inverse<Box>(),
                [](Box a, const Box& b) -> Box {
                    boost::geometry::expand(a,b);
                    return a;
                });
}