Find bounding set of rectangles

Question

I have an std::vector of rectangle's. The class definition is quite simple:

class rectangle
{
public:
    rectangle();
    rectangle(int leftX, int topY, int width, int height);
    rectangle(const rectangle &other);

    int x() const;
    int y() const;

    int width() const;
    int height() const;

    // Returns the bounding rectangle of this rectangle and the given rectangle.
    rectangle united(const rectangle &r) const;
    rectangle intersected(const rectangle &r) const;

    // Returns true if rectangle intersects with given rectagle else false.
    bool intersects(const rectangle &r) const;
};

For each rectangle, I'd like to see if intersects another rectangle in the vector and then 'unite' them (find the bounding rectangle) if they intersect.

I'm quite keen to see if there is a way to use a function in <algorithm> to perform the search/combining on a range of rectangles. Can anyone advise on a possible solution? Looking for something that is concise without reinventing the wheel.

[EDIT:] I should mention that I have already implemented 'intersects()' and 'united'.

My end goal is to implement a function that works on my range of rectangles like so:

/// For each rectangle in the vector it test if it intersects with another and return the set of united rectangles. 
/// \param v A set of rectangles
/// \return A united set of rectangles.
std::vector<rectangle> test_intersect_and_unite(const std::vector<rectangle> &v)
{
    std::vector<rectangle> united;

    // ...

    return united;
}

I'd probably be handling less than 20 rectangles.

Answer 1

My question seemed to have raised more confusion than answers. Perhaps I'm not very good at explaining myself. Nonetheless, this is my (naive) solution.

///////////////////////////////////////////////////////////////////////////
template<template <typename, typename = std::allocator<rectangle>> class Container>
Container<rectangle> test_intersect_and_unite(const Container<rectangle> &v)
{
    Container<rectangle> vTemp{v};

    for (std::size_t i = 0; i < vTemp.size(); ++i)
    {
        for (std::size_t j = 0; j < vTemp.size(); ++j)
        {
            if (i == j) { continue; }

            if (vTemp[i].intersects(vTemp[j]))
            {
                vTemp[i]  = vTemp[i].united(vTemp[j]);
                vTemp.erase(vTemp.begin() + j);
                if (j < i) { --i; }
                --j;
                continue;
            }
        }
    }

    return vTemp;
}

Some simple unit tests:

////////////////////////////////////////////////////////////////////////////////
class rectangle_utils_test : public testing::Test
{
public:

    rectangle_utils_test() = default;

    ~rectangle_utils_test() override = default;
};


//////////////////////////////////////////////////////////////////////////
TEST_F(rectangle_utils_test, test_intersect_and_unite)
{
    // TODO: This unit test makes some naive assumptions about ordering.
    // TODO: Test with negative values.

    {
        std::vector<rectangle> vArg = {{10, 10, 10, 10}, {15, 15, 10, 10}};

        std::vector<rectangle> v = test_intersect_and_unite(vArg);

        ASSERT_EQ(v.size(), 1);
        ASSERT_EQ(v[0], rectangle(10, 10, 15, 15));
    }

    {
        std::vector<rectangle> vArg = {{10, 10, 10, 10}, {21, 21, 10, 10}};

        std::vector<rectangle> v = test_intersect_and_unite(vArg);

        ASSERT_EQ(v.size(), 2);
        ASSERT_EQ(v[0], rectangle(10, 10, 10, 10));
        ASSERT_EQ(v[1], rectangle(21, 21, 10, 10));
    }

    {
        std::vector<rectangle> vArg = {{10, 10, 10, 10},
                                       {15, 15, 10, 10},
                                       {60, 60, 10, 10},
                                       {5,  5,  10, 10},
                                       {0,  0,  10, 10},
                                       {40, 40, 10, 10}};

        std::vector<rectangle> v = test_intersect_and_unite(vArg);

        ASSERT_EQ(v.size(), 3);
        ASSERT_EQ(v[0], rectangle(0, 0, 25, 25));
        ASSERT_EQ(v[1], rectangle(60, 60, 10, 10));
        ASSERT_EQ(v[2], rectangle(40, 40, 10, 10));
    }

    // Most interesting test case.
    {
        std::vector<rectangle> vArg = {{0,  0,  10, 10},
                                      {20, 20, 10, 10},
                                      {10, 10, 10, 10},
                                      {5,  5,  10, 10},
                                      {15, 15, 10, 10},
                                      {40, 40, 10, 10}};

        std::vector<rectangle> v = test_intersect_and_unite(vArg);

        ASSERT_EQ(v.size(), 2);
        ASSERT_EQ(v[0], rectangle(0, 0, 30, 30));
        ASSERT_EQ(v[1], rectangle(40, 40, 10, 10));
    }
}