1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2CAP_H_
4#define UTIL_GEOMETRY_S2CAP_H_
5
6#include "base/basictypes.h"
7#include "base/logging.h"
8#include "s1angle.h"
9#include "s2region.h"
10
11// This class represents a spherical cap, i.e. a portion of a sphere cut off
12// by a plane. The cap is defined by its axis and height. This
13// representation has good numerical accuracy for very small caps (unlike the
14// (axis, min-distance-from-origin) representation), and is also efficient for
15// containment tests (unlike the (axis, angle) representation).
16//
17// Here are some useful relationships between the cap height (h), the cap
18// opening angle (theta), the maximum chord length from the cap's center (d),
19// and the radius of cap's base (a). All formulas assume a unit radius.
20//
21// h = 1 - cos(theta)
22// = 2 sin^2(theta/2)
23// d^2 = 2 h
24// = a^2 + h^2
25//
26// Caps may be constructed from either an axis and a height, or an axis and
27// an angle. To avoid ambiguity, there are no public constructors except
28// the default constructor.
29//
30// This class is intended to be copied by value as desired. It uses
31// the default copy constructor and assignment operator, however it is
32// not a "plain old datatype" (POD) because it has virtual functions.
33class S2Cap : public S2Region {
34 public:
35 // The default constructor returns an empty S2Cap.
36 S2Cap() : axis_(1, 0, 0), height_(-1) {}
37
38 // Create a cap given its axis and the cap height, i.e. the maximum
39 // projected distance along the cap axis from the cap center.
40 // 'axis' should be a unit-length vector.
41 inline static S2Cap FromAxisHeight(S2Point const& axis, double height);
42
43 // Create a cap given its axis and the cap opening angle, i.e. maximum
44 // angle between the axis and a point on the cap. 'axis' should be a
45 // unit-length vector, and 'angle' should be non-negative. If 'angle' is
46 // 180 degrees or larger, the cap will contain the entire unit sphere.
47 static S2Cap FromAxisAngle(S2Point const& axis, S1Angle const& angle);
48
49 // Create a cap given its axis and its area in steradians. 'axis' should be
50 // a unit-length vector, and 'area' should be between 0 and 4 * M_PI.
51 inline static S2Cap FromAxisArea(S2Point const& axis, double area);
52
53 // Return an empty cap, i.e. a cap that contains no points.
54 static S2Cap Empty() { return S2Cap(); }
55
56 // Return a full cap, i.e. a cap that contains all points.
57 static S2Cap Full() { return S2Cap(S2Point(1, 0, 0), 2); }
58
59 ~S2Cap() {}
60
61 // Accessor methods.
62 S2Point const& axis() const { return axis_; }
63 double height() const { return height_; }
64 double area() const { return 2 * M_PI * max(0.0, height_); }
65
66 // Return the cap opening angle in radians, or a negative number for
67 // empty caps.
68 S1Angle angle() const;
69
70 // We allow negative heights (to represent empty caps) but not heights
71 // greater than 2.
72 bool is_valid() const { return S2::IsUnitLength(axis_) && height_ <= 2; }
73
74 // Return true if the cap is empty, i.e. it contains no points.
75 bool is_empty() const { return height_ < 0; }
76
77 // Return true if the cap is full, i.e. it contains all points.
78 bool is_full() const { return height_ >= 2; }
79
80 // Return the complement of the interior of the cap. A cap and its
81 // complement have the same boundary but do not share any interior points.
82 // The complement operator is not a bijection, since the complement of a
83 // singleton cap (containing a single point) is the same as the complement
84 // of an empty cap.
85 S2Cap Complement() const;
86
87 // Return true if and only if this cap contains the given other cap
88 // (in a set containment sense, e.g. every cap contains the empty cap).
89 bool Contains(S2Cap const& other) const;
90
91 // Return true if and only if this cap intersects the given other cap,
92 // i.e. whether they have any points in common.
93 bool Intersects(S2Cap const& other) const;
94
95 // Return true if and only if the interior of this cap intersects the
96 // given other cap. (This relationship is not symmetric, since only
97 // the interior of this cap is used.)
98 bool InteriorIntersects(S2Cap const& other) const;
99
100 // Return true if and only if the given point is contained in the interior
101 // of the region (i.e. the region excluding its boundary). 'p' should be
102 // be a unit-length vector.
103 bool InteriorContains(S2Point const& p) const;
104
105 // Increase the cap height if necessary to include the given point.
106 // If the cap is empty the axis is set to the given point, but otherwise
107 // it is left unchanged. 'p' should be a unit-length vector.
108 void AddPoint(S2Point const& p);
109
110 // Increase the cap height if necessary to include "other". If the current
111 // cap is empty it is set to the given other cap.
112 void AddCap(S2Cap const& other);
113
114 // Return a cap that contains all points within a given distance of this
115 // cap. Note that any expansion of the empty cap is still empty.
116 S2Cap Expanded(S1Angle const& distance) const;
117
118 ////////////////////////////////////////////////////////////////////////
119 // S2Region interface (see s2region.h for details):
120
121 virtual S2Cap* Clone() const;
122 virtual S2Cap GetCapBound() const;
123 virtual S2LatLngRect GetRectBound() const;
124 virtual bool Contains(S2Cell const& cell) const;
125 virtual bool MayIntersect(S2Cell const& cell) const;
126 virtual bool VirtualContainsPoint(S2Point const& p) const {
127 return Contains(p); // The same as Contains() below, just virtual.
128 }
129
130 // The point 'p' should be a unit-length vector.
131 bool Contains(S2Point const& p) const;
132
133 virtual void Encode(Encoder* const encoder) const {
134 LOG(FATAL) << "Unimplemented";
135 }
136 virtual bool Decode(Decoder* const decoder) { return false; }
137
138 ///////////////////////////////////////////////////////////////////////
139 // The following static methods are convenience functions for assertions
140 // and testing purposes only.
141
142 // Return true if two caps are identical.
143 bool operator==(S2Cap const& other) const;
144
145 // Return true if the cap axis and height differ by at most "max_error"
146 // from the given cap "other".
147 bool ApproxEquals(S2Cap const& other, double max_error = 1e-14);
148
149 private:
150 S2Cap(S2Point const& axis, double height)
151 : axis_(axis), height_(height) {
152 DCHECK(is_valid());
153 }
154
155 // Return true if the cap intersects 'cell', given that the cap
156 // vertices have alrady been checked.
157 bool Intersects(S2Cell const& cell, S2Point const* vertices) const;
158
159 S2Point axis_;
160 double height_;
161};
162
163inline S2Cap S2Cap::FromAxisHeight(S2Point const& axis, double height) {
164 DCHECK(S2::IsUnitLength(axis));
165 return S2Cap(axis, height);
166}
167
168inline S2Cap S2Cap::FromAxisArea(S2Point const& axis, double area) {
169 DCHECK(S2::IsUnitLength(axis));
170 return S2Cap(axis, area / (2 * M_PI));
171}
172
173ostream& operator<<(ostream& os, S2Cap const& cap);
174
175#endif // UTIL_GEOMETRY_S2CAP_H_
176