← Back to branch summary

~evarlast/ubuntu/utopic/mongodb/upstart-workaround-debian-bug-718702

« back to all changes in this revision

Viewing changes to src/third_party/s2/s2edgeindex_test.cc

  • Committer: Package Import Robot
  • Author(s): James Page, James Page, Robie Basak
  • Date: 2013-05-29 17:44:42 UTC
  • mfrom: (44.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20130529174442-z0a4qmoww4y0t458
Tags: 1:2.4.3-1ubuntu1
[ James Page ]
* Merge from Debian unstable, remaining changes:
  - Enable SSL support:
    + d/control: Add libssl-dev to BD's.
    + d/rules: Enabled --ssl option.
    + d/mongodb.conf: Add example SSL configuration options.
  - d/mongodb-server.mongodb.upstart: Add upstart configuration.
  - d/rules: Don't strip binaries during scons build for Ubuntu.
  - d/control: Add armhf to target archs.
  - d/p/SConscript.client.patch: fixup install of client libraries.
  - d/p/0010-install-libs-to-usr-lib-not-usr-lib64-Closes-588557.patch:
    Install libraries to lib not lib64.
* Dropped changes:
  - d/p/arm-support.patch: Included in Debian.
  - d/p/double-alignment.patch: Included in Debian.
  - d/rules,control: Debian also builds with avaliable system libraries
    now.
* Fix FTBFS due to gcc and boost upgrades in saucy:
  - d/p/0008-ignore-unused-local-typedefs.patch: Add -Wno-unused-typedefs
    to unbreak building with g++-4.8.
  - d/p/0009-boost-1.53.patch: Fixup signed/unsigned casting issue.

[ Robie Basak ]
* d/p/0011-Use-a-signed-char-to-store-BSONType-enumerations.patch: Fixup
  build failure on ARM due to missing signed'ness of char cast.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/third_party/s2/s2edgeindex_test.cc
 
1
// Copyright 2009 Google Inc. All Rights Reserved.
 
2
 
 
3
#include "s2edgeindex.h"
 
4
 
 
5
#include <set>
 
6
using std::set;
 
7
using std::multiset;
 
8
 
 
9
#include <string>
 
10
using std::string;
 
11
 
 
12
#include <vector>
 
13
using std::vector;
 
14
 
 
15
 
 
16
#include "base/commandlineflags.h"
 
17
#include "base/stringprintf.h"
 
18
#include "base/logging.h"
 
19
#include "testing/base/public/benchmark.h"
 
20
#include "testing/base/public/gunit.h"
 
21
#include "s2cap.h"
 
22
#include "s2cell.h"
 
23
#include "s2cellid.h"
 
24
#include "s2edgeutil.h"
 
25
#include "s2loop.h"
 
26
#include "s2testing.h"
 
27
#include "util/math/vector3-inl.h"
 
28
#include "util/math/matrix3x3-inl.h"
 
29
 
 
30
DECLARE_bool(always_recurse_on_children);
 
31
 
 
32
typedef pair<S2Point, S2Point> S2Edge;
 
33
 
 
34
static const double kEarthRadiusMeters = 6371000;
 
35
 
 
36
 
 
37
 
 
38
// Generates a random edge whose center is in the given cap.
 
39
static S2Edge RandomEdgeCrossingCap(double max_length_meters,
 
40
                                    const S2Cap& cap) {
 
41
  // Pick the edge center at random.
 
42
  S2Point edge_center = S2Testing::SamplePoint(cap);
 
43
  // Pick two random points in a suitably sized cap about the edge center.
 
44
  S2Cap edge_cap = S2Cap::FromAxisAngle(
 
45
      edge_center,
 
46
      S1Angle::Radians(max_length_meters / kEarthRadiusMeters / 2));
 
47
  S2Point p1 = S2Testing::SamplePoint(edge_cap);
 
48
  S2Point p2 = S2Testing::SamplePoint(edge_cap);
 
49
  return S2Edge(p1, p2);
 
50
}
 
51
 
 
52
// Generates "num_edges" random edges, of length at most
 
53
// "edge_length_meters_max" and each of whose center is in a randomly located
 
54
// cap with radius "cap_span_meters", and puts results into "edges".
 
55
static void GenerateRandomEarthEdges(double edge_length_meters_max,
 
56
                                     double cap_span_meters,
 
57
                                     int num_edges,
 
58
                                     vector<S2Edge>* edges) {
 
59
  S2Cap cap = S2Cap::FromAxisAngle(
 
60
      S2Testing::RandomPoint(),
 
61
      S1Angle::Radians(cap_span_meters / kEarthRadiusMeters));
 
62
  for (int i = 0; i < num_edges; ++i) {
 
63
    edges->push_back(RandomEdgeCrossingCap(edge_length_meters_max, cap));
 
64
  }
 
65
}
 
66
 
 
67
static string ToString(const S2Edge& e1, const S2Edge& e2) {
 
68
  double u1, v1, u2, v2, u3, v3, u4, v4;
 
69
  S2::XYZtoFaceUV(e1.first, &u1, &v1);
 
70
  S2::XYZtoFaceUV(e1.second, &u2, &v2);
 
71
  S2::XYZtoFaceUV(e2.first, &u3, &v3);
 
72
  S2::XYZtoFaceUV(e2.second, &u4, &v4);
 
73
  u2 = u2 - u1;
 
74
  u3 = u3 - u1;
 
75
  u4 = u4 - u1;
 
76
  v2 = v2 - v1;
 
77
  v3 = v3 - v1;
 
78
  v4 = v4 - v1;
 
79
  return StringPrintf("[%6.2f,%6.2f] 0,0 -> %3.3e,%3.3e) --"
 
80
                      " (%3.3e,%3.3e -> %3.3e %3.3e)",
 
81
                      u1, v1, u2, v2, u3, v3, u4, v4);
 
82
}
 
83
 
 
84
class EdgeVectorIndex: public S2EdgeIndex {
 
85
 public:
 
86
  explicit EdgeVectorIndex(vector<S2Edge> const* edges):
 
87
      edges_(edges) {}
 
88
 
 
89
  virtual int num_edges() const { return edges_->size(); }
 
90
  virtual S2Point const* edge_from(int index) const {
 
91
    return &((*edges_)[index].first);
 
92
  }
 
93
  virtual S2Point const* edge_to(int index) const {
 
94
    return &((*edges_)[index].second);
 
95
  }
 
96
 private:
 
97
  vector<S2Edge> const* edges_;
 
98
};
 
99
 
 
100
static void TestAllCrossings(vector<S2Edge> const& all_edges,
 
101
                             int min_crossings,
 
102
                             int max_checks_crossings_ratio) {
 
103
  EdgeVectorIndex index(&all_edges);
 
104
  index.ComputeIndex();
 
105
  EdgeVectorIndex::Iterator it(&index);
 
106
  double total_crossings = 0;
 
107
  double total_index_checks = 0;
 
108
 
 
109
  VLOG(1) << "start detailed checking\n";
 
110
  for (int in = 0; in < all_edges.size(); ++in) {
 
111
    S2Edge e = all_edges[in];
 
112
 
 
113
    set<int> candidate_set;
 
114
 
 
115
    for (it.GetCandidates(e.first, e.second); !it.Done(); it.Next()) {
 
116
      candidate_set.insert(it.Index());
 
117
      total_index_checks++;
 
118
    }
 
119
 
 
120
    for (int i = 0; i < all_edges.size(); ++i) {
 
121
      int crossing = S2EdgeUtil::RobustCrossing(e.first, e.second,
 
122
                                                all_edges[i].first,
 
123
                                                all_edges[i].second);
 
124
      if (crossing  >= 0) {
 
125
        EXPECT_EQ(1, candidate_set.count(i))
 
126
            << "Edge " << i <<  " is not a candidate of edge " << in
 
127
            << " (" << ToString(all_edges[i], e) << ")";
 
128
        ++total_crossings;
 
129
      }
 
130
    }
 
131
  }
 
132
 
 
133
  VLOG(1) << "Pairs/num crossings/check crossing ratio: "
 
134
          << all_edges.size() * all_edges.size() << "/"
 
135
          << total_crossings << "/"
 
136
          << total_index_checks / total_crossings;
 
137
  EXPECT_LE(min_crossings, total_crossings);
 
138
  EXPECT_GE(total_crossings * max_checks_crossings_ratio, total_index_checks);
 
139
}
 
140
 
 
141
 
 
142
// Generates random edges and tests, for each edge,
 
143
// that all those that cross are candidates.
 
144
static void TestCrossingsRandomInCap(int num_edges,
 
145
                                     double edge_length_max,
 
146
                                     double cap_span_meters,
 
147
                                     int min_crossings,
 
148
                                     int max_checks_crossings_ratio) {
 
149
  vector<S2Edge> all_edges;
 
150
  GenerateRandomEarthEdges(edge_length_max, cap_span_meters, num_edges,
 
151
                           &all_edges);
 
152
  TestAllCrossings(all_edges, min_crossings, max_checks_crossings_ratio);
 
153
}
 
154
 
 
155
 
 
156
TEST(S2EdgeIndex, LoopCandidateOfItself) {
 
157
  vector<S2Point> ps;  // A diamond loop around 0,180.
 
158
  ps.push_back(S2Testing::MakePoint("0:178"));
 
159
  ps.push_back(S2Testing::MakePoint("-1:180"));
 
160
  ps.push_back(S2Testing::MakePoint("0:-179"));
 
161
  ps.push_back(S2Testing::MakePoint("1:-180"));
 
162
  vector<S2Edge> all_edges;
 
163
  for (int i = 0; i < 4; ++i) {
 
164
    all_edges.push_back(make_pair(ps[i], ps[(i+1)%4]));
 
165
  }
 
166
  TestAllCrossings(all_edges, 0, 16);
 
167
}
 
168
 
 
169
TEST(S2EdgeIndex, RandomEdgeCrossings) {
 
170
  TestCrossingsRandomInCap(2000, 30, 5000, 500, 2);
 
171
  TestCrossingsRandomInCap(1000, 100, 5000, 500, 3);
 
172
  TestCrossingsRandomInCap(1000, 1000, 5000, 1000, 40);
 
173
  TestCrossingsRandomInCap(500, 5000, 5000, 5000, 20);
 
174
}
 
175
 
 
176
TEST(S2EdgeIndex, RandomEdgeCrossingsSparse) {
 
177
  for (int i = 0; i < 5; ++i) {
 
178
    TestCrossingsRandomInCap(2000, 100, 5000, 500, 8);
 
179
    TestCrossingsRandomInCap(2000, 300, 50000, 1000, 10);
 
180
  }
 
181
}
 
182
 
 
183
TEST(S2EdgeIndex, DegenerateEdgeOnCellVertexIsItsOwnCandidate) {
 
184
  for (int i = 0; i < 100; ++i) {
 
185
    S2Cell cell(S2Testing::GetRandomCellId());
 
186
    S2Edge e = make_pair(cell.GetVertex(0), cell.GetVertex(0));
 
187
    vector<S2Edge> all_edges;
 
188
    all_edges.push_back(e);
 
189
    EdgeVectorIndex index(&all_edges);
 
190
    index.ComputeIndex();
 
191
    EdgeVectorIndex::Iterator it(&index);
 
192
    it.GetCandidates(e.first, e.second);
 
193
    ASSERT_FALSE(it.Done());
 
194
    it.Next();
 
195
    ASSERT_TRUE(it.Done());
 
196
  }
 
197
}
 
198
 
 
199
TEST(S2EdgeIndex, LongEdgeCrossesLoop) {
 
200
  vector<S2Edge> all_edges;
 
201
  S2Point loop_center = S2Testing::MakePoint("42:107");
 
202
  pair<S2Point, S2Point> test_edge = make_pair(S2::Origin(), loop_center);
 
203
 
 
204
  S2Loop* loop = S2Testing::MakeRegularLoop(loop_center, 4,
 
205
                                            7e-3);  // = 5km/6400km
 
206
  for (int i = 0; i < loop->num_vertices(); ++i) {
 
207
    all_edges.push_back(make_pair(loop->vertex(i), loop->vertex(i+1)));
 
208
  }
 
209
  delete loop;
 
210
  EdgeVectorIndex index(&all_edges);
 
211
  index.ComputeIndex();
 
212
  EdgeVectorIndex::Iterator it(&index);
 
213
  it.GetCandidates(test_edge.first, test_edge.second);
 
214
 
 
215
  ASSERT_FALSE(it.Done());  // At least one candidate
 
216
}
 
217
 
 
218
TEST(S2EdgeIndex, CollinearEdgesOnCellBoundaries) {
 
219
  FLAGS_always_recurse_on_children = true;
 
220
  const int kNumPointsOnEdge = 8;  // About 32 edges
 
221
  for (int level = 0; level <= S2CellId::kMaxLevel; ++level) {
 
222
    S2Cell cell(S2Testing::GetRandomCellId(level));
 
223
    int v1 = S2Testing::rnd.Uniform(4);
 
224
    int v2 = (v1 + 1) & 3;
 
225
    S2Point p1 = cell.GetVertex(v1);
 
226
    S2Point p2 = cell.GetVertex(v2);
 
227
    S2Point p2_p1 = (p2 - p1) / kNumPointsOnEdge;
 
228
    vector<S2Edge> all_edges;
 
229
    S2Point points[kNumPointsOnEdge+1];
 
230
    for (int i = 0; i <= kNumPointsOnEdge; ++i) {
 
231
      points[i] = (p1 + i * p2_p1).Normalize();
 
232
      for (int j = 0; j < i; ++j) {
 
233
        all_edges.push_back(make_pair(points[i], points[j]));
 
234
      }
 
235
    }
 
236
    TestAllCrossings(all_edges, kNumPointsOnEdge*kNumPointsOnEdge,
 
237
                     kNumPointsOnEdge*kNumPointsOnEdge);
 
238
  }
 
239
}
 
240
 
 
241
TEST(S2EdgeIndex, QuadTreeGetsComputedAutomatically) {
 
242
  int const kNumVertices = 200;
 
243
  S2Point loop_center = S2Testing::MakePoint("42:107");
 
244
  S2Loop* loop = S2Testing::MakeRegularLoop(loop_center, kNumVertices,
 
245
                                            7e-3);  // = 5km/6400km
 
246
  S2Point q = S2Testing::MakePoint("5:5");
 
247
 
 
248
  S2LoopIndex index(loop);
 
249
  S2LoopIndex::Iterator it(&index);
 
250
 
 
251
  int num_candidates = 0;
 
252
  it.GetCandidates(q, q);
 
253
  for (; !it.Done(); it.Next()) {
 
254
    num_candidates++;
 
255
  }
 
256
  EXPECT_EQ(kNumVertices, num_candidates);
 
257
 
 
258
  bool computed = false;
 
259
  for (int i = 0; i < 500; ++i) {  // Trigger the quad tree computation
 
260
    num_candidates = 0;
 
261
    for (it.GetCandidates(q, q); !it.Done(); it.Next()) num_candidates++;
 
262
    if (!computed && num_candidates == 0) {
 
263
      LOG(INFO) << "Index was computed at iteration " << i;
 
264
      computed = true;
 
265
    }
 
266
  }
 
267
 
 
268
  num_candidates = 0;
 
269
  for (it.GetCandidates(q, q); !it.Done(); it.Next()) num_candidates++;
 
270
  EXPECT_EQ(0, num_candidates);
 
271
 
 
272
  delete loop;
 
273
}
 
274
 
 
275
 
 
276
// MICROBENCHMARKS (and related structures)
 
277
 
 
278
// Generates a bunch of random edges and tests each against all others for
 
279
// crossings. This is just for benchmarking; there's no correctness testing in
 
280
// this function. Set "cutoff_level" negative to apply brute force checking.
 
281
static void ComputeCrossings(int num_edges,
 
282
                             double edge_length_max,
 
283
                             double cap_span_meters,
 
284
                             int brute_force) {
 
285
  StopBenchmarkTiming();
 
286
  vector<S2Edge> all_edges;
 
287
  GenerateRandomEarthEdges(edge_length_max, cap_span_meters, num_edges,
 
288
                           &all_edges);
 
289
  StartBenchmarkTiming();
 
290
  if (brute_force) {
 
291
    for (vector<S2Edge>::const_iterator it = all_edges.begin();
 
292
         it != all_edges.end(); ++it) {
 
293
      for (vector<S2Edge>::const_iterator it2 = all_edges.begin();
 
294
           it2 != all_edges.end(); ++it2) {
 
295
        S2EdgeUtil::RobustCrossing(it->first, it->second,
 
296
                                   it2->first, it2->second);
 
297
      }
 
298
    }
 
299
  } else {
 
300
    EdgeVectorIndex index(&all_edges);
 
301
    index.ComputeIndex();
 
302
    EdgeVectorIndex::Iterator can_it(&index);
 
303
    for (vector<S2Edge>::const_iterator it = all_edges.begin();
 
304
         it != all_edges.end(); ++it) {
 
305
      for (can_it.GetCandidates(it->first, it->second);
 
306
           !can_it.Done(); can_it.Next()) {
 
307
        int in = can_it.Index();
 
308
        S2EdgeUtil::RobustCrossing(all_edges[in].first, all_edges[in].second,
 
309
                                   it->first,
 
310
                                   it->second);
 
311
      }
 
312
    }
 
313
  }
 
314
}
 
315
 
 
316
// "Sparse" tests are those where we expect relatively few segment crossings.
 
317
// In general the segment lengths are short (< 300m) and the random segments
 
318
// are distributed over caps of radius 5-50km.
 
319
 
 
320
static void BM_TestCrossingsSparse(int iters, int num_edges, int brute_force) {
 
321
  for (int i = 0; i < iters; ++i) {
 
322
    ComputeCrossings(num_edges, 30,  5000,  brute_force);
 
323
    ComputeCrossings(num_edges, 100, 5000,  brute_force);
 
324
  }
 
325
}
 
326
BENCHMARK(BM_TestCrossingsSparse)
 
327
    ->ArgPair(10, true)
 
328
    ->ArgPair(10, false)
 
329
    ->ArgPair(50, true)
 
330
    ->ArgPair(50, false)
 
331
    ->ArgPair(100, true)
 
332
    ->ArgPair(100, false)
 
333
    ->ArgPair(300, true)
 
334
    ->ArgPair(300, false)
 
335
    ->ArgPair(600, true)
 
336
    ->ArgPair(600, false)
 
337
    ->ArgPair(1000, true)
 
338
    ->ArgPair(1000, false)
 
339
    ->ArgPair(2000, false)
 
340
    ->ArgPair(5000, false)
 
341
    ->ArgPair(10000, false)
 
342
    ->ArgPair(20000, false)
 
343
    ->ArgPair(50000, false)
 
344
    ->ArgPair(100000, false);
 
345
 
 
346
// These benchmarks are used to find the right trade-off between brute force
 
347
// and quad tree.
 
348
 
 
349
// To compute kQuadTreeInsertionCost
 
350
static void BM_QuadTreeInsertionCost(int iters) {
 
351
  const int kNumVertices = 1000;
 
352
  StopBenchmarkTiming();
 
353
  S2Point loop_center = S2Testing::MakePoint("42:107");
 
354
  S2Loop* loop = S2Testing::MakeRegularLoop(loop_center, kNumVertices,
 
355
                                            7e-3);  // = 5km/6400km
 
356
  StartBenchmarkTiming();
 
357
 
 
358
  for (int i = 0; i < iters; ++i) {
 
359
    S2LoopIndex index(loop);
 
360
    index.ComputeIndex();
 
361
  }
 
362
  delete loop;
 
363
}
 
364
BENCHMARK(BM_QuadTreeInsertionCost);
 
365
 
 
366
// To compute kQuadTreeFindCost
 
367
static void BM_QuadTreeFindCost(int iters, int num_vertices) {
 
368
  StopBenchmarkTiming();
 
369
  S2Point loop_center = S2Testing::MakePoint("42:107");
 
370
  S2Loop* loop = S2Testing::MakeRegularLoop(loop_center, num_vertices,
 
371
                                            7e-3);  // = 5km/6400km
 
372
  S2Point p(S2Testing::MakePoint("42:106.99"));
 
373
  S2Point q(S2Testing::MakePoint("42:107.01"));
 
374
  S2LoopIndex index(loop);
 
375
  index.ComputeIndex();
 
376
  EdgeVectorIndex::Iterator can_it(&index);
 
377
  StartBenchmarkTiming();
 
378
 
 
379
  for (int i = 0; i < iters; ++i) {
 
380
    can_it.GetCandidates(p, q);
 
381
  }
 
382
  delete loop;
 
383
}
 
384
BENCHMARK(BM_QuadTreeFindCost)
 
385
  ->Arg(10)
 
386
  ->Arg(100)
 
387
  ->Arg(1000)
 
388
  ->Arg(10000);