1// Copyright 2005 Google Inc. All Rights Reserved.
2
3#ifndef UTIL_GEOMETRY_S2REGION_COVERER_H_
4#define UTIL_GEOMETRY_S2REGION_COVERER_H_
5
6#include <queue>
7using std::priority_queue;
8
9#include <utility>
10using std::pair;
11using std::make_pair;
12
13#include <vector>
14using std::vector;
15
16#include "base/macros.h"
17#include "base/scoped_ptr.h"
18#include "s2cell.h"
19#include "s2cellid.h"
20
21class S2CellUnion;
22
23// An S2RegionCoverer is a class that allows arbitrary regions to be
24// approximated as unions of cells (S2CellUnion). This is useful for
25// implementing various sorts of search and precomputation operations.
26//
27// Typical usage:
28//
29// S2RegionCoverer coverer;
30// coverer.set_max_cells(5);
31// S2Cap cap = S2Cap::FromAxisAngle(...);
32// vector<S2CellId> covering;
33// coverer.GetCovering(cap, &covering);
34//
35// This yields a vector of at most 5 cells that is guaranteed to cover the
36// given cap (a disc-shaped region on the sphere).
37//
38// The approximation algorithm is not optimal but does a pretty good job in
39// practice. The output does not always use the maximum number of cells
40// allowed, both because this would not always yield a better approximation,
41// and because max_cells() is a limit on how much work is done exploring the
42// possible covering as well as a limit on the final output size.
43//
44// One can also generate interior coverings, which are sets of cells which
45// are entirely contained within a region. Interior coverings can be
46// empty, even for non-empty regions, if there are no cells that satisfy
47// the provided constraints and are contained by the region. Note that for
48// performance reasons, it is wise to specify a max_level when computing
49// interior coverings - otherwise for regions with small or zero area, the
50// algorithm may spend a lot of time subdividing cells all the way to leaf
51// level to try to find contained cells.
52class S2RegionCoverer {
53 public:
54 // By default, the covering uses at most 8 cells at any level. This gives
55 // a reasonable tradeoff between the number of cells used and the accuracy
56 // of the approximation (see table below).
57 static int const kDefaultMaxCells = 8;
58
59 S2RegionCoverer();
60 ~S2RegionCoverer();
61
62 // Set the minimum and maximum cell level to be used. The default is to use
63 // all cell levels. Requires: max_level() >= min_level().
64 //
65 // To find the cell level corresponding to a given physical distance, use
66 // the S2Cell metrics defined in s2.h. For example, to find the cell
67 // level that corresponds to an average edge length of 10km, use:
68 //
69 // int level = S2::kAvgEdge.GetClosestLevel(
70 // geostore::S2Earth::KmToRadians(length_km));
71 //
72 // Note: min_level() takes priority over max_cells(), i.e. cells below the
73 // given level will never be used even if this causes a large number of
74 // cells to be returned.
75 void set_min_level(int min_level);
76 void set_max_level(int max_level);
77 int min_level() const { return min_level_; }
78 int max_level() const { return max_level_; }
79
80 // If specified, then only cells where (level - min_level) is a multiple of
81 // "level_mod" will be used (default 1). This effectively allows the
82 // branching factor of the S2CellId hierarchy to be increased. Currently
83 // the only parameter values allowed are 1, 2, or 3, corresponding to
84 // branching factors of 4, 16, and 64 respectively.
85 void set_level_mod(int level_mod);
86 int level_mod() const { return level_mod_; }
87
88 // Sets the maximum desired number of cells in the approximation (defaults
89 // to kDefaultMaxCells). Note the following:
90 //
91 // - For any setting of max_cells(), up to 6 cells may be returned if that
92 // is the minimum number of cells required (e.g. if the region intersects
93 // all six face cells). Up to 3 cells may be returned even for very tiny
94 // convex regions if they happen to be located at the intersection of
95 // three cube faces.
96 //
97 // - For any setting of max_cells(), an arbitrary number of cells may be
98 // returned if min_level() is too high for the region being approximated.
99 //
100 // - If max_cells() is less than 4, the area of the covering may be
101 // arbitrarily large compared to the area of the original region even if
102 // the region is convex (e.g. an S2Cap or S2LatLngRect).
103 //
104 // Accuracy is measured by dividing the area of the covering by the area of
105 // the original region. The following table shows the median and worst case
106 // values for this area ratio on a test case consisting of 100,000 spherical
107 // caps of random size (generated using s2regioncoverer_unittest):
108 //
109 // max_cells: 3 4 5 6 8 12 20 100 1000
110 // median ratio: 5.33 3.32 2.73 2.34 1.98 1.66 1.42 1.11 1.01
111 // worst case: 215518 14.41 9.72 5.26 3.91 2.75 1.92 1.20 1.02
112 void set_max_cells(int max_cells);
113 int max_cells() const { return max_cells_; }
114
115 // Return a vector of cell ids that covers (GetCovering) or is contained
116 // within (GetInteriorCovering) the given region and satisfies the various
117 // restrictions specified above.
118 void GetCovering(S2Region const& region, vector<S2CellId>* covering);
119 void GetInteriorCovering(S2Region const& region, vector<S2CellId>* interior);
120
121 // Return a normalized cell union that covers (GetCellUnion) or is contained
122 // within (GetInteriorCellUnion) the given region and satisfies the
123 // restrictions *EXCEPT* for min_level() and level_mod(). These criteria
124 // cannot be satisfied using a cell union because cell unions are
125 // automatically normalized by replacing four child cells with their parent
126 // whenever possible. (Note that the list of cell ids passed to the cell
127 // union constructor does in fact satisfy all the given restrictions.)
128 void GetCellUnion(S2Region const& region, S2CellUnion* covering);
129 void GetInteriorCellUnion(S2Region const& region, S2CellUnion* interior);
130
131 // Given a connected region and a starting point, return a set of cells at
132 // the given level that cover the region.
133 static void GetSimpleCovering(S2Region const& region, S2Point const& start,
134 int level, vector<S2CellId>* output);
135
136 private:
137 struct Candidate {
138 S2Cell cell;
139 bool is_terminal; // Cell should not be expanded further.
140 int num_children; // Number of children that intersect the region.
141 Candidate* children[0]; // Actual size may be 0, 4, 16, or 64 elements.
142 };
143
144 // If the cell intersects the given region, return a new candidate with no
145 // children, otherwise return NULL. Also marks the candidate as "terminal"
146 // if it should not be expanded further.
147 Candidate* NewCandidate(S2Cell const& cell);
148
149 // Return the log base 2 of the maximum number of children of a candidate.
150 inline int max_children_shift() const { return 2 * level_mod_; }
151
152 // Free the memory associated with a candidate.
153 static void DeleteCandidate(Candidate* candidate, bool delete_children);
154
155 // Process a candidate by either adding it to the result_ vector or
156 // expanding its children and inserting it into the priority queue.
157 // Passing an argument of NULL does nothing.
158 void AddCandidate(Candidate* candidate);
159
160 // Populate the children of "candidate" by expanding the given number of
161 // levels from the given cell. Returns the number of children that were
162 // marked "terminal".
163 int ExpandChildren(Candidate* candidate, S2Cell const& cell, int num_levels);
164
165 // Computes a set of initial candidates that cover the given region.
166 void GetInitialCandidates();
167
168 // Generates a covering and stores it in result_.
169 void GetCoveringInternal(S2Region const& region);
170
171 // Given a region and a starting cell, return the set of all the
172 // edge-connected cells at the same level that intersect "region".
173 // The output cells are returned in arbitrary order.
174 static void FloodFill(S2Region const& region, S2CellId const& start,
175 vector<S2CellId>* output);
176
177 int min_level_;
178 int max_level_;
179 int level_mod_;
180 int max_cells_;
181
182 // We save a temporary copy of the pointer passed to GetCovering() in order
183 // to avoid passing this parameter around internally. It is only used (and
184 // only valid) for the duration of a single GetCovering() call.
185 S2Region const* region_;
186
187 // A temporary variable used by GetCovering() that holds the cell ids that
188 // have been added to the covering so far.
189 scoped_ptr<vector<S2CellId> > result_;
190
191 // We keep the candidates in a priority queue. We specify a vector to hold
192 // the queue entries since for some reason priority_queue<> uses a deque by
193 // default.
194 struct CompareQueueEntries;
195 typedef pair<int, Candidate*> QueueEntry;
196 typedef priority_queue<QueueEntry, vector<QueueEntry>,
197 CompareQueueEntries> CandidateQueue;
198 scoped_ptr<CandidateQueue> pq_;
199
200 // True if we're computing an interior covering.
201 bool interior_covering_;
202
203 // Counter of number of candidates created, for performance evaluation.
204 int candidates_created_counter_;
205
206 DISALLOW_EVIL_CONSTRUCTORS(S2RegionCoverer);
207};
208
209#endif // UTIL_GEOMETRY_S2REGION_COVERER_H_
210