Merging rectangles in C++ [closed]

Question

I have the following code for separating out overlapping rectangles vs. non-overlapping rectangles in C++ 11:

#include <stdio.h>
#include <opencv/cv.h>
#include <opencv/highgui.h>
#include <opencv/cxcore.h>
#include <math.h>
#include <array>

int main() {
    auto detected = get_detected();
    std::vector <Rect> singles;
    std::vector <Rect> overlaps;
    for (auto rect_1: detected) {
        bool isSingle = false;
        for (auto rect_2: detected) {
            if (rect_1 == rect_2) {
                continue;
            }
            bool intersects = ((rect_1 & rect_2).area() > 0);
            if (intersects) {
                isSingle = false;
                break;
            }
        }
        if (isSingle) {
            singles.push_back(rect_1);
        } else {
            overlaps.push_back(rect_1);
        }
    }

}

How do I make this cleaner? I'm thinking of doing singles.push_back(std::move(rect_1));, but I'm not sure if that's a good idea.

I would love some guidance in the right direction.

Answer 1

Bug

        if (intersects) {
            isSingle = false;
            break;
        }

This looks like a bug. The variable isSingle is already false. Setting it to false here does nothing.

Code Review:

You use std::vector but don't include its header.

    std::vector <Rect> overlaps;

You should fix that.

---

References and Const correctness.

This is a big part of C++.

1. If you are not modifying an object, prefer to use reference than making a copy of an object.

2. Prefer const references over normal references to prevent accidental modification.

   for (auto rect_1: detected) {

Here you are making a copy of the object from the array detected into the object rect_1. Personally I would use a const reference to prevent the overhead of a copy:

for (auto const& rect_1: detected) {

---

The code looks mostly fine:

I think the only bug is here:

            if (rect_1 == rect_2) {
                continue;
            }

This tells you if two rectangles are equivalent not if they are the same rectangle. If you have two distinct but otherwise identical rectangle then by my logic they would overlap and thus not be in the single's list.

So you need a way to determine if these are the same object. Personally I would do that by changing your for loops to use references and then comparing the objects' addresses.

    for (auto const& rect_1: detected) {
              ^^^^^^
        ...
        for (auto const& rect_2: detected) {
                  ^^^^^^
            if ( & rect_1 ==  & rect_2) {
                ^^^          ^^^
                continue;
            }

            test(rect_1, rect_2);

Your other alternative is to make sure you never compare an object with itself. This also brings into mind that you do twice as many comparisons as you need to. You compare every rectangle against every other rectangle. But if A & B overlap then we already know that B & A will overlap.

for(std::size_t loop = 0l; loop <  detected.size(); ++loop) {
    for(auto check = loop + 1; check < detected.size(); ++check) {
        test(detected[loop], detected[check]);

---

in the code below "...object addresses" -- aren't rect_1 and rect_2 references already? If so, why can't we just do if (rect_1 == rect_2)

No. Because the == is supposed to compare the equality (is the state the same) of two objects. It is not supposed to be a test of equivalence (is it the same object).

Note: You can declare operator== to test if the objects are the same but that would be terrible practice and would cause a lot of issues with people expecting the normal operation. So don't do that. The above statement is said assuming you are following the normal idioms of the language.

I assume you are coming from a Java like background. The term reference in C++ has a different meaning than in Java. A reference means another name for an object (they are not like Java references (which in C++ we would call pointers). So a reference is another name for an object but the test operator== will compare if the two objects' state are the same (not if they are the same object).

Also, if I use auto const&, I would have to change my return type to vector<Rect&>...is that idiomatic? I think the OpenCV API expects vector<Rect>

No. You can pass a reference to the vector and it will copy the object into the vector. You don't want to hold references in a vector.

Answer 2

Prefer <cstdio> to <stdio.h> and <cmath> to <math.h> in C++ code. You will probably never need the C compatibility headers unless you're writing headers that must also be included in C code. The compatibility headers are less useful in C++ code, because they declare everything in the global namespace rather than neatly in std.

Prefer not including headers at all when you don't use them (as is the case here). Unnecessary includes waste the compiler's time and the reader's brainpower.