1// Copyright 2006 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2POLYGONBUILDER_H__
4#define UTIL_GEOMETRY_S2POLYGONBUILDER_H__
5
6#include <hash_map>
7using __gnu_cxx::hash_map;
8
9#include <set>
10using std::set;
11using std::multiset;
12
13#include <utility>
14using std::pair;
15using std::make_pair;
16
17#include <vector>
18using std::vector;
19
20#include "base/basictypes.h"
21#include "base/scoped_ptr.h"
22#include "s2.h"
23#include "s1angle.h"
24#include "util/math/matrix3x3.h"
25
26class S2Loop;
27class S2Polygon;
28
29// This is a simple class for assembling polygons out of edges. It requires
30// that no two edges cross. It can handle both directed and undirected edges,
31// and optionally it can also remove duplicate edge pairs (consisting of two
32// identical edges or an edge and its reverse edge). This is useful for
33// computing seamless unions of polygons that have been cut into pieces.
34//
35// Here are some of the situations this class was designed to handle:
36//
37// 1. Computing the union of disjoint polygons that may share part of their
38// boundaries. For example, reassembling a lake that has been split into
39// two loops by a state boundary.
40//
41// 2. Constructing polygons from input data that does not follow S2
42// conventions, i.e. where loops may have repeated vertices, or distinct
43// loops may share edges, or shells and holes have opposite or unspecified
44// orientations.
45//
46// 3. Computing the symmetric difference of a set of polygons whose edges
47// intersect only at vertices. This can be used to implement a limited
48// form of polygon intersection or subtraction as well as unions.
49//
50// 4. As a tool for implementing other polygon operations by generating a
51// collection of directed edges and then assembling them into loops.
52class S2PolygonBuilderOptions {
53 public:
54 S2PolygonBuilderOptions() :
55 undirected_edges_(false), xor_edges_(true), validate_(false),
56 vertex_merge_radius_(S1Angle::Radians(0)),
57 edge_splice_fraction_(0.866) {}
58
59 // These are the options that should be used for assembling well-behaved
60 // input data into polygons. All edges should be directed such that
61 // "shells" and "holes" have opposite orientations (typically CCW shells and
62 // clockwise holes), unless it is known that shells and holes do not share
63 // any edges.
64 inline static S2PolygonBuilderOptions DIRECTED_XOR();
65
66 // These are the options that should be used for assembling polygons that do
67 // not follow the conventions above, e.g. where edge directions may vary
68 // within a single loop, or shells and holes are not oppositely oriented and
69 // may share edges.
70 inline static S2PolygonBuilderOptions UNDIRECTED_XOR();
71
72 // These are the options that should be used for assembling edges where the
73 // desired output is a collection of loops rather than a polygon, and edges
74 // may occur more than once. Edges are treated as undirected and are not
75 // XORed together.
76 inline static S2PolygonBuilderOptions UNDIRECTED_UNION();
77
78 // Default value: false.
79 //
80 // If "undirected_edges" is false, then the input is assumed to consist of
81 // edges that can be assembled into oriented loops without reversing any of
82 // the edges. Otherwise, "undirected_edges" should be set to true.
83 bool undirected_edges() const { return undirected_edges_; }
84 void set_undirected_edges(bool undirected_edges);
85
86 // Default value: true.
87 //
88 // If "xor_edges" is true, then any duplicate edge pairs are removed. This
89 // is useful for computing the union of a collection of polygons whose
90 // interiors are disjoint but whose boundaries may share some common edges
91 // (e.g. computing the union of South Africa, Lesotho, and Swaziland).
92 //
93 // Note that for directed edges, a "duplicate edge pair" consists of an edge
94 // and its corresponding reverse edge. This means that either (a) "shells"
95 // and "holes" must have opposite orientations, or (b) shells and holes do
96 // not share edges. Otherwise undirected_edges() should be specified.
97 //
98 // There are only two reasons to turn off xor_edges():
99 //
100 // (1) AssemblePolygon() will be called, and you want to assert that there
101 // are no duplicate edge pairs in the input.
102 //
103 // (2) AssembleLoops() will be called, and you want to keep abutting loops
104 // separate in the output rather than merging their regions together
105 // (e.g. assembling loops for Kansas City, KS and Kansas City, MO
106 // simultaneously).
107 bool xor_edges() const { return xor_edges_; }
108 void set_xor_edges(bool xor_edges);
109
110 // Default value: false.
111 //
112 // If true, IsValid() is called on all loops and polygons before
113 // constructing them. If any loop is invalid (e.g. self-intersecting), it
114 // is rejected and returned as a set of "unused edges". Any remaining valid
115 // loops are kept. If the entire polygon is invalid (e.g. two loops
116 // intersect), then all loops are rejected and returned as unused edges.
117 bool validate() const { return validate_; }
118 void set_validate(bool validate);
119
120 // Default value: 0.
121 //
122 // If set to a positive value, all vertex pairs that are separated by less
123 // than this distance will be merged together. Note that vertices can move
124 // arbitrarily far if there is a long chain of vertices separated by less
125 // than this distance.
126 //
127 // This method is useful for assembling polygons out of input data where
128 // vertices and/or edges may not be perfectly aligned.
129 S1Angle vertex_merge_radius() const { return vertex_merge_radius_; }
130 void set_vertex_merge_radius(S1Angle const& vertex_merge_radius);
131
132 // Default value: 0.866 (approximately sqrt(3)/2).
133 //
134 // The edge splice radius is automatically set to this fraction of the vertex
135 // merge radius. If the edge splice radius is positive, then all vertices
136 // that are closer than this distance to an edge are spliced into that edge.
137 // Note that edges can move arbitrarily far if there is a long chain of
138 // vertices in just the right places.
139 //
140 // You can turn off edge splicing by setting this value to zero. This will
141 // save some time if you don't need this feature, or you don't want vertices
142 // to be spliced into nearby edges for some reason.
143 //
144 // Note that the edge splice fraction must be less than sqrt(3)/2 in order to
145 // avoid infinite loops in the merge algorithm. The default value is very
146 // close to this maximum and therefore results in the maximum amount of edge
147 // splicing for a given vertex merge radius.
148 //
149 // The only reason to reduce the edge splice fraction is if you want to limit
150 // changes in edge direction due to splicing. The direction of an edge can
151 // change by up to asin(edge_splice_fraction) due to each splice. Thus by
152 // default, edges are allowed to change direction by up to 60 degrees per
153 // splice. However, note that most direction changes are much smaller than
154 // this: the worst case occurs only if the vertex being spliced is just
155 // outside the vertex merge radius from one of the edge endpoints.
156 double edge_splice_fraction() const { return edge_splice_fraction_; }
157 void set_edge_splice_fraction(double edge_splice_fraction);
158
159 private:
160 bool undirected_edges_;
161 bool xor_edges_;
162 bool validate_;
163 S1Angle vertex_merge_radius_;
164 double edge_splice_fraction_;
165};
166
167class S2PolygonBuilder {
168 public:
169 explicit S2PolygonBuilder(S2PolygonBuilderOptions const& options);
170 ~S2PolygonBuilder();
171
172 S2PolygonBuilderOptions const& options() const { return options_; }
173
174 // Add the given edge to the polygon builder. This method should be used
175 // for input data that may not follow S2 polygon conventions. Note that
176 // edges are not allowed to cross each other. Also note that as a
177 // convenience, edges where v0 == v1 are ignored.
178 //
179 // Returns true if an edge was added, and false if an edge was erased
180 // (due to XORing) or not added (if both endpoints were the same).
181 bool AddEdge(S2Point const& v0, S2Point const& v1);
182
183 // Add all edges in the given loop. If the sign() of the loop is negative
184 // (i.e. this loop represents a hole), the reverse edges are added instead.
185 // This implies that "shells" are CCW and "holes" are CW, as required for
186 // the directed edges convention described above.
187 //
188 // This method does not take ownership of the loop.
189 void AddLoop(S2Loop const* loop);
190
191 // Add all loops in the given polygon. Shells and holes are added with
192 // opposite orientations as described for AddLoop().
193 //
194 // This method does not take ownership of the polygon.
195 void AddPolygon(S2Polygon const* polygon);
196
197 // This type is used to return any edges that could not be assembled.
198 typedef vector<pair<S2Point, S2Point> > EdgeList;
199
200 // Assembles the given edges into as many non-crossing loops as possible.
201 // When there is a choice about how to assemble the loops, then CCW loops
202 // are preferred. Returns true if all edges were assembled. If
203 // "unused_edges" is not NULL, it is initialized to the set of edges that
204 // could not be assembled into loops.
205 //
206 // Note that if xor_edges() is false and duplicate edge pairs may be
207 // present, then undirected_edges() should be specified unless all loops can
208 // be assembled in a counter-clockwise direction. Otherwise this method may
209 // not be able to assemble all loops due to its preference for CCW loops.
210 //
211 // This method resets the S2PolygonBuilder state so that it can be reused.
212 bool AssembleLoops(vector<S2Loop*>* loops, EdgeList* unused_edges);
213
214 // Like AssembleLoops, but normalizes all the loops so that they enclose
215 // less than half the sphere, and then assembles the loops into a polygon.
216 //
217 // For this method to succeed, there should be no duplicate edges in the
218 // input. If this is not known to be true, then the "xor_edges" option
219 // should be set (which is true by default).
220 //
221 // Note that S2Polygons cannot represent arbitrary regions on the sphere,
222 // because of the limitation that no loop encloses more than half of the
223 // sphere. For example, an S2Polygon cannot represent a 100km wide band
224 // around the equator. In such cases, this method will return the
225 // *complement* of the expected region. So for example if all the world's
226 // coastlines were assembled, the output S2Polygon would represent the land
227 // area (irrespective of the input edge or loop orientations).
228 bool AssemblePolygon(S2Polygon* polygon, EdgeList* unused_edges);
229
230 // This function is only for debugging. If it is called, then points will
231 // be transformed by the inverse of the given matrix before being printed as
232 // lat-lng coordinates in degrees. "m" should be orthonormal.
233 void set_debug_matrix(Matrix3x3_d const& m);
234
235 protected:
236 // These functions print either a single vertex, all edges from a single
237 // vertex, or all edges in the builder.
238 void DumpVertex(S2Point const& v) const;
239 void DumpEdges(S2Point const& v0) const;
240 void Dump() const;
241
242 private:
243
244 // Return true if the given edge exists.
245 bool HasEdge(S2Point const& v0, S2Point const& v1);
246
247 // Erase an edge or an entire loop. The edge/loop must exist.
248 void EraseEdge(S2Point const& v0, S2Point const& v1);
249 void EraseLoop(S2Point const* v, int n);
250
251 // Assembles and returns a single loop starting with the given edge.
252 // If a loop cannot be assembled starting from this edge, returns NULL
253 // and updates "unused_edges".
254 S2Loop* AssembleLoop(S2Point const& v0, S2Point const& v1,
255 EdgeList* unused_edges);
256
257 // Adds all the given edges to "unused_edges".
258 void RejectLoop(S2Point const* v, int n, EdgeList* unused_edges);
259
260 // Builds a map indicating which vertices need to be moved from their
261 // current position to a new position, and also returns a spatial index
262 // containing all of the vertices that do not need to be moved.
263 class PointIndex;
264 typedef hash_map<S2Point, S2Point> MergeMap;
265 void BuildMergeMap(PointIndex* index, MergeMap* merge_map);
266
267 // Moves a set of vertices from old to new positions.
268 void MoveVertices(MergeMap const& merge_map);
269
270 // Modifies each edge by splicing in any vertices whose distance to the edge
271 // is at most (edge_splice_fraction() * vertex_merge_radius()).
272 void SpliceEdges(PointIndex* index);
273
274 S2PolygonBuilderOptions options_;
275
276 // This is only used for debugging purposes.
277 scoped_ptr<Matrix3x3_d> debug_matrix_;
278
279 // The current set of edges, grouped by origin. The set of destination
280 // vertices is a multiset so that the same edge can be present more than
281 // once. We could have also used a multiset<pair<S2Point, S2Point> >,
282 // but this representation is a bit more convenient.
283 typedef multiset<S2Point> VertexSet;
284 typedef hash_map<S2Point, VertexSet> EdgeSet;
285 scoped_ptr<EdgeSet> edges_;
286
287 // Unique collection of the starting (first) vertex of all edges,
288 // in the order they are added to edges_.
289 vector<S2Point> starting_vertices_;
290};
291
292inline S2PolygonBuilderOptions S2PolygonBuilderOptions::DIRECTED_XOR() {
293 return S2PolygonBuilderOptions();
294}
295
296inline S2PolygonBuilderOptions S2PolygonBuilderOptions::UNDIRECTED_XOR() {
297 S2PolygonBuilderOptions options;
298 options.set_undirected_edges(true);
299 return options;
300}
301
302inline S2PolygonBuilderOptions S2PolygonBuilderOptions::UNDIRECTED_UNION() {
303 S2PolygonBuilderOptions options;
304 options.set_undirected_edges(true);
305 options.set_xor_edges(false);
306 return options;
307}
308
309#endif // UTIL_GEOMETRY_S2POLYGONBUILDER_H__
310