1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2POLYLINE_H__
4#define UTIL_GEOMETRY_S2POLYLINE_H__
5
6#include <vector>
7using std::vector;
8
9#include "base/logging.h"
10#include "base/macros.h"
11#include "s2.h"
12#include "s2region.h"
13#include "s2latlngrect.h"
14
15class S1Angle;
16
17// An S2Polyline represents a sequence of zero or more vertices connected by
18// straight edges (geodesics). Edges of length 0 and 180 degrees are not
19// allowed, i.e. adjacent vertices should not be identical or antipodal.
20class S2Polyline : public S2Region {
21 public:
22 // Creates an empty S2Polyline that should be initialized by calling Init()
23 // or Decode().
24 S2Polyline();
25
26 // Convenience constructors that call Init() with the given vertices.
27 S2Polyline(vector<S2Point> const& vertices);
28 S2Polyline(vector<S2LatLng> const& vertices);
29
30 // Initialize a polyline that connects the given vertices. Empty polylines are
31 // allowed. Adjacent vertices should not be identical or antipodal. All
32 // vertices should be unit length.
33 void Init(vector<S2Point> const& vertices);
34
35 // Convenience initialization function that accepts latitude-longitude
36 // coordinates rather than S2Points.
37 void Init(vector<S2LatLng> const& vertices);
38
39 ~S2Polyline();
40
41 // Return true if the given vertices form a valid polyline.
42 static bool IsValid(vector<S2Point> const& vertices);
43
44 int num_vertices() const { return num_vertices_; }
45 S2Point const& vertex(int k) const {
46 DCHECK_GE(k, 0);
47 DCHECK_LT(k, num_vertices_);
48 return vertices_[k];
49 }
50
51 // Return the length of the polyline.
52 S1Angle GetLength() const;
53
54 // Return the true centroid of the polyline multiplied by the length of the
55 // polyline (see s2.h for details on centroids). The result is not unit
56 // length, so you may want to normalize it.
57 //
58 // Prescaling by the polyline length makes it easy to compute the centroid
59 // of several polylines (by simply adding up their centroids).
60 S2Point GetCentroid() const;
61
62 // Return the point whose distance from vertex 0 along the polyline is the
63 // given fraction of the polyline's total length. Fractions less than zero
64 // or greater than one are clamped. The return value is unit length. This
65 // cost of this function is currently linear in the number of vertices.
66 // The polyline must not be empty.
67 S2Point Interpolate(double fraction) const;
68
69 // Like Interpolate(), but also return the index of the next polyline
70 // vertex after the interpolated point P. This allows the caller to easily
71 // construct a given suffix of the polyline by concatenating P with the
72 // polyline vertices starting at "next_vertex". Note that P is guaranteed
73 // to be different than vertex(*next_vertex), so this will never result in
74 // a duplicate vertex.
75 //
76 // The polyline must not be empty. Note that if "fraction" >= 1.0, then
77 // "next_vertex" will be set to num_vertices() (indicating that no vertices
78 // from the polyline need to be appended). The value of "next_vertex" is
79 // always between 1 and num_vertices().
80 //
81 // This method can also be used to construct a prefix of the polyline, by
82 // taking the polyline vertices up to "next_vertex - 1" and appending the
83 // returned point P if it is different from the last vertex (since in this
84 // case there is no guarantee of distinctness).
85 S2Point GetSuffix(double fraction, int* next_vertex) const;
86
87 // The inverse operation of GetSuffix/Interpolate. Given a point on the
88 // polyline, returns the ratio of the distance to the point from the
89 // beginning of the polyline over the length of the polyline. The return
90 // value is always betwen 0 and 1 inclusive. See GetSuffix() for the
91 // meaning of "next_vertex".
92 //
93 // The polyline should not be empty. If it has fewer than 2 vertices, the
94 // return value is zero.
95 double UnInterpolate(S2Point const& point, int next_vertex) const;
96
97 // Given a point, returns a point on the polyline that is closest to the given
98 // point. See GetSuffix() for the meaning of "next_vertex", which is chosen
99 // here w.r.t. the projected point as opposed to the interpolated point in
100 // GetSuffix().
101 //
102 // The polyline must be non-empty.
103 S2Point Project(S2Point const& point, int* next_vertex) const;
104
105 // Returns true if the point given is on the right hand side of the polyline,
106 // using a naive definition of "right-hand-sideness" where the point is on
107 // the RHS of the polyline iff the point is on the RHS of the line segment in
108 // the polyline which it is closest to.
109 //
110 // The polyline must have at least 2 vertices.
111 bool IsOnRight(S2Point const& point) const;
112
113 // Return true if this polyline intersects the given polyline. If the
114 // polylines share a vertex they are considered to be intersecting. When a
115 // polyline endpoint is the only intersection with the other polyline, the
116 // function may return true or false arbitrarily.
117 //
118 // The running time is quadratic in the number of vertices.
119 bool Intersects(S2Polyline const* line) const;
120
121 // Reverse the order of the polyline vertices.
122 void Reverse();
123
124 // Return a subsequence of vertex indices such that the polyline connecting
125 // these vertices is never further than "tolerance" from the original
126 // polyline. The first and last vertices are always preserved.
127 //
128 // Some useful properties of the algorithm:
129 //
130 // - It runs in linear time.
131 //
132 // - The output is always a valid polyline. In particular, adjacent
133 // output vertices are never identical or antipodal.
134 //
135 // - The method is not optimal, but it tends to produce 2-3% fewer
136 // vertices than the Douglas-Peucker algorithm with the same tolerance.
137 //
138 // - The output is *parametrically* equivalent to the original polyline to
139 // within the given tolerance. For example, if a polyline backtracks on
140 // itself and then proceeds onwards, the backtracking will be preserved
141 // (to within the given tolerance). This is different than the
142 // Douglas-Peucker algorithm used in maps/util/geoutil-inl.h, which only
143 // guarantees geometric equivalence.
144 void SubsampleVertices(S1Angle const& tolerance, vector<int>* indices) const;
145
146 // Return true if two polylines have the same number of vertices, and
147 // corresponding vertex pairs are separated by no more than "max_error".
148 // (For testing purposes.)
149 bool ApproxEquals(S2Polyline const* b, double max_error = 1e-15) const;
150
151 // Return true if "covered" is within "max_error" of a contiguous subpath of
152 // this polyline over its entire length. Specifically, this method returns
153 // true if this polyline has parameterization a:[0,1] -> S^2, "covered" has
154 // parameterization b:[0,1] -> S^2, and there is a non-decreasing function
155 // f:[0,1] -> [0,1] such that distance(a(f(t)), b(t)) <= max_error for all t.
156 //
157 // You can think of this as testing whether it is possible to drive a car
158 // along "covered" and a car along some subpath of this polyline such that no
159 // car ever goes backward, and the cars are always within "max_error" of each
160 // other.
161 bool NearlyCoversPolyline(S2Polyline const& covered,
162 S1Angle const& max_error) const;
163
164 ////////////////////////////////////////////////////////////////////////
165 // S2Region interface (see s2region.h for details):
166
167 virtual S2Polyline* Clone() const;
168 virtual S2Cap GetCapBound() const;
169 virtual S2LatLngRect GetRectBound() const;
170 virtual bool Contains(S2Cell const& cell) const { return false; }
171 virtual bool MayIntersect(S2Cell const& cell) const;
172
173 // Polylines do not have a Contains(S2Point) method, because "containment"
174 // is not numerically well-defined except at the polyline vertices.
175 virtual bool VirtualContainsPoint(S2Point const& p) const { return false; }
176
177 virtual void Encode(Encoder* const encoder) const;
178 virtual bool Decode(Decoder* const decoder);
179
180 private:
181 // Internal constructor used only by Clone() that makes a deep copy of
182 // its argument.
183 S2Polyline(S2Polyline const* src);
184
185 // We store the vertices in an array rather than a vector because we don't
186 // need any STL methods, and computing the number of vertices using size()
187 // would be relatively expensive (due to division by sizeof(S2Point) == 24).
188 int num_vertices_;
189 S2Point* vertices_;
190
191 DISALLOW_EVIL_CONSTRUCTORS(S2Polyline);
192};
193
194#endif // UTIL_GEOMETRY_S2POLYLINE_H__
195