1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_R1INTERVAL_H_
4#define UTIL_GEOMETRY_R1INTERVAL_H_
5
6#include <math.h>
7
8#include <algorithm>
9using std::min;
10using std::max;
11using std::swap;
12using std::reverse;
13
14#include <iostream>
15using std::ostream;
16using std::cout;
17using std::endl;
18
19#include "base/basictypes.h"
20#include "base/logging.h"
21#include "util/math/vector2-inl.h"
22
23// An R1Interval represents a closed, bounded interval on the real line.
24// It is capable of representing the empty interval (containing no points)
25// and zero-length intervals (containing a single point).
26//
27// This class is intended to be copied by value as desired. It uses
28// the default copy constructor and assignment operator.
29class R1Interval {
30 public:
31 // Constructor. If lo > hi, the interval is empty.
32 R1Interval(double lo, double hi) : bounds_(lo, hi) {}
33
34 // The default constructor creates an empty interval. (Any interval where
35 // lo > hi is considered to be empty.)
36 //
37 // Note: Don't construct an interval using the default constructor and
38 // set_lo()/set_hi(), since this technique doesn't work with S1Interval and
39 // is bad programming style anyways. If you need to set both endpoints, use
40 // the constructor above:
41 //
42 // lat_bounds_ = R1Interval(lat_lo, lat_hi);
43 R1Interval() : bounds_(1, 0) {}
44
45 // Returns an empty interval.
46 static inline R1Interval Empty() { return R1Interval(); }
47
48 // Convenience method to construct an interval containing a single point.
49 static R1Interval FromPoint(double p) {
50 return R1Interval(p, p);
51 }
52
53 // Convenience method to construct the minimal interval containing
54 // the two given points. This is equivalent to starting with an empty
55 // interval and calling AddPoint() twice, but it is more efficient.
56 static R1Interval FromPointPair(double p1, double p2) {
57 if (p1 <= p2) {
58 return R1Interval(p1, p2);
59 } else {
60 return R1Interval(p2, p1);
61 }
62 }
63
64 double lo() const { return bounds_[0]; }
65 double hi() const { return bounds_[1]; }
66 double bound(int i) const { return bounds_[i]; }
67 Vector2_d const& bounds() const { return bounds_; }
68
69 // Methods to modify one endpoint of an existing R1Interval. Do not use
70 // these methods if you want to replace both endpoints of the interval; use
71 // a constructor instead. For example:
72 //
73 // *lat_bounds = R1Interval(lat_lo, lat_hi);
74 void set_lo(double p) { bounds_[0] = p; }
75 void set_hi(double p) { bounds_[1] = p; }
76
77 // Return true if the interval is empty, i.e. it contains no points.
78 bool is_empty() const { return lo() > hi(); }
79
80 // Return the center of the interval. For empty intervals,
81 // the result is arbitrary.
82 double GetCenter() const { return 0.5 * (lo() + hi()); }
83
84 // Return the length of the interval. The length of an empty interval
85 // is negative.
86 double GetLength() const { return hi() - lo(); }
87
88 bool Contains(double p) const {
89 return p >= lo() && p <= hi();
90 }
91
92 bool InteriorContains(double p) const {
93 return p > lo() && p < hi();
94 }
95
96 // Return true if this interval contains the interval 'y'.
97 bool Contains(R1Interval const& y) const {
98 if (y.is_empty()) return true;
99 return y.lo() >= lo() && y.hi() <= hi();
100 }
101
102 // Return true if the interior of this interval contains the entire
103 // interval 'y' (including its boundary).
104 bool InteriorContains(R1Interval const& y) const {
105 if (y.is_empty()) return true;
106 return y.lo() > lo() && y.hi() < hi();
107 }
108
109 // Return true if this interval intersects the given interval,
110 // i.e. if they have any points in common.
111 bool Intersects(R1Interval const& y) const {
112 if (lo() <= y.lo()) {
113 return y.lo() <= hi() && y.lo() <= y.hi();
114 } else {
115 return lo() <= y.hi() && lo() <= hi();
116 }
117 }
118
119 // Return true if the interior of this interval intersects
120 // any point of the given interval (including its boundary).
121 bool InteriorIntersects(R1Interval const& y) const {
122 return y.lo() < hi() && lo() < y.hi() && lo() < hi() && y.lo() <= y.hi();
123 }
124
125 // Return the Hausdorff distance to the given interval 'y'. For two
126 // R1Intervals x and y, this distance is defined as
127 // h(x, y) = max_{p in x} min_{q in y} d(p, q).
128 double GetDirectedHausdorffDistance(R1Interval const& y) const {
129 if (is_empty()) return 0.0;
130 if (y.is_empty()) return HUGE_VAL;
131 return max(0.0, max(hi() - y.hi(), y.lo() - lo()));
132 }
133
134 // Expand the interval so that it contains the given point "p".
135 void AddPoint(double p) {
136 if (is_empty()) { set_lo(p); set_hi(p); }
137 else if (p < lo()) { set_lo(p); }
138 else if (p > hi()) { set_hi(p); }
139 }
140
141 // Return an interval that contains all points with a distance "radius" of
142 // a point in this interval. Note that the expansion of an empty interval
143 // is always empty.
144 R1Interval Expanded(double radius) const {
145 DCHECK_GE(radius, 0);
146 if (is_empty()) return *this;
147 return R1Interval(lo() - radius, hi() + radius);
148 }
149
150 // Return the smallest interval that contains this interval and the
151 // given interval "y".
152 R1Interval Union(R1Interval const& y) const {
153 if (is_empty()) return y;
154 if (y.is_empty()) return *this;
155 return R1Interval(min(lo(), y.lo()), max(hi(), y.hi()));
156 }
157
158 // Return the intersection of this interval with the given interval.
159 // Empty intervals do not need to be special-cased.
160 R1Interval Intersection(R1Interval const& y) const {
161 return R1Interval(max(lo(), y.lo()), min(hi(), y.hi()));
162 }
163
164 // Return true if two intervals contain the same set of points.
165 bool operator==(R1Interval const& y) const {
166 return (lo() == y.lo() && hi() == y.hi()) || (is_empty() && y.is_empty());
167 }
168
169 // Return true if length of the symmetric difference between the two
170 // intervals is at most the given tolerance.
171 bool ApproxEquals(R1Interval const& y, double max_error = 1e-15) const {
172 if (is_empty()) return y.GetLength() <= max_error;
173 if (y.is_empty()) return GetLength() <= max_error;
174 return fabs(y.lo() - lo()) + fabs(y.hi() - hi()) <= max_error;
175 }
176
177 private:
178 Vector2_d bounds_;
179};
180DECLARE_POD(R1Interval);
181
182inline ostream& operator<<(ostream& os, R1Interval const& x) {
183 return os << "[" << x.lo() << ", " << x.hi() << "]";
184}
185
186#endif // UTIL_GEOMETRY_R1INTERVAL_H_
187