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.

I see a desire expressed, but no actual question. Or even requirements. Have you tried anything? Like, check each pair? Did it work? What went wrong if it didn't? — Yakk - Adam Nevraumont, Aug 07 '18 at 11:07
I had mentioned using 'algorithm' header file (with brackets) but it was not displayed because I hadn't escaped it - a bit clear now?. You ask if I've tried anything - no. I can't see a solution from std::algorithm that fits my needs. — ZeroDefect, Aug 07 '18 at 11:13
Possible duplicate of [Determine if two rectangles overlap each other?](https://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other) — , Aug 07 '18 at 11:14
@Sembei I don't think it's a duplicate because I've already implemented 'intersects' and 'united'. I'm looking for a function in STL to work on a range of rectangles. — ZeroDefect, Aug 07 '18 at 11:17
So you already have an algorithm that checks if two rectangles overlap and creates the bounding box? What you look then is a way of comparing each pair of rectangles? Modify your question to ask exactly what you need and show what you have so far. — , Aug 07 '18 at 11:18
`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.`, No you don't want that, you already have it, so you shouldn't ask for it in the question. — , Aug 07 '18 at 11:20
Ok thanks for your feedback. Can you suggest on how to rephrase the question? I'm attempting to outline my high-level goal. Yes you're right, I can determine if two rectangles intersect and 'unite' them, but I can't do that for a range of rectangles. Please understand, I'm not trying to be difficult. — ZeroDefect, Aug 07 '18 at 11:24
As far as I know there are no standard algorithm that do that... How many rectangles do you have to process? If you have only a few rectangles, then nested loops woulb be adequate. If you have many thousand, you probably need a more complex algorithm to get a reasonable performance. — Phil1970, Aug 07 '18 at 11:28
Again, it is utterly unclear what you want to do; please try your best to implement it yourself. There are a dozen or more decisions that I have no idea which you'd want in a solution (where does the result go? Does this unioning process commute? Is destructive ok? How many elements we talking about? If A B C pairwise intersect, do we get 1 2 or 3 output rectangles?), and a naive solution (together with why it isn't what you want) answers more than half of them. I get it may be obvious to you, but we cannot read your mind. — Yakk - Adam Nevraumont, Aug 07 '18 at 11:36
Since you keep not posting the code you have so far I'm afraid we cannot really help you. What's `intersects`? a bool that tells you that the rectangle intersects another? What if it intersects more than one? What's `intersected`? The rectangle it intersects with? Shouldn't be the index where that rectangle is in your vector? What you should do is post a clear example of what you want (for example with only 3 or 4 rectangles) and show us the steps and results that you aim to obtain — , Aug 07 '18 at 11:37
You might get `find_if` to work, at least showing you what overlaps with what - but if everything overlaps with everything easle you may end up needing recursion or a bit more thought. You possibly want to avoid "unite"ing the elements of a vector as you iterate over it too - perhaps a new vector? See - there are lots of ways to do this. — doctorlove, Aug 07 '18 at 11:37
I suggest you to manually write the algorithm you'd like to find in ``, chances are high that you will realize that a simple nested loop is sufficient (and replacing a loop with an algorithm not always improves readability) — 463035818_is_not_an_ai, Aug 07 '18 at 11:39
A set of test cases, with your best explanation of what desirable properties each demonstrate, would be *very helpful* — Caleth, Aug 07 '18 at 11:54
Less than 20 rectangles? Just do a double loop to get each pair of rectangles (20*20=400 loops) then for each pair call your function `united` which returns the united rectangles and you are done. — , Aug 07 '18 at 12:04
From your title, I reckon that you want to find the **union** of a set of rectangles. In general, the union of two or more rectangles is not a rectangle, but can be represented by a set of rectangles, possibly smaller than the input. So, do you want to find such a smaller set, possibly the minimum such set? That's a non-trivial exercise in geometry, for which the standard library makes no provision. — Walter, Aug 07 '18 at 12:08

score 0 · Accepted Answer · answered Aug 07 '18 at 14:50

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));
    }
}

I believe the results here will be order dependent; it is easy to see that the results of a single `i=0` pass is. Suppose A intersects B, and B intersects C. If you have {A,B,C} in order then we get {A U B, C} then {A U B U C}. If we have {A, C, B} in order then after the `i=0` pass we have {A U B, C}. I haven't explicitly constructed it, but I'm pretty certain a long enough chain like A B C will result in different outputs depending on order. Maybe not; possibly the n^2 passes prevent this. But I'd be concerned and would want a proof. — Yakk - Adam Nevraumont, Aug 09 '18 at 22:50
The last test case aims to test what you describe albeit with a small set of data. Nonetheless, for further peace of mind, it should be fairly easy to override `operator<` on the `rectangle` and use `std::next_permutation`. — ZeroDefect, Aug 13 '18 at 21:12
my fear is a long chain might not collapse; no unit test can rule out it. You would need a proof. — Yakk - Adam Nevraumont, Aug 13 '18 at 22:04

Find bounding set of rectangles

1 Answers1