1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S1INTERVAL_H_
4#define UTIL_GEOMETRY_S1INTERVAL_H_
5
6#include <iostream>
7using std::ostream;
8using std::cout;
9using std::endl;
10
11#include <math.h>
12#include "base/basictypes.h"
13#include "base/logging.h"
14#include "util/math/vector2-inl.h"
15
16// An S1Interval represents a closed interval on a unit circle (also known
17// as a 1-dimensional sphere). It is capable of representing the empty
18// interval (containing no points), the full interval (containing all
19// points), and zero-length intervals (containing a single point).
20//
21// Points are represented by the angle they make with the positive x-axis in
22// the range [-Pi, Pi]. An interval is represented by its lower and upper
23// bounds (both inclusive, since the interval is closed). The lower bound may
24// be greater than the upper bound, in which case the interval is "inverted"
25// (i.e. it passes through the point (-1, 0)).
26//
27// Note that the point (-1, 0) has two valid representations, Pi and -Pi.
28// The normalized representation of this point internally is Pi, so that
29// endpoints of normal intervals are in the range (-Pi, Pi]. However, we
30// take advantage of the point -Pi to construct two special intervals:
31// the Full() interval is [-Pi, Pi], and the Empty() interval is [Pi, -Pi].
32//
33// This class is intended to be copied by value as desired. It uses
34// the default copy constructor and assignment operator.
35class S1Interval {
36 public:
37 // Constructor. Both endpoints must be in the range -Pi to Pi inclusive.
38 // The value -Pi is converted internally to Pi except for the Full()
39 // and Empty() intervals.
40 inline S1Interval(double lo, double hi);
41
42 // The default constructor creates an empty interval.
43 //
44 // Note: Don't construct an interval using the default constructor and
45 // set_lo()/set_hi(). If you need to set both endpoints, use the
46 // constructor above:
47 //
48 // lng_bounds_ = S1Interval(lng_lo, lng_hi);
49 inline S1Interval();
50
51 // Returns the empty interval.
52 static inline S1Interval Empty();
53
54 // Returns the full interval.
55 static inline S1Interval Full();
56
57 // Convenience method to construct an interval containing a single point.
58 static S1Interval FromPoint(double p);
59
60 // Convenience method to construct the minimal interval containing
61 // the two given points. This is equivalent to starting with an empty
62 // interval and calling AddPoint() twice, but it is more efficient.
63 static S1Interval FromPointPair(double p1, double p2);
64
65 double lo() const { return bounds_[0]; }
66 double hi() const { return bounds_[1]; }
67 double bound(int i) const { return bounds_[i]; }
68 Vector2_d const& bounds() const { return bounds_; }
69
70 // Methods to modify one endpoint of an existing S1Interval. Requires that
71 // the resulting S1Interval is valid. This implies you cannot call this
72 // method on an Empty() or Full() interval, since these intervals do not
73 // have any endpoints.
74 //
75 // Do not use these methods if you want to replace both endpoints of the
76 // interval; use a constructor instead. For example:
77 //
78 // *lng_bounds = S1Interval(lng_lo, lng_hi);
79 void set_lo(double p) { bounds_[0] = p; DCHECK(is_valid()); }
80 void set_hi(double p) { bounds_[1] = p; DCHECK(is_valid()); }
81
82 // An interval is valid if neither bound exceeds Pi in absolute value,
83 // and the value -Pi appears only in the Empty() and Full() intervals.
84 inline bool is_valid() const;
85
86 // Return true if the interval contains all points on the unit circle.
87 bool is_full() const { return hi() - lo() == 2 * M_PI; }
88
89 // Return true if the interval is empty, i.e. it contains no points.
90 bool is_empty() const { return lo() - hi() == 2 * M_PI; }
91
92 // Return true if lo() > hi(). (This is true for empty intervals.)
93 bool is_inverted() const { return lo() > hi(); }
94
95 // Return the midpoint of the interval. For full and empty intervals,
96 // the result is arbitrary.
97 double GetCenter() const;
98
99 // Return the length of the interval. The length of an empty interval
100 // is negative.
101 double GetLength() const;
102
103 // Return the complement of the interior of the interval. An interval and
104 // its complement have the same boundary but do not share any interior
105 // values. The complement operator is not a bijection, since the complement
106 // of a singleton interval (containing a single value) is the same as the
107 // complement of an empty interval.
108 S1Interval Complement() const;
109
110 // Return the midpoint of the complement of the interval. For full and empty
111 // intervals, the result is arbitrary. For a singleton interval (containing a
112 // single point), the result is its antipodal point on S1.
113 double GetComplementCenter() const;
114
115 // Return true if the interval (which is closed) contains the point 'p'.
116 bool Contains(double p) const;
117
118 // Return true if the interior of the interval contains the point 'p'.
119 bool InteriorContains(double p) const;
120
121 // Return true if the interval contains the given interval 'y'.
122 // Works for empty, full, and singleton intervals.
123 bool Contains(S1Interval const& y) const;
124
125 // Returns true if the interior of this interval contains the entire
126 // interval 'y'. Note that x.InteriorContains(x) is true only when
127 // x is the empty or full interval, and x.InteriorContains(S1Interval(p,p))
128 // is equivalent to x.InteriorContains(p).
129 bool InteriorContains(S1Interval const& y) const;
130
131 // Return true if the two intervals contain any points in common.
132 // Note that the point +/-Pi has two representations, so the intervals
133 // [-Pi,-3] and [2,Pi] intersect, for example.
134 bool Intersects(S1Interval const& y) const;
135
136 // Return true if the interior of this interval contains any point of the
137 // interval 'y' (including its boundary). Works for empty, full, and
138 // singleton intervals.
139 bool InteriorIntersects(S1Interval const& y) const;
140
141 // Return the Hausdorff distance to the given interval 'y'. For two
142 // S1Intervals x and y, this distance is defined by
143 // h(x, y) = max_{p in x} min_{q in y} d(p, q),
144 // where d(.,.) is measured along S1.
145 double GetDirectedHausdorffDistance(S1Interval const& y) const;
146
147 // Expand the interval by the minimum amount necessary so that it
148 // contains the given point "p" (an angle in the range [-Pi, Pi]).
149 void AddPoint(double p);
150
151 // Return an interval that contains all points with a distance "radius" of a
152 // point in this interval. Note that the expansion of an empty interval is
153 // always empty. The radius must be non-negative.
154 S1Interval Expanded(double radius) const;
155
156 // Return the smallest interval that contains this interval and the
157 // given interval "y".
158 S1Interval Union(S1Interval const& y) const;
159
160 // Return the smallest interval that contains the intersection of this
161 // interval with "y". Note that the region of intersection may
162 // consist of two disjoint intervals.
163 S1Interval Intersection(S1Interval const& y) const;
164
165 // Return true if two intervals contains the same set of points.
166 inline bool operator==(S1Interval const& y) const;
167
168 // Return true if the length of the symmetric difference between the two
169 // intervals is at most the given tolerance.
170 bool ApproxEquals(S1Interval const& y, double max_error = 1e-15) const;
171
172 private:
173 enum ArgsChecked { ARGS_CHECKED };
174
175 // Internal constructor that assumes that both arguments are in the
176 // correct range, i.e. normalization from -Pi to Pi is already done.
177 inline S1Interval(double lo, double hi, ArgsChecked dummy);
178
179 // Return true if the interval (which is closed) contains the point 'p'.
180 // Skips the normalization of 'p' from -Pi to Pi.
181 bool FastContains(double p) const;
182
183 Vector2_d bounds_;
184};
185DECLARE_POD(S1Interval);
186
187inline S1Interval::S1Interval(double lo, double hi) : bounds_(lo, hi) {
188 if (lo == -M_PI && hi != M_PI) set_lo(M_PI);
189 if (hi == -M_PI && lo != M_PI) set_hi(M_PI);
190 DCHECK(is_valid());
191}
192
193inline S1Interval::S1Interval(double lo, double hi, ArgsChecked dummy)
194 : bounds_(lo, hi) {
195 DCHECK(is_valid());
196}
197
198inline S1Interval::S1Interval() : bounds_(M_PI, -M_PI) {
199}
200
201inline S1Interval S1Interval::Empty() {
202 return S1Interval();
203}
204
205inline S1Interval S1Interval::Full() {
206 return S1Interval(-M_PI, M_PI, ARGS_CHECKED);
207}
208
209inline bool S1Interval::is_valid() const {
210 return (fabs(lo()) <= M_PI && fabs(hi()) <= M_PI &&
211 !(lo() == -M_PI && hi() != M_PI) &&
212 !(hi() == -M_PI && lo() != M_PI));
213}
214
215inline bool S1Interval::operator==(S1Interval const& y) const {
216 return lo() == y.lo() && hi() == y.hi();
217}
218
219inline ostream& operator<<(ostream& os, S1Interval const& x) {
220 return os << "[" << x.lo() << ", " << x.hi() << "]";
221}
222
223#endif // UTIL_GEOMETRY_S1INTERVAL_H_
224