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/s2shapeutil_get_reference_point.h"
19
20 #include <vector>
21
22 #include <gtest/gtest.h>
23 #include "s2/s2lax_polygon_shape.h"
24 #include "s2/s2polygon.h"
25 #include "s2/s2shapeutil_contains_brute_force.h"
26 #include "s2/s2testing.h"
27 #include "s2/s2text_format.h"
28
29 using std::vector;
30
31 namespace s2shapeutil {
32
TEST(GetReferencePoint,EmptyPolygon)33 TEST(GetReferencePoint, EmptyPolygon) {
34 S2LaxPolygonShape shape((S2Polygon()));
35 EXPECT_FALSE(shape.GetReferencePoint().contained);
36 }
37
TEST(GetReferencePoint,FullPolygon)38 TEST(GetReferencePoint, FullPolygon) {
39 S2LaxPolygonShape shape(S2Polygon(s2textformat::MakeLoopOrDie("full")));
40 EXPECT_TRUE(shape.GetReferencePoint().contained);
41 }
42
TEST(GetReferencePoint,DegenerateLoops)43 TEST(GetReferencePoint, DegenerateLoops) {
44 vector<S2LaxPolygonShape::Loop> loops = {
45 s2textformat::ParsePoints("1:1, 1:2, 2:2, 1:2, 1:3, 1:2, 1:1"),
46 s2textformat::ParsePoints("0:0, 0:3, 0:6, 0:9, 0:6, 0:3, 0:0"),
47 s2textformat::ParsePoints("5:5, 6:6")
48 };
49 S2LaxPolygonShape shape(loops);
50 EXPECT_FALSE(shape.GetReferencePoint().contained);
51 }
52
TEST(GetReferencePoint,InvertedLoops)53 TEST(GetReferencePoint, InvertedLoops) {
54 vector<S2LaxPolygonShape::Loop> loops = {
55 s2textformat::ParsePoints("1:2, 1:1, 2:2"),
56 s2textformat::ParsePoints("3:4, 3:3, 4:4")
57 };
58 S2LaxPolygonShape shape(loops);
59 EXPECT_TRUE(s2shapeutil::ContainsBruteForce(shape, S2::Origin()));
60 }
61
TEST(GetReferencePoint,PartiallyDegenerateLoops)62 TEST(GetReferencePoint, PartiallyDegenerateLoops) {
63 for (int iter = 0; iter < 100; ++iter) {
64 // First we construct a long convoluted edge chain that follows the
65 // S2CellId Hilbert curve. At some random point along the curve, we
66 // insert a small triangular loop.
67 vector<S2LaxPolygonShape::Loop> loops(1);
68 S2LaxPolygonShape::Loop* loop = &loops[0];
69 const int num_vertices = 100;
70 S2CellId start = S2Testing::GetRandomCellId(S2CellId::kMaxLevel - 1);
71 S2CellId end = start.advance_wrap(num_vertices);
72 S2CellId loop_cellid = start.advance_wrap(
73 S2Testing::rnd.Uniform(num_vertices - 2) + 1);
74 vector<S2Point> triangle;
75 for (S2CellId cellid = start; cellid != end; cellid = cellid.next_wrap()) {
76 if (cellid == loop_cellid) {
77 // Insert a small triangular loop. We save the loop so that we can
78 // test whether it contains the origin later.
79 triangle.push_back(cellid.child(0).ToPoint());
80 triangle.push_back(cellid.child(1).ToPoint());
81 triangle.push_back(cellid.child(2).ToPoint());
82 loop->insert(loop->end(), triangle.begin(), triangle.end());
83 loop->push_back(cellid.child(0).ToPoint());
84 } else {
85 loop->push_back(cellid.ToPoint());
86 }
87 }
88 // Now we retrace our steps, except that we skip the three edges that form
89 // the triangular loop above.
90 for (S2CellId cellid = end; cellid != start; cellid = cellid.prev_wrap()) {
91 if (cellid == loop_cellid) {
92 loop->push_back(cellid.child(0).ToPoint());
93 } else {
94 loop->push_back(cellid.ToPoint());
95 }
96 }
97 S2LaxPolygonShape shape(loops);
98 S2Loop triangle_loop(triangle);
99 auto ref = shape.GetReferencePoint();
100 EXPECT_EQ(triangle_loop.Contains(ref.point), ref.contained);
101 }
102 }
103
104 } // namespace s2shapeutil
105