1// Copyright 2009 Google Inc. All Rights Reserved.
2
3// Defines the class S2EdgeIndex, a fast lookup structure for edges in S2.
4
5#ifndef UTIL_GEOMETRY_S2EDGEINDEX_H_
6#define UTIL_GEOMETRY_S2EDGEINDEX_H_
7
8#include <map>
9using std::map;
10using std::multimap;
11
12#include <utility>
13using std::pair;
14using std::make_pair;
15
16#include <vector>
17using std::vector;
18
19
20#include "base/logging.h"
21#include "base/macros.h"
22#include "s2cellid.h"
23#include "s2edgeutil.h"
24
25class S2Cell;
26
27// This class structures a set S of data edges, so that one can quickly
28// find which edges of S may potentially intersect or touch a query edge.
29//
30// The set S is assumed to be indexable by a consecutive sequence of
31// integers in the range [0..num_edges()-1]. You subclass this class by
32// defining the three virtual functions num_edges(), edge_from(),
33// edge_to(). Then you use it as follows for a query edge (a,b):
34//
35// MyS2EdgeIndex edge_index;
36// MyS2EdgeIndex::Iterator it(&edge_index);
37// S2Point const* from;
38// S2Point const* to;
39// for (it.GetCandidates(a, b); !it.Done(); it.Next()) {
40// edge_index.GetEdge(it.Index(), &from, &to);
41// ... RobustCrossing(a,b, from,to) ...
42// }
43//
44// What is this GetEdge()? You don't want to use edge_from() and
45// edge_to() in your own code: these are virtual functions that will
46// add a lot of overhead. The most efficient way is as above: you
47// define GetEdge() in your S2EdgeIndex subclass that access the edge
48// points as efficiently as possible.
49//
50// The function GetCandidates initializes the iterator to return a set
51// of candidate edges from S, such that we are sure that any data edge
52// that touches or crosses (a,b) is a candidate.
53//
54// This class returns all edges until it finds that it is worth it to compute
55// a quad tree on the data set. Chance my have it that you compute the quad
56// tree exactly when it's too late and all the work is done, If this happens,
57// we only double the total running time.
58//
59// You can help the class by declaring in advance that you will make a
60// certain number of calls to GetCandidates():
61// MyS2EdgeIndex::Iterator it(&edge_index)
62// edge_index.PredictAdditionalCalls(n);
63// for (int i = 0; i < n; ++i) {
64// for (it.GetCandidates(v(i), v(i+1)); !it.Done(); it.Next()) {
65// ... RobustCrossing(v(i), v(i+1), it.From(), it.To()) ...
66// }
67// }
68//
69// Here, we say that we will call GetCandidates() n times. If we have
70// 1000 data edges and n=1000, then we will compute the quad tree
71// immediately instead of waiting till we've wasted enough time to
72// justify the cost.
73//
74// The tradeoff between brute force and quad tree depends on many
75// things, we use a very approximate trade-off.
76//
77// See examples in S2Loop.cc and S2Polygon.cc, in particular, look at
78// the optimization that allows one to use the EdgeCrosser.
79//
80// TODO(user): Get a better API without the clumsy GetCandidates().
81// Maybe edge_index.GetIterator()?
82class S2EdgeIndex {
83 public:
84 S2EdgeIndex() { Reset(); }
85
86 virtual ~S2EdgeIndex() { }
87
88 // An iterator on data edges that may cross a query edge (a,b).
89 // Create the iterator, call GetCandidates(), then Done()/Next()
90 // repeatedly.
91 //
92 // The current edge in the iteration has index Index(), goes between
93 // From() and To().
94 class Iterator {
95 public:
96 explicit Iterator(S2EdgeIndex* edge_index): edge_index_(edge_index) {}
97
98 // Initializes the iterator to iterate over a set of candidates that may
99 // cross the edge (a,b).
100 void GetCandidates(S2Point const& a, S2Point const& b);
101
102 // Index of the current edge in the iteration.
103 int Index() const;
104
105 // True if there is no more candidate.
106 bool Done() const;
107
108 // Iterate to the next available candidate.
109 void Next();
110
111 private:
112 // The structure containing the data edges.
113 S2EdgeIndex* edge_index_;
114
115 // Tells whether GetCandidates() obtained the candidates through brute
116 // force iteration or using the quad tree structure.
117 bool is_brute_force_;
118
119 // Index of the current edge and of the edge before the last Next() call.
120 int current_index_;
121
122 // Cache of edge_index_->num_edges() so that Done() doesn't call a virtual
123 int num_edges_;
124
125 // All the candidates obtained by GetCandidates() when we are
126 // using a quad-tree (i.e. is_brute_force = false).
127 vector<int> candidates_;
128
129 // Index within array above.
130 // We have: current_index_ = candidates_[current_index_in_candidates_].
131 int current_index_in_candidates_;
132
133 DISALLOW_COPY_AND_ASSIGN(Iterator);
134 };
135
136 // Empties the index in case it already contained something.
137 void Reset();
138
139 // Computes the index if not yet done and tells if the index has
140 // been computed.
141 void ComputeIndex();
142 bool IsIndexComputed() const;
143
144 // If the index hasn't been computed yet, looks at how much work has
145 // gone into iterating using the brute force method, and how much
146 // more work is planned as defined by 'cost'. If it were to have been
147 // cheaper to use a quad tree from the beginning, then compute it
148 // now. This guarantees that we will never use more than twice the
149 // time we would have used had we known in advance exactly how many
150 // edges we would have wanted to test. It is the theoretical best.
151 //
152 // The value 'n' is the number of iterators we expect to request from
153 // this edge index.
154 void PredictAdditionalCalls(int n);
155
156 // Overwrite these functions to give access to the underlying data.
157 // The function num_edges() returns the number of edges in the
158 // index, while edge_from(index) and edge_to(index) return the
159 // "from" and "to" endpoints of the edge at the given index.
160 virtual int num_edges() const = 0;
161 virtual S2Point const* edge_from(int index) const = 0;
162 virtual S2Point const* edge_to(int index) const = 0;
163
164 protected:
165 // Appends to result all edge references in the map that cross the
166 // query edge, and possibly some more.
167 void FindCandidateCrossings(S2Point const& a, S2Point const& b,
168 vector<int>* result) const;
169
170 // Tell the index that we just received a new request for candidates.
171 // Useful to compute when to switch to quad tree.
172 void IncrementQueryCount();
173
174 private:
175 typedef multimap<S2CellId, int> CellEdgeMultimap;
176
177 // Inserts the given directed edge into the quad tree.
178 void Insert(S2Point const& a, S2Point const& b, int reference);
179
180 // Computes a cell covering of an edge. Returns the level of the s2 cells
181 // used in the covering (only one level is ever used for each call).
182 //
183 // If thicken_edge is true, the edge is thickened and extended
184 // by 1% of its length.
185 //
186 // It is guaranteed that no child of a covering cell will fully contain
187 // the covered edge.
188 int GetCovering(S2Point const& a, S2Point const& b,
189 bool thicken_edge,
190 vector<S2CellId>* result) const;
191
192 // Adds to candidate_crossings all the edges present in any ancestor of any
193 // cell of cover, down to minimum_s2_level_used. The cell->edge map
194 // is in the variable mapping.
195 static void GetEdgesInParentCells(
196 const vector<S2CellId>& cover,
197 const CellEdgeMultimap& mapping,
198 int minimum_s2_level_used,
199 vector<int>* candidate_crossings);
200
201 // Returns true if the edge and the cell (including boundary) intersect.
202 static bool EdgeIntersectsCellBoundary(
203 S2Point const& a, S2Point const& b,
204 const S2Cell& cell);
205
206 // Appends to candidate_crossings the edges that are fully contained in an
207 // S2 covering of edge. The covering of edge used is initially cover, but
208 // is refined to eliminate quickly subcells that contain many edges but do
209 // not intersect with edge.
210 static void GetEdgesInChildrenCells(
211 S2Point const& a, S2Point const& b,
212 vector<S2CellId>* cover,
213 const CellEdgeMultimap& mapping,
214 vector<int>* candidate_crossings);
215
216 // Maps cell ids to covered edges; has the property that the set of all cell
217 // ids mapping to a particular edge forms a covering of that edge.
218 CellEdgeMultimap mapping_;
219
220 // No cell strictly below this level appears in mapping_. Initially leaf
221 // level, that's the minimum level at which we will ever look for test edges.
222 int minimum_s2_level_used_;
223
224 // Has the index been computed already?
225 bool index_computed_;
226
227 // Number of queries so far
228 int query_count_;
229
230 DISALLOW_COPY_AND_ASSIGN(S2EdgeIndex);
231};
232
233inline bool S2EdgeIndex::Iterator::Done() const {
234 if (is_brute_force_) {
235 return (current_index_ >= num_edges_);
236 } else {
237 return size_t(current_index_in_candidates_) >= candidates_.size();
238 }
239}
240
241inline int S2EdgeIndex::Iterator::Index() const {
242 DCHECK(!Done());
243 return current_index_;
244}
245
246inline void S2EdgeIndex::Iterator::Next() {
247 DCHECK(!Done());
248 if (is_brute_force_) {
249 current_index_++;
250 } else {
251 current_index_in_candidates_++;
252 if (size_t(current_index_in_candidates_) < candidates_.size()) {
253 current_index_ = candidates_[current_index_in_candidates_];
254 }
255 }
256}
257
258#endif // UTIL_GEOMETRY_S2EDGEINDEX_H_
259