1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#include <stdlib.h>
4#include <sys/resource.h> // for rusage, RUSAGE_SELF
5#include <limits.h>
6
7#include <vector>
8using std::vector;
9
10
11#include "base/integral_types.h"
12#include "base/logging.h"
13#include "base/stringprintf.h"
14#include "util/math/matrix3x3-inl.h"
15#include "s2testing.h"
16#include "s2loop.h"
17#include "s2latlng.h"
18#include "s2latlngrect.h"
19#include "s2polygon.h"
20#include "s2polyline.h"
21#include "s2cellunion.h"
22#include "s2cell.h"
23#include "s2cap.h"
24#include "strings/split.h"
25#include "strings/strutil.h"
26
27S2Testing::Random::Random() {
28 srandom(4);
29}
30
31uint64 S2Testing::Random::Rand64() {
32 int bits_of_rand = log2(1ULL + RAND_MAX);
33 uint64 result = 0;
34 for (int num_bits = 0; num_bits < 8 * sizeof(uint64);
35 num_bits += bits_of_rand) {
36 result <<= bits_of_rand;
37 result += random();
38 }
39 return result;
40}
41
42uint32 S2Testing::Random::Rand32() {
43 return Rand64() & ((1ULL << 32) - 1);
44}
45
46double S2Testing::Random::RandDouble() {
47 const int NUMBITS = 53;
48 return ldexp(Rand64() & ((1ULL << NUMBITS) - 1ULL), -NUMBITS);
49}
50
51int S2Testing::Random::Uniform(int upper_bound) {
52 return static_cast<uint32>(RandDouble() * upper_bound);
53}
54
55bool S2Testing::Random::OneIn(int x) {
56 return Uniform(x) == 0;
57}
58
59int32 S2Testing::Random::Skewed(int max_log) {
60 const int32 base = Rand32() % (max_log + 1);
61 return Rand32() & ((1u << base) - 1);
62}
63
64int32 S2Testing::Random::PlusOrMinus(int32 value, float multiplier) {
65 const int32 range = static_cast<int32>(value * multiplier);
66 const int32 rand_val = Uniform(range * 2);
67 return value - range + rand_val;
68}
69
70S2Testing::Random S2Testing::rnd;
71
72static double ParseDouble(const string& str) {
73 char* end_ptr = NULL;
74 double value = strtod(str.c_str(), &end_ptr);
75 CHECK(end_ptr && *end_ptr == 0) << ": str == \"" << str << "\"";
76 return value;
77}
78
79void S2Testing::ParseLatLngs(string const& str, vector<S2LatLng>* latlngs) {
80 vector<pair<string, string> > p;
81 CHECK(DictionaryParse(str, &p)) << ": str == \"" << str << "\"";
82 latlngs->clear();
83 for (int i = 0; i < p.size(); ++i) {
84 latlngs->push_back(S2LatLng::FromDegrees(ParseDouble(p[i].first),
85 ParseDouble(p[i].second)));
86 }
87}
88
89void S2Testing::ParsePoints(string const& str, vector<S2Point>* vertices) {
90 vector<S2LatLng> latlngs;
91 S2Testing::ParseLatLngs(str, &latlngs);
92 vertices->clear();
93 for (int i = 0; i < latlngs.size(); ++i) {
94 vertices->push_back(latlngs[i].ToPoint());
95 }
96}
97
98S2Point S2Testing::MakePoint(string const& str) {
99 vector<S2Point> vertices;
100 ParsePoints(str, &vertices);
101 CHECK_EQ(vertices.size(), 1);
102 return vertices[0];
103}
104
105S2LatLngRect S2Testing::MakeLatLngRect(string const& str) {
106 vector<S2LatLng> latlngs;
107 ParseLatLngs(str, &latlngs);
108 CHECK_GT(latlngs.size(), 0);
109 S2LatLngRect rect = S2LatLngRect::FromPoint(latlngs[0]);
110 for (int i = 1; i < latlngs.size(); ++i) {
111 rect.AddPoint(latlngs[i]);
112 }
113 return rect;
114}
115
116S2Loop* S2Testing::MakeLoop(string const& str) {
117 vector<S2Point> vertices;
118 ParsePoints(str, &vertices);
119 return new S2Loop(vertices);
120}
121
122S2Polyline* S2Testing::MakePolyline(string const& str) {
123 vector<S2Point> vertices;
124 ParsePoints(str, &vertices);
125 return new S2Polyline(vertices);
126}
127
128S2Polygon* S2Testing::MakePolygon(string const& str) {
129 vector<string> loop_strs;
130 SplitStringUsing(str, ";", &loop_strs);
131 vector<S2Loop*> loops;
132 for (int i = 0; i < loop_strs.size(); ++i) {
133 S2Loop* loop = MakeLoop(loop_strs[i]);
134 loop->Normalize();
135 loops.push_back(loop);
136 }
137 return new S2Polygon(&loops); // Takes ownership.
138}
139
140
141S2Loop* S2Testing::MakeRegularLoop(S2Point const& center,
142 int num_vertices,
143 double angle_radius) {
144 Matrix3x3_d m;
145 S2::GetFrame(center, &m);
146 vector<S2Point> vertices;
147 double radian_step = 2 * M_PI / num_vertices;
148 // We create the vertices on the plane tangent to center, so the
149 // radius on that plane is larger.
150 double planar_radius = tan(angle_radius);
151 for (int vi = 0; vi < num_vertices; ++vi) {
152 double angle = vi * radian_step;
153 S2Point p(planar_radius * cos(angle), planar_radius * sin(angle), 1);
154 vertices.push_back(S2::FromFrame(m, p.Normalize()));
155 }
156 return new S2Loop(vertices);
157}
158
159static void AppendVertex(S2Point const& p, string* out) {
160 S2LatLng ll(p);
161 StringAppendF(out, "%.17g:%.17g", ll.lat().degrees(), ll.lng().degrees());
162}
163
164static void AppendVertices(S2Point const* v, int n, string* out) {
165 for (int i = 0; i < n; ++i) {
166 if (i > 0) *out += ", ";
167 AppendVertex(v[i], out);
168 }
169}
170
171string S2Testing::ToString(S2Point const& point) {
172 string out;
173 AppendVertex(point, &out);
174 return out;
175}
176
177string S2Testing::ToString(S2LatLngRect const& rect) {
178 string out;
179 AppendVertex(rect.lo().ToPoint(), &out);
180 out += ", ";
181 AppendVertex(rect.hi().ToPoint(), &out);
182 return out;
183}
184
185string S2Testing::ToString(S2Loop const* loop) {
186 string out;
187 AppendVertices(&loop->vertex(0), loop->num_vertices(), &out);
188 return out;
189}
190
191string S2Testing::ToString(S2Polyline const* polyline) {
192 string out;
193 AppendVertices(&polyline->vertex(0), polyline->num_vertices(), &out);
194 return out;
195}
196
197string S2Testing::ToString(S2Polygon const* polygon) {
198 string out;
199 for (int i = 0; i < polygon->num_loops(); ++i) {
200 if (i > 0) out += ";\n";
201 S2Loop* loop = polygon->loop(i);
202 AppendVertices(&loop->vertex(0), loop->num_vertices(), &out);
203 }
204 return out;
205}
206
207void DumpLoop(S2Loop const* loop) {
208 // Only for calling from a debugger.
209 cout << S2Testing::ToString(loop) << "\n";
210}
211
212void DumpPolyline(S2Polyline const* polyline) {
213 // Only for calling from a debugger.
214 cout << S2Testing::ToString(polyline) << "\n";
215}
216
217void DumpPolygon(S2Polygon const* polygon) {
218 // Only for calling from a debugger.
219 cout << S2Testing::ToString(polygon) << "\n";
220}
221
222S2Point S2Testing::RandomPoint() {
223 // The order of evaluation of function arguments is unspecified,
224 // so we may not just call S2Point with three RandDouble-based args.
225 // Use temporaries to induce sequence points between calls.
226 double x = 2 * rnd.RandDouble() - 1;
227 double y = 2 * rnd.RandDouble() - 1;
228 double z = 2 * rnd.RandDouble() - 1;
229 return S2Point(x, y, z).Normalize();
230}
231
232void S2Testing::GetRandomFrame(S2Point* x, S2Point* y, S2Point* z) {
233 *x = RandomPoint();
234 *y = x->CrossProd(RandomPoint()).Normalize();
235 *z = x->CrossProd(*y).Normalize();
236}
237
238S2CellId S2Testing::GetRandomCellId(int level) {
239 int face = rnd.Uniform(S2CellId::kNumFaces);
240 uint64 pos = rnd.Rand64() & ((1ULL << (2 * S2CellId::kMaxLevel)) - 1);
241 return S2CellId::FromFacePosLevel(face, pos, level);
242}
243
244S2CellId S2Testing::GetRandomCellId() {
245 return GetRandomCellId(rnd.Uniform(S2CellId::kMaxLevel + 1));
246}
247
248S2Cap S2Testing::GetRandomCap(double min_area, double max_area) {
249 double cap_area = max_area * pow(min_area / max_area, rnd.RandDouble());
250 DCHECK_GE(cap_area, min_area);
251 DCHECK_LE(cap_area, max_area);
252
253 // The surface area of a cap is 2*Pi times its height.
254 return S2Cap::FromAxisArea(RandomPoint(), cap_area);
255}
256
257S2Point S2Testing::SamplePoint(S2Cap const& cap) {
258 // We consider the cap axis to be the "z" axis. We choose two other axes to
259 // complete the coordinate frame.
260
261 Matrix3x3_d m;
262 S2::GetFrame(cap.axis(), &m);
263
264 // The surface area of a spherical cap is directly proportional to its
265 // height. First we choose a random height, and then we choose a random
266 // point along the circle at that height.
267
268 double h = rnd.RandDouble() * cap.height();
269 double theta = 2 * M_PI * rnd.RandDouble();
270 double r = sqrt(h * (2 - h)); // Radius of circle.
271
272 // The result should already be very close to unit-length, but we might as
273 // well make it accurate as possible.
274 return S2::FromFrame(m, S2Point(cos(theta) * r, sin(theta) * r, 1 - h))
275 .Normalize();
276}
277
278void S2Testing::CheckCovering(S2Region const& region,
279 S2CellUnion const& covering,
280 bool check_tight,
281 S2CellId const& id) {
282 if (!id.is_valid()) {
283 for (int face = 0; face < 6; ++face) {
284 CheckCovering(region, covering, check_tight,
285 S2CellId::FromFacePosLevel(face, 0, 0));
286 }
287 return;
288 }
289
290 if (!region.MayIntersect(S2Cell(id))) {
291 // If region does not intersect id, then neither should the covering.
292 if (check_tight) CHECK(!covering.Intersects(id));
293
294 } else if (!covering.Contains(id)) {
295 // The region may intersect id, but we can't assert that the covering
296 // intersects id because we may discover that the region does not actually
297 // intersect upon further subdivision. (MayIntersect is not exact.)
298 CHECK(!region.Contains(S2Cell(id)));
299 CHECK(!id.is_leaf());
300 S2CellId end = id.child_end();
301 S2CellId child;
302 for (child = id.child_begin(); child != end; child = child.next()) {
303 CheckCovering(region, covering, check_tight, child);
304 }
305 }
306}
307
308double S2Testing::GetCpuTime() {
309 struct rusage ru;
310 CHECK_EQ(getrusage(RUSAGE_SELF, &ru), 0);
311 return ru.ru_utime.tv_sec + ru.ru_utime.tv_usec / 1e6;
312}
313