1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2TESTING_H__
4#define UTIL_GEOMETRY_S2TESTING_H__
5
6#include <string>
7using std::string;
8
9#include <vector>
10using std::vector;
11
12#include "s2.h"
13#include "s2cellid.h"
14
15class S2LatLngRect;
16class S2Loop;
17class S2Polygon;
18class S2Polyline;
19class S2Region;
20class S2CellUnion;
21class S2Cap;
22
23// This class defines various static functions that are useful for writing
24// unit tests.
25class S2Testing {
26 public:
27 class Random;
28
29 // Given a latitude-longitude coordinate in degrees,
30 // return a newly allocated point. Example of the input format:
31 // "-20:150"
32 static S2Point MakePoint(string const& str);
33
34 // Given a string of one or more latitude-longitude coordinates in degrees,
35 // return the minimal bounding S2LatLngRect that contains the coordinates.
36 // Example of the input format:
37 // "-20:150" // one point
38 // "-20:150, -20:151, -19:150" // three points
39 static S2LatLngRect MakeLatLngRect(string const& str);
40
41 // Given a string of latitude-longitude coordinates in degrees,
42 // return a newly allocated loop. Example of the input format:
43 // "-20:150, 10:-120, 0.123:-170.652"
44 static S2Loop* MakeLoop(string const& str);
45
46 // Similar to MakeLoop(), but returns an S2Polyline rather than an S2Loop.
47 static S2Polyline* MakePolyline(string const& str);
48
49 // Given a sequence of loops separated by semicolons, return a newly
50 // allocated polygon. Loops are automatically inverted if necessary so
51 // that they enclose at most half of the unit sphere.
52 static S2Polygon* MakePolygon(string const& str);
53
54
55 // Returns a newly allocated loop (owned by caller) shaped as a
56 // regular polygon with num_vertices vertices, all on a circle of
57 // radius radius_angle around the center. The radius is the actual
58 // distance from the center to the circle along the sphere.
59 static S2Loop* MakeRegularLoop(S2Point const& center,
60 int num_vertices,
61 double radius_angle);
62
63 // Examples of the input format:
64 // "10:20, 90:0, 20:30" // one loop
65 // "10:20, 90:0, 20:30; 5.5:6.5, -90:-180, -15.2:20.3" // two loops
66
67 // Parse a string in the same format as MakeLatLngRect, and return the
68 // corresponding vector of S2LatLng points.
69 static void ParseLatLngs(string const& str, vector<S2LatLng>* latlngs);
70
71 // Parse a string in the same format as MakeLatLngRect, and return the
72 // corresponding vector of S2Point values.
73 static void ParsePoints(string const& str, vector<S2Point>* vertices);
74
75 // Convert a point, lat-lng rect, loop, polyline, or polygon to the string
76 // format above.
77 static string ToString(S2Point const& point);
78 static string ToString(S2LatLngRect const& rect);
79 static string ToString(S2Loop const* loop);
80 static string ToString(S2Polyline const* polyline);
81 static string ToString(S2Polygon const* polygon);
82
83 // A deterministically-seeded random number generator.
84 static Random rnd;
85
86 // Return a random unit-length vector.
87 static S2Point RandomPoint();
88
89 // Return a right-handed coordinate frame (three orthonormal vectors).
90 static void GetRandomFrame(S2Point* x, S2Point* y, S2Point* z);
91
92 // Return a cap with a random axis such that the log of its area is
93 // uniformly distributed between the logs of the two given values.
94 // (The log of the cap angle is also approximately uniformly distributed.)
95 static S2Cap GetRandomCap(double min_area, double max_area);
96
97 // Return a point chosen uniformly at random (with respect to area)
98 // from the given cap.
99 static S2Point SamplePoint(S2Cap const& cap);
100
101 // Return a random cell id at the given level or at a randomly chosen
102 // level. The distribution is uniform over the space of cell ids,
103 // but only approximately uniform over the surface of the sphere.
104 static S2CellId GetRandomCellId(int level);
105 static S2CellId GetRandomCellId();
106
107 // Checks that "covering" completely covers the given region. If
108 // "check_tight" is true, also checks that it does not contain any cells
109 // that do not intersect the given region. ("id" is only used internally.)
110 static void CheckCovering(S2Region const& region,
111 S2CellUnion const& covering,
112 bool check_tight,
113 S2CellId const& id = S2CellId());
114
115 // Returns the user time consumed by this process, in seconds.
116 static double GetCpuTime();
117};
118
119// Functions in this class return random numbers that are as good as
120// rand() is. The results will be reproducible as the seed is
121// deterministic.
122class S2Testing::Random {
123 public:
124 Random();
125 uint64 Rand64();
126 uint32 Rand32();
127 double RandDouble();
128 int32 Uniform(int32 upper_bound);
129 int32 operator() (int32 n) {
130 return Uniform(n);
131 }
132 bool OneIn(int x);
133
134 // Skewed: pick "base" uniformly from range [0,max_log] and then
135 // return "base" random bits. The effect is to pick a number in the
136 // range [0,2^max_log-1] with bias towards smaller numbers.
137 int32 Skewed(int max_log);
138
139 // PlusOrMinus: return a uniformly distributed value in the range
140 // [value - (value * multiplier), value + (value * multiplier) )
141 // (i.e. inclusive on the lower end and exclusive on the upper end).
142 //
143 // Be careful of floating point rounding, e.g., 1.0/29 is inexactly
144 // represented, and so we get:
145 //
146 // PlusOrMinus(2 * 29, 1.0/29) is
147 // PlusOrMinus(58, 0.0344827849223) which gives
148 // range = static_cast<int32>(1.999999992549) = 1, rand_val \in [0, 2)
149 // and return result \in [57, 59) rather than [56, 60) as probably
150 // intended. (This holds for IEEE754 floating point.)
151 int32 PlusOrMinus(int32 value, float multiplier);
152};
153
154#endif // UTIL_GEOMETRY_S2TESTING_H__
155