1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2POLYGON_H_
4#define UTIL_GEOMETRY_S2POLYGON_H_
5
6#include <map>
7using std::map;
8using std::multimap;
9
10#include <vector>
11using std::vector;
12
13
14#include "base/basictypes.h"
15#include "base/macros.h"
16#include "s2.h"
17#include "s2region.h"
18#include "s2loop.h"
19#include "s2polyline.h"
20
21class S2CellUnion;
22
23// An S2Polygon is an S2Region object that represents a polygon. A polygon
24// consists of zero or more loops representing "shells" and "holes". All
25// loops should be oriented CCW, i.e. the shell or hole is on the left side of
26// the loop. Loops may be specified in any order. A point is defined to be
27// inside the polygon if it is contained by an odd number of loops.
28//
29// Polygons have the following restrictions:
30//
31// - Loops may not cross, i.e. the boundary of a loop may not intersect
32// both the interior and exterior of any other loop.
33//
34// - Loops may not share edges, i.e. if a loop contains an edge AB, then
35// no other loop may contain AB or BA.
36//
37// - No loop may cover more than half the area of the sphere. This ensures
38// that no loop properly contains the complement of any other loop, even
39// if the loops are from different polygons. (Loops that represent exact
40// hemispheres are allowed.)
41//
42// Loops may share vertices, however no vertex may appear twice in a single
43// loop (see s2loop.h).
44class S2Polygon : public S2Region {
45 public:
46 // Creates an empty polygon that should be initialized by calling Init() or
47 // Decode().
48 S2Polygon();
49
50 // Convenience constructor that calls Init() with the given loops. Takes
51 // ownership of the loops and clears the given vector.
52 explicit S2Polygon(vector<S2Loop*>* loops);
53
54 // Convenience constructor that creates a polygon with a single loop
55 // corresponding to the given cell.
56 explicit S2Polygon(S2Cell const& cell);
57
58 // Initialize a polygon by taking ownership of the given loops and clearing
59 // the given vector. This method figures out the loop nesting hierarchy and
60 // then reorders the loops by following a preorder traversal. This implies
61 // that each loop is immediately followed by its descendants in the nesting
62 // hierarchy. (See also GetParent and GetLastDescendant.)
63 void Init(vector<S2Loop*>* loops);
64
65 // Release ownership of the loops of this polygon, and appends them to
66 // "loops" if non-NULL. Resets the polygon to be empty.
67 void Release(vector<S2Loop*>* loops);
68
69 // Makes a deep copy of the given source polygon. Requires that the
70 // destination polygon is empty.
71 void Copy(S2Polygon const* src);
72
73 // Destroys the polygon and frees its loops.
74 ~S2Polygon();
75
76 // Return true if the given loops form a valid polygon. Assumes that
77 // all of the given loops have already been validated.
78 static bool IsValid(const vector<S2Loop*>& loops);
79
80 // Return true if this is a valid polygon. Note that in debug mode,
81 // validity is checked at polygon creation time, so IsValid() should always
82 // return true.
83 bool IsValid() const;
84
85 // DEPRECATED.
86 bool IsValid(bool check_loops, int max_adjacent) const;
87
88 int num_loops() const { return loops_.size(); }
89
90 // Total number of vertices in all loops.
91 int num_vertices() const { return num_vertices_; }
92
93 S2Loop* loop(int k) const { return loops_[k]; }
94
95 // Return the index of the parent of loop k, or -1 if it has no parent.
96 int GetParent(int k) const;
97
98 // Return the index of the last loop that is contained within loop k.
99 // Returns num_loops() - 1 if k < 0. Note that loops are indexed according
100 // to a preorder traversal of the nesting hierarchy, so the immediate
101 // children of loop k can be found by iterating over loops
102 // (k+1)..GetLastDescendant(k) and selecting those whose depth is equal to
103 // (loop(k)->depth() + 1).
104 int GetLastDescendant(int k) const;
105
106 // Return the area of the polygon interior, i.e. the region on the left side
107 // of an odd number of loops. The return value is between 0 and 4*Pi.
108 double GetArea() const;
109
110 // Return the true centroid of the polygon multiplied by the area of the
111 // polygon (see s2.h for details on centroids). The result is not unit
112 // length, so you may want to normalize it. Also note that in general, the
113 // centroid may not be contained by the polygon.
114 //
115 // We prescale by the polygon area for two reasons: (1) it is cheaper to
116 // compute this way, and (2) it makes it easier to compute the centroid of
117 // more complicated shapes (by splitting them into disjoint regions and
118 // adding their centroids).
119 S2Point GetCentroid() const;
120
121 // Return true if this polygon contains the given other polygon, i.e.
122 // if polygon A contains all points contained by polygon B.
123 bool Contains(S2Polygon const* b) const;
124
125 // Returns true if this polgyon (A) approximately contains the given other
126 // polygon (B). This is true if it is possible to move the vertices of B
127 // no further than "vertex_merge_radius" such that A contains the modified B.
128 //
129 // For example, the empty polygon will contain any polygon whose maximum
130 // width is no more than vertex_merge_radius.
131 bool ApproxContains(S2Polygon const* b, S1Angle vertex_merge_radius) const;
132
133 // Return true if this polygon intersects the given other polygon, i.e.
134 // if there is a point that is contained by both polygons.
135 bool Intersects(S2Polygon const* b) const;
136
137 // Initialize this polygon to the intersection, union, or difference
138 // (A - B) of the given two polygons. The "vertex_merge_radius" determines
139 // how close two vertices must be to be merged together and how close a
140 // vertex must be to an edge in order to be spliced into it (see
141 // S2PolygonBuilder for details). By default, the merge radius is just
142 // large enough to compensate for errors that occur when computing
143 // intersection points between edges (S2EdgeUtil::kIntersectionTolerance).
144 //
145 // If you are going to convert the resulting polygon to a lower-precision
146 // format, it is necessary to increase the merge radius in order to get a
147 // valid result after rounding (i.e. no duplicate vertices, etc). For
148 // example, if you are going to convert them to geostore::PolygonProto
149 // format, then S1Angle::E7(1) is a good value for "vertex_merge_radius".
150 void InitToIntersection(S2Polygon const* a, S2Polygon const* b);
151 void InitToIntersectionSloppy(S2Polygon const* a, S2Polygon const* b,
152 S1Angle vertex_merge_radius);
153 void InitToUnion(S2Polygon const* a, S2Polygon const* b);
154 void InitToUnionSloppy(S2Polygon const* a, S2Polygon const* b,
155 S1Angle vertex_merge_radius);
156 void InitToDifference(S2Polygon const* a, S2Polygon const* b);
157 void InitToDifferenceSloppy(S2Polygon const* a, S2Polygon const* b,
158 S1Angle vertex_merge_radius);
159
160 // Initializes this polygon to a polygon that contains fewer vertices and is
161 // within tolerance of the polygon a, with some caveats.
162 //
163 // - If there is a very small island in the original polygon, it may
164 // disappear completely. Thus some parts of the original polygon
165 // may not be close to the simplified polygon. Those parts are small,
166 // though, and arguably don't need to be kept.
167 // - However, if there are dense islands, they may all disappear, instead
168 // of replacing them by a big simplified island.
169 // - For small tolerances (compared to the polygon size), it may happen that
170 // the simplified polygon has more vertices than the original, if the
171 // first step of the simplification creates too many self-intersections.
172 // One can construct irrealistic cases where that happens to an extreme
173 // degree.
174 void InitToSimplified(S2Polygon const* a, S1Angle tolerance);
175
176 // Intersect this polygon with the polyline "in" and append the resulting
177 // zero or more polylines to "out" (which must be empty). The polylines
178 // are appended in the order they would be encountered by traversing "in"
179 // from beginning to end. Note that the output may include polylines with
180 // only one vertex, but there will not be any zero-vertex polylines.
181 //
182 // This is equivalent to calling IntersectWithPolylineSloppy() with the
183 // "vertex_merge_radius" set to S2EdgeUtil::kIntersectionTolerance.
184 void IntersectWithPolyline(S2Polyline const* in,
185 vector<S2Polyline*> *out) const;
186
187 // Similar to IntersectWithPolyline(), except that vertices will be
188 // dropped as necessary to ensure that all adjacent vertices in the
189 // sequence obtained by concatenating the output polylines will be
190 // farther than "vertex_merge_radius" apart. Note that this can change
191 // the number of output polylines and/or yield single-vertex polylines.
192 void IntersectWithPolylineSloppy(S2Polyline const* in,
193 vector<S2Polyline*> *out,
194 S1Angle vertex_merge_radius) const;
195
196 // Same as IntersectWithPolyline, but subtracts this polygon from
197 // the given polyline.
198 void SubtractFromPolyline(S2Polyline const* in,
199 vector<S2Polyline*> *out) const;
200
201 // Same as IntersectWithPolylineSloppy, but subtracts this polygon
202 // from the given polyline.
203 void SubtractFromPolylineSloppy(S2Polyline const* in,
204 vector<S2Polyline*> *out,
205 S1Angle vertex_merge_radius) const;
206
207 // Return a polygon which is the union of the given polygons.
208 // Clears the vector and deletes the polygons!
209 static S2Polygon* DestructiveUnion(vector<S2Polygon*>* polygons);
210 static S2Polygon* DestructiveUnionSloppy(vector<S2Polygon*>* polygons,
211 S1Angle vertex_merge_radius);
212
213 // Initialize this polygon to the outline of the given cell union.
214 // In principle this polygon should exactly contain the cell union and
215 // this polygon's inverse should not intersect the cell union, but rounding
216 // issues may cause this not to be the case.
217 // Does not work correctly if the union covers more than half the sphere.
218 void InitToCellUnionBorder(S2CellUnion const& cells);
219
220 // Return true if every loop of this polygon shares at most one vertex with
221 // its parent loop. Every polygon has a unique normalized form. Normalized
222 // polygons are useful for testing since it is easy to compare whether two
223 // polygons represent the same region.
224 bool IsNormalized() const;
225
226 // Return true if two polygons have the same boundary. More precisely, this
227 // method requires that both polygons have loops with the same cyclic vertex
228 // order and the same nesting hierarchy.
229 bool BoundaryEquals(S2Polygon const* b) const;
230
231 // Return true if two polygons have the same boundary except for vertex
232 // perturbations. Both polygons must have loops with the same cyclic vertex
233 // order and the same nesting hierarchy, but the vertex locations are
234 // allowed to differ by up to "max_error".
235 bool BoundaryApproxEquals(S2Polygon const* b, double max_error = 1e-15) const;
236
237 // Return true if two polygons have boundaries that are within "max_error"
238 // of each other along their entire lengths. More precisely, there must be
239 // a bijection between the two sets of loops such that for each pair of
240 // loops, "a_loop->BoundaryNear(b_loop)" is true.
241 bool BoundaryNear(S2Polygon const* b, double max_error = 1e-15) const;
242
243 // If the point is not contained by the polygon returns a point on the
244 // polygon closest to the given point. Otherwise returns the point itself.
245 // The polygon must not be empty.
246 S2Point Project(S2Point const& point) const;
247
248 ////////////////////////////////////////////////////////////////////////
249 // S2Region interface (see s2region.h for details):
250
251 // GetRectBound() guarantees that it will return exact bounds. GetCapBound()
252 // does not.
253 virtual S2Polygon* Clone() const;
254 virtual S2Cap GetCapBound() const; // Cap surrounding rect bound.
255 virtual S2LatLngRect GetRectBound() const { return bound_; }
256
257 virtual bool Contains(S2Cell const& cell) const;
258 virtual bool MayIntersect(S2Cell const& cell) const;
259 virtual bool VirtualContainsPoint(S2Point const& p) const;
260
261 // The point 'p' does not need to be normalized.
262 bool Contains(S2Point const& p) const;
263
264 virtual void Encode(Encoder* const encoder) const;
265 virtual bool Decode(Decoder* const decoder);
266 virtual bool DecodeWithinScope(Decoder* const decoder);
267
268 private:
269 // Internal constructor that does *not* take ownership of its argument.
270 explicit S2Polygon(S2Loop* loop);
271
272 // A map from each loop to its immediate children with respect to nesting.
273 // This map is built during initialization of multi-loop polygons to
274 // determine which are shells and which are holes, and then discarded.
275 typedef map<S2Loop*, vector<S2Loop*> > LoopMap;
276
277 // Internal implementation of the Decode and DecodeWithinScope methods above.
278 // The within_scope parameter specifies whether to call DecodeWithinScope
279 // on the loops.
280 bool DecodeInternal(Decoder* const decoder, bool within_scope);
281
282 // Internal implementation of intersect/subtract polyline functions above.
283 void InternalClipPolyline(bool invert,
284 S2Polyline const* a,
285 vector<S2Polyline*> *out,
286 S1Angle vertex_merge_radius) const;
287
288 static void InsertLoop(S2Loop* new_loop, S2Loop* parent, LoopMap* loop_map);
289 static bool ContainsChild(S2Loop* a, S2Loop* b, LoopMap const& loop_map);
290 void InitLoop(S2Loop* loop, int depth, LoopMap* loop_map);
291
292 int ContainsOrCrosses(S2Loop const* b) const;
293 bool AnyLoopContains(S2Loop const* b) const;
294 bool ContainsAllShells(S2Polygon const* b) const;
295 bool ExcludesAllHoles(S2Polygon const* b) const;
296 bool IntersectsAnyShell(S2Polygon const* b) const;
297 bool IntersectsShell(S2Loop const* b) const;
298
299 vector<S2Loop*> loops_;
300 S2LatLngRect bound_;
301 char owns_loops_;
302 char has_holes_;
303
304 // Cache for num_vertices().
305 int num_vertices_;
306
307 DISALLOW_EVIL_CONSTRUCTORS(S2Polygon);
308};
309
310#endif // UTIL_GEOMETRY_S2POLYGON_H_
311