← 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/s2polygonbuilder.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/s2polygonbuilder.cc
 
1
// Copyright 2006 Google Inc. All Rights Reserved.
 
2
 
 
3
#include "s2polygonbuilder.h"
 
4
 
 
5
#include "s2.h"
 
6
#include <algorithm>
 
7
using std::min;
 
8
using std::max;
 
9
using std::swap;
 
10
using std::reverse;
 
11
 
 
12
#include "hash.h"
 
13
 
 
14
#include <iomanip>
 
15
using std::setprecision;
 
16
 
 
17
#include <iostream>
 
18
using std::ostream;
 
19
using std::cout;
 
20
using std::endl;
 
21
 
 
22
#include <map>
 
23
using std::map;
 
24
using std::multimap;
 
25
 
 
26
#include <set>
 
27
using std::set;
 
28
using std::multiset;
 
29
 
 
30
#include <vector>
 
31
using std::vector;
 
32
 
 
33
 
 
34
#include "base/logging.h"
 
35
#include "base/macros.h"
 
36
#include "s2.h"
 
37
#include "s2cellid.h"
 
38
#include "s2polygon.h"
 
39
#include "util/math/matrix3x3-inl.h"
 
40
 
 
41
void S2PolygonBuilderOptions::set_undirected_edges(bool undirected_edges) {
 
42
  undirected_edges_ = undirected_edges;
 
43
}
 
44
 
 
45
void S2PolygonBuilderOptions::set_xor_edges(bool xor_edges) {
 
46
  xor_edges_ = xor_edges;
 
47
}
 
48
 
 
49
void S2PolygonBuilderOptions::set_validate(bool validate) {
 
50
  validate_ = validate;
 
51
}
 
52
 
 
53
void S2PolygonBuilderOptions::set_vertex_merge_radius(S1Angle const& angle) {
 
54
  vertex_merge_radius_ = angle;
 
55
}
 
56
 
 
57
void S2PolygonBuilderOptions::set_edge_splice_fraction(double fraction) {
 
58
  CHECK(fraction < sqrt(3) / 2);
 
59
  edge_splice_fraction_ = fraction;
 
60
}
 
61
 
 
62
S2PolygonBuilder::S2PolygonBuilder(S2PolygonBuilderOptions const& options)
 
63
  : options_(options), edges_(new EdgeSet) {
 
64
}
 
65
 
 
66
S2PolygonBuilder::~S2PolygonBuilder() {
 
67
}
 
68
 
 
69
bool S2PolygonBuilder::HasEdge(S2Point const& v0, S2Point const& v1) {
 
70
  EdgeSet::const_iterator candidates = edges_->find(v0);
 
71
  return (candidates != edges_->end() &&
 
72
          candidates->second.find(v1) != candidates->second.end());
 
73
}
 
74
 
 
75
bool S2PolygonBuilder::AddEdge(S2Point const& v0, S2Point const& v1) {
 
76
  // If xor_edges is true, we look for an existing edge in the opposite
 
77
  // direction.  We either delete that edge or insert a new one.
 
78
 
 
79
  if (v0 == v1) return false;
 
80
  if (options_.xor_edges() && HasEdge(v1, v0)) {
 
81
    EraseEdge(v1, v0);
 
82
    return false;
 
83
  }
 
84
  if (edges_->find(v0) == edges_->end()) starting_vertices_.push_back(v0);
 
85
  (*edges_)[v0].insert(v1);
 
86
  if (options_.undirected_edges()) {
 
87
    if (edges_->find(v1) == edges_->end()) starting_vertices_.push_back(v1);
 
88
    (*edges_)[v1].insert(v0);
 
89
  }
 
90
  return true;
 
91
}
 
92
 
 
93
void S2PolygonBuilder::AddLoop(S2Loop const* loop) {
 
94
  int sign = loop->sign();
 
95
  for (int i = loop->num_vertices(); i > 0; --i) {
 
96
    // Vertex indices need to be in the range [0, 2*num_vertices()-1].
 
97
    AddEdge(loop->vertex(i), loop->vertex(i + sign));
 
98
  }
 
99
}
 
100
 
 
101
void S2PolygonBuilder::AddPolygon(S2Polygon const* polygon) {
 
102
  for (int i = 0; i < polygon->num_loops(); ++i) {
 
103
    AddLoop(polygon->loop(i));
 
104
  }
 
105
}
 
106
 
 
107
void S2PolygonBuilder::EraseEdge(S2Point const& v0, S2Point const& v1) {
 
108
  // Note that there may be more than one copy of an edge if we are not XORing
 
109
  // them, so a VertexSet is a multiset.
 
110
 
 
111
  VertexSet* vset = &(*edges_)[v0];
 
112
  DCHECK(vset->find(v1) != vset->end());
 
113
  vset->erase(vset->find(v1));
 
114
  if (vset->empty()) edges_->erase(v0);
 
115
 
 
116
  if (options_.undirected_edges()) {
 
117
    vset = &(*edges_)[v1];
 
118
    DCHECK(vset->find(v0) != vset->end());
 
119
    vset->erase(vset->find(v0));
 
120
    if (vset->empty()) edges_->erase(v1);
 
121
  }
 
122
}
 
123
 
 
124
void S2PolygonBuilder::set_debug_matrix(Matrix3x3_d const& m) {
 
125
  debug_matrix_.reset(new Matrix3x3_d(m));
 
126
}
 
127
 
 
128
void S2PolygonBuilder::DumpVertex(S2Point const& v) const {
 
129
  if (debug_matrix_.get()) {
 
130
    // For orthonormal matrices, Inverse() == Transpose().
 
131
    cout << S2LatLng(debug_matrix_->Transpose() * v);
 
132
  } else {
 
133
    cout << setprecision(17) << v << setprecision(6);
 
134
  }
 
135
}
 
136
 
 
137
void S2PolygonBuilder::DumpEdges(S2Point const& v0) const {
 
138
  DumpVertex(v0);
 
139
  cout << ":\n";
 
140
  EdgeSet::const_iterator candidates = edges_->find(v0);
 
141
  if (candidates != edges_->end()) {
 
142
    VertexSet const& vset = candidates->second;
 
143
    for (VertexSet::const_iterator i = vset.begin(); i != vset.end(); ++i) {
 
144
      cout << "    ";
 
145
      DumpVertex(*i);
 
146
      cout << "\n";
 
147
    }
 
148
  }
 
149
}
 
150
 
 
151
void S2PolygonBuilder::Dump() const {
 
152
  for (EdgeSet::const_iterator i = edges_->begin(); i != edges_->end(); ++i) {
 
153
    DumpEdges(i->first);
 
154
  }
 
155
}
 
156
 
 
157
void S2PolygonBuilder::EraseLoop(S2Point const* v, int n) {
 
158
  for (int i = n - 1, j = 0; j < n; i = j++) {
 
159
    EraseEdge(v[i], v[j]);
 
160
  }
 
161
}
 
162
 
 
163
void S2PolygonBuilder::RejectLoop(S2Point const* v, int n,
 
164
                                  EdgeList* unused_edges) {
 
165
  for (int i = n - 1, j = 0; j < n; i = j++) {
 
166
    unused_edges->push_back(make_pair(v[i], v[j]));
 
167
  }
 
168
}
 
169
 
 
170
S2Loop* S2PolygonBuilder::AssembleLoop(S2Point const& v0, S2Point const& v1,
 
171
                                       EdgeList* unused_edges) {
 
172
  // We start at the given edge and assemble a loop taking left turns
 
173
  // whenever possible.  We stop the loop as soon as we encounter any
 
174
  // vertex that we have seen before *except* for the first vertex (v0).
 
175
  // This ensures that only CCW loops are constructed when possible.
 
176
 
 
177
  vector<S2Point> path;          // The path so far.
 
178
  hash_map<S2Point, int> index;  // Maps a vertex to its index in "path".
 
179
  path.push_back(v0);
 
180
  path.push_back(v1);
 
181
  index[v1] = 1;
 
182
  while (path.size() >= 2) {
 
183
    // Note that "v0" and "v1" become invalid if "path" is modified.
 
184
    S2Point const& v0 = path.end()[-2];
 
185
    S2Point const& v1 = path.end()[-1];
 
186
    S2Point v2;
 
187
    bool v2_found = false;
 
188
    EdgeSet::const_iterator candidates = edges_->find(v1);
 
189
    if (candidates != edges_->end()) {
 
190
      VertexSet const& vset = candidates->second;
 
191
      for (VertexSet::const_iterator i = vset.begin(); i != vset.end(); ++i) {
 
192
        // We prefer the leftmost outgoing edge, ignoring any reverse edges.
 
193
        if (*i == v0) continue;
 
194
        if (!v2_found || S2::OrderedCCW(v0, v2, *i, v1)) { v2 = *i; }
 
195
        v2_found = true;
 
196
      }
 
197
    }
 
198
    if (!v2_found) {
 
199
      // We've hit a dead end.  Remove this edge and backtrack.
 
200
      unused_edges->push_back(make_pair(v0, v1));
 
201
      EraseEdge(v0, v1);
 
202
      index.erase(v1);
 
203
      path.pop_back();
 
204
    } else if (index.insert(make_pair(v2, path.size())).second) {
 
205
      // This is the first time we've visited this vertex.
 
206
      path.push_back(v2);
 
207
    } else {
 
208
      // We've completed a loop.  Throw away any initial vertices that
 
209
      // are not part of the loop.
 
210
      path.erase(path.begin(), path.begin() + index[v2]);
 
211
 
 
212
      // In the case of undirected edges, we may have assembled a clockwise
 
213
      // loop while trying to assemble a CCW loop.  To fix this, we assemble
 
214
      // a new loop starting with an arbitrary edge in the reverse direction.
 
215
      // This is guaranteed to assemble a loop that is interior to the previous
 
216
      // one and will therefore eventually terminate.
 
217
 
 
218
      S2Loop* loop = new S2Loop(path);
 
219
      if (options_.validate() && !loop->IsValid()) {
 
220
        // We've constructed a loop that crosses itself, which can only
 
221
        // happen if there is bad input data.  Throw away the whole loop.
 
222
        RejectLoop(&path[0], path.size(), unused_edges);
 
223
        EraseLoop(&path[0], path.size());
 
224
        delete loop;
 
225
        return NULL;
 
226
      }
 
227
 
 
228
      if (options_.undirected_edges() && !loop->IsNormalized()) {
 
229
        scoped_ptr<S2Loop> deleter(loop);  // XXX for debugging
 
230
        return AssembleLoop(path[1], path[0], unused_edges);
 
231
      }
 
232
      return loop;
 
233
    }
 
234
  }
 
235
  return NULL;
 
236
}
 
237
 
 
238
class S2PolygonBuilder::PointIndex {
 
239
  // A PointIndex is a cheap spatial index to help us find mergeable
 
240
  // vertices.  Given a set of points, it can efficiently find all of the
 
241
  // points within a given search radius of an arbitrary query location.
 
242
  // It is essentially just a hash map from cell ids at a given fixed level to
 
243
  // the set of points contained by that cell id.
 
244
  //
 
245
  // This class is not suitable for general use because it only supports
 
246
  // fixed-radius queries and has various special-purpose operations to avoid
 
247
  // the need for additional data structures.
 
248
 
 
249
 private:
 
250
  typedef multimap<S2CellId, S2Point> Map;
 
251
  Map map_;
 
252
 
 
253
  double vertex_radius_;
 
254
  double edge_fraction_;
 
255
  int level_;
 
256
  vector<S2CellId> ids_;  // Allocated here for efficiency.
 
257
 
 
258
 public:
 
259
  PointIndex(double vertex_radius, double edge_fraction)
 
260
    : vertex_radius_(vertex_radius),
 
261
      edge_fraction_(edge_fraction),
 
262
      // We compute an S2CellId level such that the vertex neighbors at that
 
263
      // level of any point A are a covering for spherical cap (i.e. "disc")
 
264
      // of the given search radius centered at A.  This requires that the
 
265
      // minimum cell width at that level must be twice the search radius.
 
266
      level_(min(S2::kMinWidth.GetMaxLevel(2 * vertex_radius),
 
267
                 S2CellId::kMaxLevel - 1)) {
 
268
    // We insert a sentinel so that we don't need to test for map_.end().
 
269
    map_.insert(make_pair(S2CellId::Sentinel(), S2Point()));
 
270
  }
 
271
 
 
272
  void Insert(S2Point const& p) {
 
273
    S2CellId::FromPoint(p).AppendVertexNeighbors(level_, &ids_);
 
274
    for (int i = ids_.size(); --i >= 0; ) {
 
275
      map_.insert(make_pair(ids_[i], p));
 
276
    }
 
277
    ids_.clear();
 
278
  }
 
279
 
 
280
  void Erase(S2Point const& p) {
 
281
    S2CellId::FromPoint(p).AppendVertexNeighbors(level_, &ids_);
 
282
    for (int i = ids_.size(); --i >= 0; ) {
 
283
      Map::iterator j = map_.lower_bound(ids_[i]);
 
284
      for (; j->second != p; ++j) {
 
285
        DCHECK_EQ(ids_[i], j->first);
 
286
      }
 
287
      map_.erase(j);
 
288
    }
 
289
    ids_.clear();
 
290
  }
 
291
 
 
292
  void QueryCap(S2Point const& axis, vector<S2Point>* output) {
 
293
    // Return the set the points whose distance to "axis" is less than
 
294
    // vertex_radius_.
 
295
 
 
296
    output->clear();
 
297
    S2CellId id = S2CellId::FromPoint(axis).parent(level_);
 
298
    for (Map::const_iterator i = map_.lower_bound(id); i->first == id; ++i) {
 
299
      S2Point const& p = i->second;
 
300
      if (axis.Angle(p) < vertex_radius_) {
 
301
        output->push_back(p);
 
302
      }
 
303
    }
 
304
  }
 
305
 
 
306
  bool FindNearbyPoint(S2Point const& v0, S2Point const& v1,
 
307
                       S2Point* nearby) {
 
308
    // Return a point whose distance from the edge (v0,v1) is less than
 
309
    // vertex_radius_, and which is not equal to v0 or v1.  The current
 
310
    // implementation returns the closest such point.
 
311
    //
 
312
    // Strategy: we compute a very cheap covering by approximating the edge as
 
313
    // two spherical caps, one around each endpoint, and then computing a
 
314
    // 4-cell covering of each one.  We could improve the quality of the
 
315
    // covering by using some intermediate points along the edge as well.
 
316
 
 
317
    double length = v0.Angle(v1);
 
318
    S2Point normal = S2::RobustCrossProd(v0, v1);
 
319
    int level = min(level_, S2::kMinWidth.GetMaxLevel(length));
 
320
    S2CellId::FromPoint(v0).AppendVertexNeighbors(level, &ids_);
 
321
    S2CellId::FromPoint(v1).AppendVertexNeighbors(level, &ids_);
 
322
 
 
323
    // Sort the cell ids so that we can skip duplicates in the loop below.
 
324
    sort(ids_.begin(), ids_.end());
 
325
 
 
326
    double best_dist = 2 * vertex_radius_;
 
327
    for (int i = ids_.size(); --i >= 0; ) {
 
328
      if (i > 0 && ids_[i-1] == ids_[i]) continue;  // Skip duplicates.
 
329
 
 
330
      S2CellId const& max_id = ids_[i].range_max();
 
331
      for (Map::const_iterator j = map_.lower_bound(ids_[i].range_min());
 
332
           j->first <= max_id; ++j) {
 
333
        S2Point const& p = j->second;
 
334
        if (p == v0 || p == v1) continue;
 
335
        double dist = S2EdgeUtil::GetDistance(p, v0, v1, normal).radians();
 
336
        if (dist < best_dist) {
 
337
          best_dist = dist;
 
338
          *nearby = p;
 
339
        }
 
340
      }
 
341
    }
 
342
    ids_.clear();
 
343
    return (best_dist < edge_fraction_ * vertex_radius_);
 
344
  }
 
345
 
 
346
 private:
 
347
  DISALLOW_EVIL_CONSTRUCTORS(PointIndex);
 
348
};
 
349
 
 
350
void S2PolygonBuilder::BuildMergeMap(PointIndex* index, MergeMap* merge_map) {
 
351
  // The overall strategy is to start from each vertex and grow a maximal
 
352
  // cluster of mergeable vertices.  In graph theoretic terms, we find the
 
353
  // connected components of the undirected graph whose edges connect pairs of
 
354
  // vertices that are separated by at most vertex_merge_radius().
 
355
  //
 
356
  // We then choose a single representative vertex for each cluster, and
 
357
  // update "merge_map" appropriately.  We choose an arbitrary existing
 
358
  // vertex rather than computing the centroid of all the vertices to avoid
 
359
  // creating new vertex pairs that need to be merged.  (We guarantee that all
 
360
  // vertex pairs are separated by at least the merge radius in the output.)
 
361
 
 
362
  // First, we build the set of all the distinct vertices in the input.
 
363
  // We need to include the source and destination of every edge.
 
364
  hash_set<S2Point> vertices;
 
365
  for (EdgeSet::const_iterator i = edges_->begin(); i != edges_->end(); ++i) {
 
366
    vertices.insert(i->first);
 
367
    VertexSet const& vset = i->second;
 
368
    for (VertexSet::const_iterator j = vset.begin(); j != vset.end(); ++j)
 
369
      vertices.insert(*j);
 
370
  }
 
371
 
 
372
  // Build a spatial index containing all the distinct vertices.
 
373
  for (hash_set<S2Point>::const_iterator i = vertices.begin();
 
374
       i != vertices.end(); ++i) {
 
375
    index->Insert(*i);
 
376
  }
 
377
 
 
378
  // Next, we loop through all the vertices and attempt to grow a maximial
 
379
  // mergeable group starting from each vertex.
 
380
  vector<S2Point> frontier, mergeable;
 
381
  for (hash_set<S2Point>::const_iterator vstart = vertices.begin();
 
382
       vstart != vertices.end(); ++vstart) {
 
383
    // Skip any vertices that have already been merged with another vertex.
 
384
    if (merge_map->find(*vstart) != merge_map->end()) continue;
 
385
 
 
386
    // Grow a maximal mergeable component starting from "vstart", the
 
387
    // canonical representative of the mergeable group.
 
388
    frontier.push_back(*vstart);
 
389
    while (!frontier.empty()) {
 
390
      index->QueryCap(frontier.back(), &mergeable);
 
391
      frontier.pop_back();  // Do this before entering the loop below.
 
392
      for (int j = mergeable.size(); --j >= 0; ) {
 
393
        S2Point const& v1 = mergeable[j];
 
394
        if (v1 != *vstart) {
 
395
          // Erase from the index any vertices that will be merged.  This
 
396
          // ensures that we won't try to merge the same vertex twice.
 
397
          index->Erase(v1);
 
398
          frontier.push_back(v1);
 
399
          (*merge_map)[v1] = *vstart;
 
400
        }
 
401
      }
 
402
    }
 
403
  }
 
404
}
 
405
 
 
406
void S2PolygonBuilder::MoveVertices(MergeMap const& merge_map) {
 
407
  if (merge_map.empty()) return;
 
408
 
 
409
  // We need to copy the set of edges affected by the move, since
 
410
  // edges_ could be reallocated when we start modifying it.
 
411
  vector<pair<S2Point, S2Point> > edges;
 
412
  for (EdgeSet::const_iterator i = edges_->begin(); i != edges_->end(); ++i) {
 
413
    S2Point const& v0 = i->first;
 
414
    VertexSet const& vset = i->second;
 
415
    for (VertexSet::const_iterator j = vset.begin(); j != vset.end(); ++j) {
 
416
      S2Point const& v1 = *j;
 
417
      if (merge_map.find(v0) != merge_map.end() ||
 
418
          merge_map.find(v1) != merge_map.end()) {
 
419
        // We only need to modify one copy of each undirected edge.
 
420
        if (!options_.undirected_edges() || v0 < v1) {
 
421
          edges.push_back(make_pair(v0, v1));
 
422
        }
 
423
      }
 
424
    }
 
425
  }
 
426
 
 
427
  // Now erase all the old edges, and add all the new edges.  This will
 
428
  // automatically take care of any XORing that needs to be done, because
 
429
  // EraseEdge also erases the sibling of undirected edges.
 
430
  for (size_t i = 0; i < edges.size(); ++i) {
 
431
    S2Point v0 = edges[i].first;
 
432
    S2Point v1 = edges[i].second;
 
433
    EraseEdge(v0, v1);
 
434
    MergeMap::const_iterator new0 = merge_map.find(v0);
 
435
    if (new0 != merge_map.end()) v0 = new0->second;
 
436
    MergeMap::const_iterator new1 = merge_map.find(v1);
 
437
    if (new1 != merge_map.end()) v1 = new1->second;
 
438
    AddEdge(v0, v1);
 
439
  }
 
440
}
 
441
 
 
442
void S2PolygonBuilder::SpliceEdges(PointIndex* index) {
 
443
  // We keep a stack of unprocessed edges.  Initially all edges are
 
444
  // pushed onto the stack.
 
445
  vector<pair<S2Point, S2Point> > edges;
 
446
  for (EdgeSet::const_iterator i = edges_->begin(); i != edges_->end(); ++i) {
 
447
    S2Point const& v0 = i->first;
 
448
    VertexSet const& vset = i->second;
 
449
    for (VertexSet::const_iterator j = vset.begin(); j != vset.end(); ++j) {
 
450
      S2Point const& v1 = *j;
 
451
      // We only need to modify one copy of each undirected edge.
 
452
      if (!options_.undirected_edges() || v0 < v1) {
 
453
        edges.push_back(make_pair(v0, v1));
 
454
      }
 
455
    }
 
456
  }
 
457
 
 
458
  // For each edge, we check whether there are any nearby vertices that should
 
459
  // be spliced into it.  If there are, we choose one such vertex, split
 
460
  // the edge into two pieces, and iterate on each piece.
 
461
  while (!edges.empty()) {
 
462
    S2Point v0 = edges.back().first;
 
463
    S2Point v1 = edges.back().second;
 
464
    edges.pop_back();  // Do this before pushing new edges.
 
465
 
 
466
    // If we are xoring, edges may be erased before we get to them.
 
467
    if (options_.xor_edges() && !HasEdge(v0, v1)) continue;
 
468
 
 
469
    S2Point vmid;
 
470
    if (!index->FindNearbyPoint(v0, v1, &vmid)) continue;
 
471
 
 
472
    EraseEdge(v0, v1);
 
473
    if (AddEdge(v0, vmid)) edges.push_back(make_pair(v0, vmid));
 
474
    if (AddEdge(vmid, v1)) edges.push_back(make_pair(vmid, v1));
 
475
  }
 
476
}
 
477
 
 
478
bool S2PolygonBuilder::AssembleLoops(vector<S2Loop*>* loops,
 
479
                                     EdgeList* unused_edges) {
 
480
  if (options_.vertex_merge_radius().radians() > 0) {
 
481
    PointIndex index(options_.vertex_merge_radius().radians(),
 
482
                     options_.edge_splice_fraction());
 
483
    MergeMap merge_map;
 
484
    BuildMergeMap(&index, &merge_map);
 
485
    MoveVertices(merge_map);
 
486
    if (options_.edge_splice_fraction() > 0) {
 
487
      SpliceEdges(&index);
 
488
    }
 
489
  }
 
490
 
 
491
  EdgeList dummy_unused_edges;
 
492
  if (unused_edges == NULL) unused_edges = &dummy_unused_edges;
 
493
 
 
494
  // We repeatedly choose an edge and attempt to assemble a loop
 
495
  // starting from that edge.  (This is always possible unless the
 
496
  // input includes extra edges that are not part of any loop.)  To
 
497
  // maintain a consistent scanning order over edges_ between
 
498
  // different machine architectures (e.g. 'clovertown' vs. 'opteron'),
 
499
  // we follow the order they were added to the builder.
 
500
  unused_edges->clear();
 
501
  for (size_t i = 0; i < starting_vertices_.size(); ) {
 
502
    S2Point const& v0 = starting_vertices_[i];
 
503
    EdgeSet::const_iterator candidates = edges_->find(v0);
 
504
    if (candidates == edges_->end()) {
 
505
      ++i;
 
506
      continue;
 
507
    }
 
508
    // NOTE(user): If we have such two S2Points a, b that:
 
509
    //
 
510
    //   a.x = b.x, a.y = b.y and
 
511
    //   -- a.z = b.z if CPU is Intel
 
512
    //   -- a.z <> b.z if CPU is AMD
 
513
    //
 
514
    // then the order of points picked up as v1 on the following line
 
515
    // can be inconsistent between different machine architectures.
 
516
    //
 
517
    // As of b/3088321 and of cl/17847332, it's not clear if such
 
518
    // input really exists in our input and probably it's O.K. not to
 
519
    // address it in favor of the speed.
 
520
    S2Point const& v1 = *(candidates->second.begin());
 
521
    S2Loop* loop = AssembleLoop(v0, v1, unused_edges);
 
522
    if (loop != NULL) {
 
523
      loops->push_back(loop);
 
524
      EraseLoop(&loop->vertex(0), loop->num_vertices());
 
525
    }
 
526
  }
 
527
  return unused_edges->empty();
 
528
}
 
529
 
 
530
bool S2PolygonBuilder::AssemblePolygon(S2Polygon* polygon,
 
531
                                       EdgeList* unused_edges) {
 
532
  vector<S2Loop*> loops;
 
533
  bool success = AssembleLoops(&loops, unused_edges);
 
534
 
 
535
  // If edges are undirected, then all loops are already CCW.  Otherwise we
 
536
  // need to make sure the loops are normalized.
 
537
  if (!options_.undirected_edges()) {
 
538
    for (size_t i = 0; i < loops.size(); ++i) {
 
539
      loops[i]->Normalize();
 
540
    }
 
541
  }
 
542
  if (options_.validate() && !S2Polygon::IsValid(loops)) {
 
543
    if (unused_edges != NULL) {
 
544
      for (size_t i = 0; i < loops.size(); ++i) {
 
545
        RejectLoop(&loops[i]->vertex(0), loops[i]->num_vertices(),
 
546
                   unused_edges);
 
547
      }
 
548
    }
 
549
 
 
550
    for (size_t i = 0; i < loops.size(); ++i) {
 
551
      delete loops[i];
 
552
    }
 
553
    loops.clear();
 
554
    return false;
 
555
  }
 
556
  polygon->Init(&loops);
 
557
  return success;
 
558
}