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