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