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