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> |
9 | using std::map; |
10 | using std::multimap; |
11 | |
12 | #include <utility> |
13 | using std::pair; |
14 | using std::make_pair; |
15 | |
16 | #include <vector> |
17 | using std::vector; |
18 | |
19 | |
20 | #include "base/logging.h" |
21 | #include "base/macros.h" |
22 | #include "s2cellid.h" |
23 | #include "s2edgeutil.h" |
24 | |
25 | class 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()? |
82 | class 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 | |
233 | inline 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 | |
241 | inline int S2EdgeIndex::Iterator::Index() const { |
242 | DCHECK(!Done()); |
243 | return current_index_; |
244 | } |
245 | |
246 | inline 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 | |