1 // Copyright 2013 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 #include "s2/s2lax_polygon_shape.h"
19
20 #include <vector>
21
22 #include <gtest/gtest.h>
23 #include "s2/third_party/absl/memory/memory.h"
24 #include "s2/mutable_s2shape_index.h"
25 #include "s2/s2cap.h"
26 #include "s2/s2contains_point_query.h"
27 #include "s2/s2lax_loop_shape.h"
28 #include "s2/s2polygon.h"
29 #include "s2/s2shapeutil_contains_brute_force.h"
30 #include "s2/s2testing.h"
31 #include "s2/s2text_format.h"
32
33 using absl::make_unique;
34 using s2textformat::MakePolygonOrDie;
35 using std::unique_ptr;
36 using std::vector;
37
TEST(S2LaxPolygonShape,EmptyPolygon)38 TEST(S2LaxPolygonShape, EmptyPolygon) {
39 S2LaxPolygonShape shape((S2Polygon()));
40 EXPECT_EQ(0, shape.num_loops());
41 EXPECT_EQ(0, shape.num_vertices());
42 EXPECT_EQ(0, shape.num_edges());
43 EXPECT_EQ(0, shape.num_chains());
44 EXPECT_EQ(2, shape.dimension());
45 EXPECT_TRUE(shape.is_empty());
46 EXPECT_FALSE(shape.is_full());
47 EXPECT_FALSE(shape.GetReferencePoint().contained);
48 }
49
TEST(S2LaxPolygonShape,FullPolygon)50 TEST(S2LaxPolygonShape, FullPolygon) {
51 S2LaxPolygonShape shape(S2Polygon(s2textformat::MakeLoopOrDie("full")));
52 EXPECT_EQ(1, shape.num_loops());
53 EXPECT_EQ(0, shape.num_vertices());
54 EXPECT_EQ(0, shape.num_edges());
55 EXPECT_EQ(1, shape.num_chains());
56 EXPECT_EQ(2, shape.dimension());
57 EXPECT_FALSE(shape.is_empty());
58 EXPECT_TRUE(shape.is_full());
59 EXPECT_TRUE(shape.GetReferencePoint().contained);
60 }
61
TEST(S2LaxPolygonShape,SingleVertexPolygon)62 TEST(S2LaxPolygonShape, SingleVertexPolygon) {
63 // S2Polygon doesn't support single-vertex loops, so we need to construct
64 // the S2LaxPolygonShape directly.
65 vector<vector<S2Point>> loops;
66 loops.push_back(s2textformat::ParsePoints("0:0"));
67 S2LaxPolygonShape shape(loops);
68 EXPECT_EQ(1, shape.num_loops());
69 EXPECT_EQ(1, shape.num_vertices());
70 EXPECT_EQ(1, shape.num_edges());
71 EXPECT_EQ(1, shape.num_chains());
72 EXPECT_EQ(0, shape.chain(0).start);
73 EXPECT_EQ(1, shape.chain(0).length);
74 auto edge = shape.edge(0);
75 EXPECT_EQ(loops[0][0], edge.v0);
76 EXPECT_EQ(loops[0][0], edge.v1);
77 EXPECT_TRUE(edge == shape.chain_edge(0, 0));
78 EXPECT_EQ(2, shape.dimension());
79 EXPECT_FALSE(shape.is_empty());
80 EXPECT_FALSE(shape.is_full());
81 EXPECT_FALSE(shape.GetReferencePoint().contained);
82 }
83
TEST(S2LaxPolygonShape,SingleLoopPolygon)84 TEST(S2LaxPolygonShape, SingleLoopPolygon) {
85 // Test S2Polygon constructor.
86 vector<S2Point> vertices = s2textformat::ParsePoints("0:0, 0:1, 1:1, 1:0");
87 S2LaxPolygonShape shape(S2Polygon(make_unique<S2Loop>(vertices)));
88 EXPECT_EQ(1, shape.num_loops());
89 EXPECT_EQ(vertices.size(), shape.num_vertices());
90 EXPECT_EQ(vertices.size(), shape.num_loop_vertices(0));
91 EXPECT_EQ(vertices.size(), shape.num_edges());
92 EXPECT_EQ(1, shape.num_chains());
93 EXPECT_EQ(0, shape.chain(0).start);
94 EXPECT_EQ(vertices.size(), shape.chain(0).length);
95 for (int i = 0; i < vertices.size(); ++i) {
96 EXPECT_EQ(vertices[i], shape.loop_vertex(0, i));
97 auto edge = shape.edge(i);
98 EXPECT_EQ(vertices[i], edge.v0);
99 EXPECT_EQ(vertices[(i + 1) % vertices.size()], edge.v1);
100 EXPECT_EQ(edge.v0, shape.chain_edge(0, i).v0);
101 EXPECT_EQ(edge.v1, shape.chain_edge(0, i).v1);
102 }
103 EXPECT_EQ(2, shape.dimension());
104 EXPECT_FALSE(shape.is_empty());
105 EXPECT_FALSE(shape.is_full());
106 EXPECT_FALSE(s2shapeutil::ContainsBruteForce(shape, S2::Origin()));
107 }
108
TEST(S2LaxPolygonShape,MultiLoopPolygon)109 TEST(S2LaxPolygonShape, MultiLoopPolygon) {
110 // Test vector<vector<S2Point>> constructor. Make sure that the loops are
111 // oriented so that the interior of the polygon is always on the left.
112 vector<S2LaxPolygonShape::Loop> loops = {
113 s2textformat::ParsePoints("0:0, 0:3, 3:3"), // CCW
114 s2textformat::ParsePoints("1:1, 2:2, 1:2") // CW
115 };
116 S2LaxPolygonShape shape(loops);
117
118 EXPECT_EQ(loops.size(), shape.num_loops());
119 int num_vertices = 0;
120 EXPECT_EQ(loops.size(), shape.num_chains());
121 for (int i = 0; i < loops.size(); ++i) {
122 EXPECT_EQ(loops[i].size(), shape.num_loop_vertices(i));
123 EXPECT_EQ(num_vertices, shape.chain(i).start);
124 EXPECT_EQ(loops[i].size(), shape.chain(i).length);
125 for (int j = 0; j < loops[i].size(); ++j) {
126 EXPECT_EQ(loops[i][j], shape.loop_vertex(i, j));
127 auto edge = shape.edge(num_vertices + j);
128 EXPECT_EQ(loops[i][j], edge.v0);
129 EXPECT_EQ(loops[i][(j + 1) % loops[i].size()], edge.v1);
130 }
131 num_vertices += loops[i].size();
132 }
133 EXPECT_EQ(num_vertices, shape.num_vertices());
134 EXPECT_EQ(num_vertices, shape.num_edges());
135 EXPECT_EQ(2, shape.dimension());
136 EXPECT_FALSE(shape.is_empty());
137 EXPECT_FALSE(shape.is_full());
138 EXPECT_FALSE(s2shapeutil::ContainsBruteForce(shape, S2::Origin()));
139 }
140
TEST(S2LaxPolygonShape,MultiLoopS2Polygon)141 TEST(S2LaxPolygonShape, MultiLoopS2Polygon) {
142 // Verify that the orientation of loops representing holes is reversed when
143 // converting from an S2Polygon to an S2LaxPolygonShape.
144 auto polygon = MakePolygonOrDie("0:0, 0:3, 3:3; 1:1, 1:2, 2:2");
145 S2LaxPolygonShape shape(*polygon);
146 for (int i = 0; i < polygon->num_loops(); ++i) {
147 S2Loop* loop = polygon->loop(i);
148 for (int j = 0; j < loop->num_vertices(); ++j) {
149 EXPECT_EQ(loop->oriented_vertex(j),
150 shape.loop_vertex(i, j));
151 }
152 }
153 }
154
TEST(S2LaxPolygonShape,ManyLoopPolygon)155 TEST(S2LaxPolygonShape, ManyLoopPolygon) {
156 // Test a polygon with enough loops so that cumulative_vertices_ is used.
157 vector<vector<S2Point>> loops;
158 for (int i = 0; i < 100; ++i) {
159 S2Point center(S2LatLng::FromDegrees(0, i));
160 loops.push_back(
161 S2Testing::MakeRegularPoints(center, S1Angle::Degrees(0.1),
162 S2Testing::rnd.Uniform(3)));
163 }
164 S2LaxPolygonShape shape(loops);
165
166 EXPECT_EQ(loops.size(), shape.num_loops());
167 int num_vertices = 0;
168 EXPECT_EQ(loops.size(), shape.num_chains());
169 for (int i = 0; i < loops.size(); ++i) {
170 EXPECT_EQ(loops[i].size(), shape.num_loop_vertices(i));
171 EXPECT_EQ(num_vertices, shape.chain(i).start);
172 EXPECT_EQ(loops[i].size(), shape.chain(i).length);
173 for (int j = 0; j < loops[i].size(); ++j) {
174 EXPECT_EQ(loops[i][j], shape.loop_vertex(i, j));
175 auto edge = shape.edge(num_vertices + j);
176 EXPECT_EQ(loops[i][j], edge.v0);
177 EXPECT_EQ(loops[i][(j + 1) % loops[i].size()], edge.v1);
178 }
179 num_vertices += loops[i].size();
180 }
181 EXPECT_EQ(num_vertices, shape.num_vertices());
182 EXPECT_EQ(num_vertices, shape.num_edges());
183 }
184
TEST(S2LaxPolygonShape,DegenerateLoops)185 TEST(S2LaxPolygonShape, DegenerateLoops) {
186 vector<S2LaxPolygonShape::Loop> loops = {
187 s2textformat::ParsePoints("1:1, 1:2, 2:2, 1:2, 1:3, 1:2, 1:1"),
188 s2textformat::ParsePoints("0:0, 0:3, 0:6, 0:9, 0:6, 0:3, 0:0"),
189 s2textformat::ParsePoints("5:5, 6:6")
190 };
191 S2LaxPolygonShape shape(loops);
192 EXPECT_FALSE(shape.GetReferencePoint().contained);
193 }
194
TEST(S2LaxPolygonShape,InvertedLoops)195 TEST(S2LaxPolygonShape, InvertedLoops) {
196 vector<S2LaxPolygonShape::Loop> loops = {
197 s2textformat::ParsePoints("1:2, 1:1, 2:2"),
198 s2textformat::ParsePoints("3:4, 3:3, 4:4")
199 };
200 S2LaxPolygonShape shape(loops);
201 EXPECT_TRUE(s2shapeutil::ContainsBruteForce(shape, S2::Origin()));
202 }
203
CompareS2LoopToShape(const S2Loop & loop,unique_ptr<S2Shape> shape)204 void CompareS2LoopToShape(const S2Loop& loop, unique_ptr<S2Shape> shape) {
205 MutableS2ShapeIndex index;
206 index.Add(std::move(shape));
207 S2Cap cap = loop.GetCapBound();
208 auto query = MakeS2ContainsPointQuery(&index);
209 for (int iter = 0; iter < 100; ++iter) {
210 S2Point point = S2Testing::SamplePoint(cap);
211 EXPECT_EQ(loop.Contains(point),
212 query.ShapeContains(*index.shape(0), point));
213 }
214 }
215
TEST(S2LaxPolygonShape,CompareToS2Loop)216 TEST(S2LaxPolygonShape, CompareToS2Loop) {
217 for (int iter = 0; iter < 100; ++iter) {
218 S2Testing::Fractal fractal;
219 fractal.set_max_level(S2Testing::rnd.Uniform(5));
220 fractal.set_fractal_dimension(1 + S2Testing::rnd.RandDouble());
221 S2Point center = S2Testing::RandomPoint();
222 unique_ptr<S2Loop> loop(fractal.MakeLoop(
223 S2Testing::GetRandomFrameAt(center), S1Angle::Degrees(5)));
224
225 // Compare S2Loop to S2LaxLoopShape.
226 CompareS2LoopToShape(*loop, make_unique<S2LaxLoopShape>(*loop));
227
228 // Compare S2Loop to S2LaxPolygonShape.
229 vector<S2LaxPolygonShape::Loop> loops(
230 1, vector<S2Point>(&loop->vertex(0),
231 &loop->vertex(0) + loop->num_vertices()));
232 CompareS2LoopToShape(*loop, make_unique<S2LaxPolygonShape>(loops));
233 }
234 }
235