1 // Copyright 2016 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/s2polyline_simplifier.h"
19 
20 #include <cfloat>
21 #include <vector>
22 
23 #include <gtest/gtest.h>
24 #include "s2/s1angle.h"
25 #include "s2/s1chord_angle.h"
26 #include "s2/s2edge_distances.h"
27 #include "s2/s2pointutil.h"
28 #include "s2/s2testing.h"
29 #include "s2/s2text_format.h"
30 
CheckSimplify(const char * src,const char * dst,const char * target,const char * avoid,const std::vector<bool> & disc_on_left,double radius_degrees,bool expected_result)31 void CheckSimplify(const char* src, const char* dst,
32                    const char* target, const char* avoid,
33                    const std::vector<bool>& disc_on_left,
34                    double radius_degrees, bool expected_result) {
35   S1ChordAngle radius(S1Angle::Degrees(radius_degrees));
36   S2PolylineSimplifier s;
37   s.Init(s2textformat::MakePoint(src));
38   for (const S2Point& p : s2textformat::ParsePoints(target)) {
39     s.TargetDisc(p, radius);
40   }
41   int i = 0;
42   for (const S2Point& p : s2textformat::ParsePoints(avoid)) {
43     s.AvoidDisc(p, radius, disc_on_left[i++]);
44   }
45   EXPECT_EQ(expected_result, s.Extend(s2textformat::MakePoint(dst)))
46       << "\nsrc = " << src << "\ndst = " << dst
47       << "\ntarget = " << target << "\navoid = " << avoid;
48 }
49 
TEST(S2PolylineSimplifier,Reuse)50 TEST(S2PolylineSimplifier, Reuse) {
51   // Check that Init() can be called more than once.
52   S2PolylineSimplifier s;
53   S1ChordAngle radius(S1Angle::Degrees(10));
54   s.Init(S2Point(1, 0, 0));
55   EXPECT_TRUE(s.TargetDisc(S2Point(1, 1, 0).Normalize(), radius));
56   EXPECT_TRUE(s.TargetDisc(S2Point(1, 1, 0.1).Normalize(), radius));
57   EXPECT_FALSE(s.Extend(S2Point(1, 1, 0.4).Normalize()));
58 
59   // s.Init(S2Point(0, 1, 0));
60   EXPECT_TRUE(s.TargetDisc(S2Point(1, 1, 0.3).Normalize(), radius));
61   EXPECT_TRUE(s.TargetDisc(S2Point(1, 1, 0.2).Normalize(), radius));
62   EXPECT_FALSE(s.Extend(S2Point(1, 1, 0).Normalize()));
63 }
64 
TEST(S2PolylineSimplifier,NoConstraints)65 TEST(S2PolylineSimplifier, NoConstraints) {
66   // No constraints, dst == src.
67   CheckSimplify("0:1", "0:1", "", "", {}, 0, true);
68 
69   // No constraints, dst != src.
70   CheckSimplify("0:1", "1:0", "", "", {}, 0, true);
71 
72   // No constraints, (src, dst) longer than 90 degrees (not supported).
73   CheckSimplify("0:0", "0:91", "", "", {}, 0, false);
74 }
75 
TEST(S2PolylineSimplifier,TargetOnePoint)76 TEST(S2PolylineSimplifier, TargetOnePoint) {
77   // Three points on a straight line.  In theory zero tolerance should work,
78   // but in practice there are floating point errors.
79   CheckSimplify("0:0", "0:2", "0:1", "", {}, 1e-10, true);
80 
81   // Three points where the middle point is too far away.
82   CheckSimplify("0:0", "0:2", "1:1", "", {}, 0.9, false);
83 
84   // A target disc that contains the source vertex.
85   CheckSimplify("0:0", "0:2", "0:0.1", "", {}, 1.0, true);
86 
87   // A target disc that contains the destination vertex.
88   CheckSimplify("0:0", "0:2", "0:2.1", "", {}, 1.0, true);
89 }
90 
TEST(S2PolylineSimplifier,AvoidOnePoint)91 TEST(S2PolylineSimplifier, AvoidOnePoint) {
92   // Three points on a straight line, attempting to avoid the middle point.
93   CheckSimplify("0:0", "0:2", "", "0:1", {true}, 1e-10, false);
94 
95   // Three points where the middle point can be successfully avoided.
96   CheckSimplify("0:0", "0:2", "", "1:1", {true}, 0.9, true);
97 
98   // Three points where the middle point is on the left, but where the client
99   // requires the point to be on the right of the edge.
100   CheckSimplify("0:0", "0:2", "", "1:1", {false}, 1e-10, false);
101 }
102 
TEST(S2PolylineSimplifier,TargetAndAvoid)103 TEST(S2PolylineSimplifier, TargetAndAvoid) {
104   // Target several points that are separated from the proposed edge by about
105   // 0.7 degrees, and avoid several points that are separated from the
106   // proposed edge by about 1.4 degrees.
107   CheckSimplify("0:0", "10:10", "2:3, 4:3, 7:8",
108                 "4:2, 7:5, 7:9", {true, true, false}, 1.0, true);
109 
110   // The same example, but one point to be targeted is 1.4 degrees away.
111   CheckSimplify("0:0", "10:10", "2:3, 4:6, 7:8",
112                 "4:2, 7:5, 7:9", {true, true, false}, 1.0, false);
113 
114   // The same example, but one point to be avoided is 0.7 degrees away.
115   CheckSimplify("0:0", "10:10", "2:3, 4:3, 7:8",
116                 "4:2, 6:5, 7:9", {true, true, false}, 1.0, false);
117 }
118 
TEST(S2PolylineSimplifier,Precision)119 TEST(S2PolylineSimplifier, Precision) {
120   // This is a rough upper bound on both the error in constructing the disc
121   // locations (i.e., S2::InterpolateAtDistance, etc), and also on the
122   // padding that S2PolylineSimplifier uses to ensure that its results are
123   // conservative (i.e., the error calculated by GetSemiwidth).
124   const S1Angle kMaxError = S1Angle::Radians(25 * DBL_EPSILON);
125 
126   // We repeatedly generate a random edge.  We then target several discs that
127   // barely overlap the edge, and avoid several discs that barely miss the
128   // edge.  About half the time, we choose one disc and make it slightly too
129   // large or too small so that targeting fails.
130   const int kIters = 1000;  // Passes with 1 million iterations.
131   S2PolylineSimplifier simplifier;
132   for (int iter = 0; iter < kIters; ++iter) {
133     S2Testing::rnd.Reset(iter + 1);  // Easier to reproduce a specific case.
134     S2Point src = S2Testing::RandomPoint();
135     simplifier.Init(src);
136     S2Point dst = S2::InterpolateAtDistance(
137         S1Angle::Radians(S2Testing::rnd.RandDouble()),
138         src, S2Testing::RandomPoint());
139     S2Point n = S2::RobustCrossProd(src, dst).Normalize();
140 
141     // If bad_disc >= 0, then we make targeting fail for that disc.
142     const int kNumDiscs = 5;
143     int bad_disc = S2Testing::rnd.Uniform(2 * kNumDiscs) - kNumDiscs;
144     for (int i = 0; i < kNumDiscs; ++i) {
145       double f = S2Testing::rnd.RandDouble();
146       S2Point a = ((1 - f) * src + f * dst).Normalize();
147       S1Angle r = S1Angle::Radians(S2Testing::rnd.RandDouble());
148       bool on_left = S2Testing::rnd.OneIn(2);
149       S2Point x = S2::InterpolateAtDistance(r, a, on_left ? n : -n);
150       // We grow the radius slightly if we want to target the disc and shrink
151       // it otherwise, *unless* we want targeting to fail for this disc, in
152       // which case these actions are reversed.
153       bool avoid = S2Testing::rnd.OneIn(2);
154       bool grow_radius = (avoid == (i == bad_disc));
155       S1ChordAngle radius(grow_radius ? r + kMaxError : r - kMaxError);
156       if (avoid) {
157         simplifier.AvoidDisc(x, radius, on_left);
158       } else {
159         simplifier.TargetDisc(x, radius);
160       }
161     }
162     // The result is true iff all the disc constraints were satisfiable.
163     EXPECT_EQ(bad_disc < 0, simplifier.Extend(dst));
164   }
165 }
166