Merge lp:~vanvugt/mir/Rectangle-contains-Rectangle into lp:mir

[Daniel van Vugt]

Add method for testing if Rectangle::contains(Rectangle), which is the basis
of any occlusion detection.

Prerequisite for fixing bug 1227739.

[PS Jenkins bot (ps-jenkins)]

PASSED: Continuous integration, rev:1119
http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-ci/141/
Executed test runs:
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-android-saucy-i386-build/2301
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-clang-saucy-amd64-build/2186
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-saucy-amd64-ci/138
        deb: http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-saucy-amd64-ci/138/artifact/work/output/*zip*/output.zip

Click here to trigger a rebuild:
http://10.97.0.26:8080/job/mir-team-mir-development-branch-ci/141/rebuild

review: Approve (continuous-integration)

[Alan Griffiths (alan-griffiths)]

22 + return r.top_left.x >= top_left.x &&
23 + r.top_left.x.as_int() + r.size.width.as_int() <=
24 + top_left.x.as_int() + size.width.as_int() &&
25 + r.top_left.y >= top_left.y &&
26 + r.top_left.y.as_int() + r.size.height.as_int() <=
27 + top_left.y.as_int() + size.height.as_int();

I do find this a bit hard to parse. I'd write something like:

    auto const btmright = bottom_right();
    auto const r_btmright = r.bottom_right();

    return r.top_left.x >= top_left.x && r.top_left.y >= top_left.y &&
           r_btmright.x <= btmright.x && r_btmright.y <= btmright.y;

review: Approve

[Alexandros Frantzis (afrantzis)]

The current code allows an empty rectangle (x,y)(0x0) to contain another empty rectangle (x,y)(0x0).

review: Needs Fixing

[Daniel van Vugt (vanvugt)]

Alexandros,

I believe that is acceptable for emptiness to contain emptiness. It certainly doesn't break any intended use cases I can think of, or represent any problem in theory. Does it?

[Alexandros Frantzis (afrantzis)]

> I believe that is acceptable for emptiness to contain emptiness. It certainly doesn't break
> any intended use cases I can think of, or represent any problem in theory. Does it?

I think that for our use cases it may be a bit surprising for an empty rectangle to contain anything at all, but I can't think of a concrete example where this would be a major problem. It just means that all code needs to be ready to handle empty rectangles, even if it's run conditionally after a rect.contains(rect) check.

From a theoretical POV, if an empty rectangle is just the empty set of pixels, then we need (x,y)(0x0) to be contained by any (x',y')(0x0). Right now (x,y)(0x0) only contains itself.

I think we should be consistent by either making empty rectangles not contain anything, or by making all empty rectangles contain all other empty rectangles, although it may not make any difference practically either way.

[Alan Griffiths (alan-griffiths)]

> The current code allows an empty rectangle (x,y)(0x0) to contain another empty
> rectangle (x,y)(0x0).

What is special about empty rectangles?

It seems perfectly reasonable that two rectangles of the same size and location each contain the other. (Or that a rectangle contains itself.)

[Alexandros Frantzis (afrantzis)]

> What is special about empty rectangles?

> It seems perfectly reasonable that two rectangles of the same size and location
> each contain the other. (Or that a rectangle contains itself.)

It depends on what model we are using for rectangles in our discrete 2D domain. If we consider a rectangle to be a set (in the formal sense) of pixels, then we should be following the rules of sets. In this case, all rectangles with W=0 H=0 map to the empty set, so they should all contain each other.

If we are not following the set model, and then we can make our own rules for cases like this.

Anyway, since this is not likely to have any impact in practice (with the exception of "It just means that all code needs to be ready to handle empty rectangles, even if it's run conditionally after a rect.contains(rect) check"), I am OK with what is proposed, and we can reconsider if it becomes a problem.

I would like to see a comment describing the expected behavior, though (=> Needs Fixing).

review: Needs Fixing

[Daniel van Vugt (vanvugt)]

I have no preference for the behaviour of empty rectangles. And I think we should leave the behaviour "officially undefined" until there's a good enough reason to define it.

If we declare rules for empty rectangles now without having a reason, we risk needing to change them in future if a use case is found.

[Alexandros Frantzis (afrantzis)]

> I have no preference for the behaviour of empty rectangles. And I think we should leave the behaviour
> "officially undefined" until there's a good enough reason to define it.

Empty rectangles are not an edge case we can ignore, we need some form of support for them. We are implicitly defining the behavior, and code will eventually depend on it in some way, even if it's in the form of extra logic to avoid "undefined" behavior. So, UB gains us nothing really. We are better off defining the behavior and if we need to change it in the future, then so be it.

[PS Jenkins bot (ps-jenkins)]

PASSED: Continuous integration, rev:1121
http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-ci/157/
Executed test runs:
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-android-saucy-i386-build/2338
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-clang-saucy-amd64-build/2223
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-saucy-amd64-ci/154
        deb: http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-saucy-amd64-ci/154/artifact/work/output/*zip*/output.zip

Click here to trigger a rebuild:
http://10.97.0.26:8080/job/mir-team-mir-development-branch-ci/157/rebuild

review: Approve (continuous-integration)

[Alexandros Frantzis (afrantzis)]

100 + EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,0}}));
104 + EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,0}}));

125 + EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,0}}));
129 + EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,0}}));

Is there a reason to recheck for these?

Having a unit test for the expected behavior of empty rectangles is, of course, desirable, but I think a comment in the code would be more helpful for users of the class.

review: Needs Fixing

[Kevin DuBois (kdub)]

nit:
int const vs const int
most other places we have "int const"
http://unity.ubuntu.com/mir/cppguide/index.html?showone=Use_of_const#Use_of_const

i'm fine with empty rectangles being treated as points (or lines).

[Daniel van Vugt (vanvugt)]

Alexandros:
Fixed and fixed. I think there was some copy/paste or search/replace mistake there.

Kevin:
The cppguide says it "favors" the late const form without providing any solid justification other than loosely mentioning "This keeps the const with the type modifier (& or *)". So firstly, that's not a justification. The C/C++ language specs clearly define "const" as applying to the type and not the type modifier. So late const is misleading in the least. It creates confusion if you try to express "const T * const p", which is more clearly stated with prefix const. And the suffix const form is syntactically impossible for expressing "T * const p". So I think we need to update the cppguide... I mentioned this on the mailing list some time back.

[PS Jenkins bot (ps-jenkins)]

PASSED: Continuous integration, rev:1124
http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-ci/166/
Executed test runs:
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-android-saucy-i386-build/2360
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-clang-saucy-amd64-build/2245
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-saucy-amd64-ci/163
        deb: http://jenkins.qa.ubuntu.com/job/mir-team-mir-development-branch-saucy-amd64-ci/163/artifact/work/output/*zip*/output.zip

Click here to trigger a rebuild:
http://10.97.0.26:8080/job/mir-team-mir-development-branch-ci/166/rebuild

review: Approve (continuous-integration)

[Alexandros Frantzis (afrantzis)]

Looks good.

review: Approve

=== modified file 'include/shared/mir/geometry/rectangle.h'
--- include/shared/mir/geometry/rectangle.h	2013-08-28 03:41:48 +0000
+++ include/shared/mir/geometry/rectangle.h	2013-10-15 03:28:47 +0000
@@ -43,6 +43,15 @@
      */
     Point bottom_right() const;
     bool contains(Point const& p) const;
+
+    /**
+     * Test if the rectangle contains another.
+     *
+     * Note that an empty rectangle can still contain other empty rectangles,
+     * which are treated as points or lines of thickness zero.
+     */
+    bool contains(Rectangle const& r) const;
+
     bool overlaps(Rectangle const& r) const;
 };
 
 
=== modified file 'src/shared/geometry/rectangle.cpp'
--- src/shared/geometry/rectangle.cpp	2013-08-28 03:41:48 +0000
+++ src/shared/geometry/rectangle.cpp	2013-10-15 03:28:47 +0000
@@ -28,6 +28,16 @@
             top_left.y.as_int() + size.height.as_int()};
 }
 
+bool geom::Rectangle::contains(Rectangle const& r) const
+{
+    return r.top_left.x >= top_left.x &&
+           r.top_left.x.as_int() + r.size.width.as_int() <=
+               top_left.x.as_int() + size.width.as_int() &&
+           r.top_left.y >= top_left.y &&
+           r.top_left.y.as_int() + r.size.height.as_int() <=
+               top_left.y.as_int() + size.height.as_int();
+}
+
 bool geom::Rectangle::contains(Point const& p) const
 {
     if (size.width == geom::Width{0} || size.height == geom::Height{0})
 
=== modified file 'tests/unit-tests/geometry/test-rectangle.cpp'
--- tests/unit-tests/geometry/test-rectangle.cpp	2013-08-28 03:41:48 +0000
+++ tests/unit-tests/geometry/test-rectangle.cpp	2013-10-15 03:28:47 +0000
@@ -56,7 +56,97 @@
     EXPECT_EQ(Point(2,2), rect_empty.bottom_right());
 }
 
-TEST(geometry, rectangle_contains)
+TEST(geometry, rectangle_contains_rectangle)
+{
+    using namespace testing;
+    using namespace geom;
+
+    const int left = 3;
+    const int top = 3;
+    const int width = 3;
+    const int height = 3;
+    const Rectangle r{{left,top}, {width,height}};
+
+    const int right = left + width;
+    const int bottom = top + height;
+
+    // Test for _every_ rectangle contained in r
+    for (int y = top; y <= bottom; y++)
+    {
+        for (int x = left; x <= right; x++)
+        {
+            const int max_height = bottom - y;
+            const int max_width = right - x;
+            for (int h = 0; h <= max_height; h++)
+            {
+                for (int w = 0; w <= max_width; w++)
+                {
+                    EXPECT_TRUE(r.contains(Rectangle{{x,y}, {w,h}}));
+                }
+            }
+
+            EXPECT_FALSE(r.contains(Rectangle{{x,y}, {max_width+1,max_height}}));
+            EXPECT_FALSE(r.contains(Rectangle{{x,y}, {max_width,max_height+1}}));
+        }
+    }
+
+    EXPECT_FALSE(r.contains(Rectangle{{2,2}, {5,5}}));
+    EXPECT_FALSE(r.contains(Rectangle{{2,2}, {1,1}}));
+    EXPECT_FALSE(r.contains(Rectangle{{-4,-3}, {10,10}}));
+
+    EXPECT_FALSE(r.contains(Rectangle{{1,3}, {3,3}}));
+    EXPECT_FALSE(r.contains(Rectangle{{3,1}, {3,3}}));
+    EXPECT_FALSE(r.contains(Rectangle{{5,3}, {3,3}}));
+    EXPECT_FALSE(r.contains(Rectangle{{3,5}, {3,3}}));
+
+    EXPECT_FALSE(r.contains(Rectangle{{9,9}, {1,1}}));
+    EXPECT_FALSE(r.contains(Rectangle{{-6,-7}, {3,4}}));
+}
+
+TEST(geometry, empty_rectangle_contains_point_only)
+{
+    using namespace testing;
+    using namespace geom;
+
+    const int left = 3;
+    const int top = 3;
+    const Rectangle r{{left,top}, {0,0}};
+
+    EXPECT_TRUE(r.contains(Rectangle{{left,top}, {0,0}}));
+
+    EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,0}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left,top}, {0,1}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,1}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left-1,top}, {3,0}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left-1,top}, {0,0}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left,top+1}, {0,0}}));
+}
+
+TEST(geometry, elongated_empty_rectangle_contains_points_only)
+{
+    using namespace testing;
+    using namespace geom;
+
+    const int left = 3;
+    const int top = 3;
+    const Rectangle r{{left,top}, {0,3}};
+
+    EXPECT_TRUE(r.contains(Rectangle{{left,top}, {0,0}}));
+    EXPECT_TRUE(r.contains(Rectangle{{left,top+1}, {0,0}}));
+    EXPECT_TRUE(r.contains(Rectangle{{left,top+2}, {0,0}}));
+    EXPECT_TRUE(r.contains(Rectangle{{left,top+3}, {0,0}}));
+
+    EXPECT_TRUE(r.contains(Rectangle{{left,top}, {0,1}}));
+    EXPECT_TRUE(r.contains(Rectangle{{left,top+1}, {0,2}}));
+
+    EXPECT_FALSE(r.contains(Rectangle{{left,top+4}, {0,0}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,0}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left,top}, {1,1}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left-1,top}, {3,0}}));
+    EXPECT_FALSE(r.contains(Rectangle{{left-1,top}, {0,0}}));
+}
+
+TEST(geometry, rectangle_contains_point)
 {
     using namespace testing;
     using namespace geom;