1 // Copyright 2012 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //     http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 
16 // Author: ericv@google.com (Eric Veach)
17 //
18 // Most of the R2Rect methods have trivial implementations in terms of the
19 // R1Interval class, so most of the testing is done in that unit test.
20 
21 #include "s2/r2rect.h"
22 
23 #include <gtest/gtest.h>
24 #include "s2/r2.h"
25 
TestIntervalOps(const R2Rect & x,const R2Rect & y,const char * expected_rexion,const R2Rect & expected_union,const R2Rect & expected_intersection)26 static void TestIntervalOps(const R2Rect& x, const R2Rect& y,
27                             const char* expected_rexion,
28                             const R2Rect& expected_union,
29                             const R2Rect& expected_intersection) {
30   // Test all of the interval operations on the given pair of intervals.
31   // "expected_rexion" is a sequence of "T" and "F" characters corresponding
32   // to the expected results of Contains(), InteriorContains(), Intersects(),
33   // and InteriorIntersects() respectively.
34 
35   EXPECT_EQ(expected_rexion[0] == 'T', x.Contains(y));
36   EXPECT_EQ(expected_rexion[1] == 'T', x.InteriorContains(y));
37   EXPECT_EQ(expected_rexion[2] == 'T', x.Intersects(y));
38   EXPECT_EQ(expected_rexion[3] == 'T', x.InteriorIntersects(y));
39 
40   EXPECT_EQ(x.Union(y) == x, x.Contains(y));
41   EXPECT_EQ(!x.Intersection(y).is_empty(), x.Intersects(y));
42 
43   EXPECT_EQ(expected_union, x.Union(y));
44   EXPECT_EQ(expected_intersection, x.Intersection(y));
45 
46   R2Rect r = x;
47   r.AddRect(y);
48   EXPECT_EQ(expected_union, r);
49   if (y.GetSize() == R2Point(0, 0)) {
50     r = x;
51     r.AddPoint(y.lo());
52     EXPECT_EQ(expected_union, r);
53   }
54 }
55 
TEST(R2Rect,EmptyRectangles)56 TEST(R2Rect, EmptyRectangles) {
57   // Test basic properties of empty rectangles.
58   R2Rect empty = R2Rect::Empty();
59   EXPECT_TRUE(empty.is_valid());
60   EXPECT_TRUE(empty.is_empty());
61 }
62 
TEST(R2Rect,ConstructorsAndAccessors)63 TEST(R2Rect, ConstructorsAndAccessors) {
64   // Check various constructors and accessor methods.
65   R2Rect r = R2Rect(R2Point(0.1, 0), R2Point(0.25, 1));
66   EXPECT_EQ(0.1, r.x().lo());
67   EXPECT_EQ(0.25, r.x().hi());
68   EXPECT_EQ(0.0, r.y().lo());
69   EXPECT_EQ(1.0, r.y().hi());
70 
71   EXPECT_EQ(0.1, r[0][0]);
72   EXPECT_EQ(0.25, r[0][1]);
73   EXPECT_EQ(0.0, r[1][0]);
74   EXPECT_EQ(1.0, r[1][1]);
75 
76   EXPECT_EQ(R1Interval(0.1, 0.25), r.x());
77   EXPECT_EQ(R1Interval(0, 1), r.y());
78 
79   EXPECT_EQ(R1Interval(0.1, 0.25), r[0]);
80   EXPECT_EQ(R1Interval(0, 1), r[1]);
81 
82   r[0] = R1Interval(3, 4);
83   r[1][0] = 5;
84   r[1][1] = 6;
85   EXPECT_EQ(R1Interval(3, 4), r[0]);
86   EXPECT_EQ(R1Interval(5, 6), r[1]);
87 
88   R2Rect r2;
89   EXPECT_TRUE(r2.is_empty());
90 }
91 
TEST(R2Rect,FromCenterSize)92 TEST(R2Rect, FromCenterSize) {
93   // FromCenterSize()
94   EXPECT_TRUE(R2Rect::FromCenterSize(R2Point(0.3, 0.5), R2Point(0.2, 0.4)).
95               ApproxEquals(R2Rect(R2Point(0.2, 0.3), R2Point(0.4, 0.7))));
96   EXPECT_TRUE(R2Rect::FromCenterSize(R2Point(1, 0.1), R2Point(0, 2)).
97               ApproxEquals(R2Rect(R2Point(1, -0.9), R2Point(1, 1.1))));
98 }
99 
TEST(R2Rect,FromPoint)100 TEST(R2Rect, FromPoint) {
101   // FromPoint(), FromPointPair()
102   R2Rect d1 = R2Rect(R2Point(0.1, 0), R2Point(0.25, 1));
103   EXPECT_EQ(R2Rect(d1.lo(), d1.lo()), R2Rect::FromPoint(d1.lo()));
104   EXPECT_EQ(R2Rect(R2Point(0.15, 0.3), R2Point(0.35, 0.9)),
105             R2Rect::FromPointPair(R2Point(0.15, 0.9), R2Point(0.35, 0.3)));
106   EXPECT_EQ(R2Rect(R2Point(0.12, 0), R2Point(0.83, 0.5)),
107             R2Rect::FromPointPair(R2Point(0.83, 0), R2Point(0.12, 0.5)));
108 }
109 
TEST(R2Rect,SimplePredicates)110 TEST(R2Rect, SimplePredicates) {
111   // GetCenter(), GetVertex(), Contains(R2Point), InteriorContains(R2Point).
112   R2Point sw1 = R2Point(0, 0.25);
113   R2Point ne1 = R2Point(0.5, 0.75);
114   R2Rect r1(sw1, ne1);
115 
116   EXPECT_EQ(R2Point(0.25, 0.5), r1.GetCenter());
117   EXPECT_EQ(R2Point(0, 0.25), r1.GetVertex(0));
118   EXPECT_EQ(R2Point(0.5, 0.25), r1.GetVertex(1));
119   EXPECT_EQ(R2Point(0.5, 0.75), r1.GetVertex(2));
120   EXPECT_EQ(R2Point(0, 0.75), r1.GetVertex(3));
121   EXPECT_TRUE(r1.Contains(R2Point(0.2, 0.4)));
122   EXPECT_FALSE(r1.Contains(R2Point(0.2, 0.8)));
123   EXPECT_FALSE(r1.Contains(R2Point(-0.1, 0.4)));
124   EXPECT_FALSE(r1.Contains(R2Point(0.6, 0.1)));
125   EXPECT_TRUE(r1.Contains(sw1));
126   EXPECT_TRUE(r1.Contains(ne1));
127   EXPECT_FALSE(r1.InteriorContains(sw1));
128   EXPECT_FALSE(r1.InteriorContains(ne1));
129 
130   // Make sure that GetVertex() returns vertices in CCW order.
131   for (int k = 0; k < 4; ++k) {
132     R2Point a = r1.GetVertex(k - 1);
133     R2Point b = r1.GetVertex(k);
134     R2Point c = r1.GetVertex(k + 1);
135     EXPECT_GT((b - a).Ortho().DotProd(c - a), 0);
136   }
137 }
138 
TEST(R2Rect,IntervalOperations)139 TEST(R2Rect, IntervalOperations) {
140   // Contains(R2Rect), InteriorContains(R2Rect),
141   // Intersects(), InteriorIntersects(), Union(), Intersection().
142   //
143   // Much more testing of these methods is done in s1interval_test
144   // and r1interval_test.
145 
146   R2Rect empty = R2Rect::Empty();
147   R2Point sw1 = R2Point(0, 0.25);
148   R2Point ne1 = R2Point(0.5, 0.75);
149   R2Rect r1(sw1, ne1);
150   R2Rect r1_mid = R2Rect(R2Point(0.25, 0.5), R2Point(0.25, 0.5));
151   R2Rect r_sw1(sw1, sw1);
152   R2Rect r_ne1(ne1, ne1);
153 
154   TestIntervalOps(r1, r1_mid, "TTTT", r1, r1_mid);
155   TestIntervalOps(r1, r_sw1, "TFTF", r1, r_sw1);
156   TestIntervalOps(r1, r_ne1, "TFTF", r1, r_ne1);
157 
158   EXPECT_EQ(R2Rect(R2Point(0, 0.25), R2Point(0.5, 0.75)), r1);
159   TestIntervalOps(r1, R2Rect(R2Point(0.45, 0.1), R2Point(0.75, 0.3)), "FFTT",
160                   R2Rect(R2Point(0, 0.1), R2Point(0.75, 0.75)),
161                   R2Rect(R2Point(0.45, 0.25), R2Point(0.5, 0.3)));
162   TestIntervalOps(r1, R2Rect(R2Point(0.5, 0.1), R2Point(0.7, 0.3)), "FFTF",
163                   R2Rect(R2Point(0, 0.1), R2Point(0.7, 0.75)),
164                   R2Rect(R2Point(0.5, 0.25), R2Point(0.5, 0.3)));
165   TestIntervalOps(r1, R2Rect(R2Point(0.45, 0.1), R2Point(0.7, 0.25)), "FFTF",
166                   R2Rect(R2Point(0, 0.1), R2Point(0.7, 0.75)),
167                   R2Rect(R2Point(0.45, 0.25), R2Point(0.5, 0.25)));
168 
169   TestIntervalOps(R2Rect(R2Point(0.1, 0.2), R2Point(0.1, 0.3)),
170                   R2Rect(R2Point(0.15, 0.7), R2Point(0.2, 0.8)), "FFFF",
171                   R2Rect(R2Point(0.1, 0.2), R2Point(0.2, 0.8)),
172                   empty);
173 
174   // Check that the intersection of two rectangles that overlap in x but not y
175   // is valid, and vice versa.
176   TestIntervalOps(R2Rect(R2Point(0.1, 0.2), R2Point(0.4, 0.5)),
177                   R2Rect(R2Point(0, 0), R2Point(0.2, 0.1)), "FFFF",
178                   R2Rect(R2Point(0, 0), R2Point(0.4, 0.5)), empty);
179   TestIntervalOps(R2Rect(R2Point(0, 0), R2Point(0.1, 0.3)),
180                   R2Rect(R2Point(0.2, 0.1), R2Point(0.3, 0.4)), "FFFF",
181                   R2Rect(R2Point(0, 0), R2Point(0.3, 0.4)), empty);
182 }
183 
TEST(R2Rect,AddPoint)184 TEST(R2Rect, AddPoint) {
185   // AddPoint()
186   R2Point sw1 = R2Point(0, 0.25);
187   R2Point ne1 = R2Point(0.5, 0.75);
188   R2Rect r1(sw1, ne1);
189 
190   R2Rect r2 = R2Rect::Empty();
191   r2.AddPoint(R2Point(0, 0.25));
192   r2.AddPoint(R2Point(0.5, 0.25));
193   r2.AddPoint(R2Point(0, 0.75));
194   r2.AddPoint(R2Point(0.1, 0.4));
195   EXPECT_EQ(r1, r2);
196 }
197 
TEST(R2Rect,Project)198 TEST(R2Rect, Project) {
199   R2Rect r1(R1Interval(0, 0.5), R1Interval(0.25, 0.75));
200 
201   EXPECT_EQ(R2Point(0, 0.25), r1.Project(R2Point(-0.01, 0.24)));
202   EXPECT_EQ(R2Point(0, 0.48), r1.Project(R2Point(-5.0, 0.48)));
203   EXPECT_EQ(R2Point(0, 0.75), r1.Project(R2Point(-5.0, 2.48)));
204   EXPECT_EQ(R2Point(0.19, 0.75), r1.Project(R2Point(0.19, 2.48)));
205   EXPECT_EQ(R2Point(0.5, 0.75), r1.Project(R2Point(6.19, 2.48)));
206   EXPECT_EQ(R2Point(0.5, 0.53), r1.Project(R2Point(6.19, 0.53)));
207   EXPECT_EQ(R2Point(0.5, 0.25), r1.Project(R2Point(6.19, -2.53)));
208   EXPECT_EQ(R2Point(0.33, 0.25), r1.Project(R2Point(0.33, -2.53)));
209   EXPECT_EQ(R2Point(0.33, 0.37), r1.Project(R2Point(0.33, 0.37)));
210 }
211 
TEST(R2Rect,Expanded)212 TEST(R2Rect, Expanded) {
213   // Expanded()
214   EXPECT_TRUE(R2Rect::Empty().Expanded(R2Point(0.1, 0.3)).is_empty());
215   EXPECT_TRUE(R2Rect::Empty().Expanded(R2Point(-0.1, -0.3)).is_empty());
216   EXPECT_TRUE(R2Rect(R2Point(0.2, 0.4), R2Point(0.3, 0.7)).
217               Expanded(R2Point(0.1, 0.3)).
218               ApproxEquals(R2Rect(R2Point(0.1, 0.1), R2Point(0.4, 1.0))));
219   EXPECT_TRUE(R2Rect(R2Point(0.2, 0.4), R2Point(0.3, 0.7)).
220               Expanded(R2Point(-0.1, 0.3)).is_empty());
221   EXPECT_TRUE(R2Rect(R2Point(0.2, 0.4), R2Point(0.3, 0.7)).
222               Expanded(R2Point(0.1, -0.2)).is_empty());
223   EXPECT_TRUE(R2Rect(R2Point(0.2, 0.4), R2Point(0.3, 0.7)).
224               Expanded(R2Point(0.1, -0.1)).
225               ApproxEquals(R2Rect(R2Point(0.1, 0.5), R2Point(0.4, 0.6))));
226   EXPECT_TRUE(R2Rect(R2Point(0.2, 0.4), R2Point(0.3, 0.7)).Expanded(0.1).
227               ApproxEquals(R2Rect(R2Point(0.1, 0.3), R2Point(0.4, 0.8))));
228 }
229