]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | Copyright 2008 Intel Corporation | |
3 | ||
4 | Use, modification and distribution are subject to the Boost Software License, | |
5 | Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
6 | http://www.boost.org/LICENSE_1_0.txt). | |
7 | */ | |
8 | #ifndef BOOST_POLYGON_POLYGON_90_TOUCH_HPP | |
9 | #define BOOST_POLYGON_POLYGON_90_TOUCH_HPP | |
10 | namespace boost { namespace polygon{ | |
11 | ||
12 | template <typename Unit> | |
13 | struct touch_90_operation { | |
14 | typedef interval_data<Unit> Interval; | |
15 | ||
16 | class TouchScanEvent { | |
17 | private: | |
18 | typedef std::map<Unit, std::set<int> > EventData; | |
19 | EventData eventData_; | |
20 | public: | |
21 | ||
22 | // The TouchScanEvent::iterator is a lazy algorithm that accumulates | |
23 | // polygon ids in a set as it is incremented through the | |
24 | // scan event data structure. | |
25 | // The iterator provides a forward iterator semantic only. | |
26 | class iterator { | |
27 | private: | |
28 | typename EventData::const_iterator itr_; | |
29 | std::pair<Interval, std::set<int> > ivlIds_; | |
30 | bool incremented_; | |
31 | public: | |
32 | inline iterator() : itr_(), ivlIds_(), incremented_(false) {} | |
33 | inline iterator(typename EventData::const_iterator itr, | |
34 | Unit prevPos, Unit curPos, const std::set<int>& ivlIds) : itr_(itr), ivlIds_(), incremented_(false) { | |
35 | ivlIds_.second = ivlIds; | |
36 | ivlIds_.first = Interval(prevPos, curPos); | |
37 | } | |
38 | inline iterator(const iterator& that) : itr_(), ivlIds_(), incremented_(false) { (*this) = that; } | |
39 | inline iterator& operator=(const iterator& that) { | |
40 | itr_ = that.itr_; | |
41 | ivlIds_.first = that.ivlIds_.first; | |
42 | ivlIds_.second = that.ivlIds_.second; | |
43 | incremented_ = that.incremented_; | |
44 | return *this; | |
45 | } | |
46 | inline bool operator==(const iterator& that) { return itr_ == that.itr_; } | |
47 | inline bool operator!=(const iterator& that) { return itr_ != that.itr_; } | |
48 | inline iterator& operator++() { | |
49 | //std::cout << "increment\n"; | |
50 | //std::cout << "state\n"; | |
51 | //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) { | |
52 | // std::cout << (*itr) << " "; | |
53 | //} std::cout << std::endl; | |
54 | //std::cout << "update\n"; | |
55 | for(std::set<int>::const_iterator itr = (*itr_).second.begin(); | |
56 | itr != (*itr_).second.end(); ++itr) { | |
57 | //std::cout << (*itr) << " "; | |
58 | std::set<int>::iterator lb = ivlIds_.second.find(*itr); | |
59 | if(lb != ivlIds_.second.end()) { | |
60 | ivlIds_.second.erase(lb); | |
61 | } else { | |
62 | ivlIds_.second.insert(*itr); | |
63 | } | |
64 | } | |
65 | //std::cout << std::endl; | |
66 | //std::cout << "new state\n"; | |
67 | //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) { | |
68 | // std::cout << (*itr) << " "; | |
69 | //} std::cout << std::endl; | |
70 | ++itr_; | |
71 | //ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first); | |
72 | incremented_ = true; | |
73 | return *this; | |
74 | } | |
75 | inline const iterator operator++(int){ | |
76 | iterator tmpItr(*this); | |
77 | ++(*this); | |
78 | return tmpItr; | |
79 | } | |
80 | inline std::pair<Interval, std::set<int> >& operator*() { | |
81 | if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first); | |
82 | incremented_ = false; | |
83 | if(ivlIds_.second.empty())(++(*this)); | |
84 | if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first); | |
85 | incremented_ = false; | |
86 | return ivlIds_; } | |
87 | }; | |
88 | ||
89 | inline TouchScanEvent() : eventData_() {} | |
90 | template<class iT> | |
91 | inline TouchScanEvent(iT begin, iT end) : eventData_() { | |
92 | for( ; begin != end; ++begin){ | |
93 | insert(*begin); | |
94 | } | |
95 | } | |
96 | inline TouchScanEvent(const TouchScanEvent& that) : eventData_(that.eventData_) {} | |
97 | inline TouchScanEvent& operator=(const TouchScanEvent& that){ | |
98 | eventData_ = that.eventData_; | |
99 | return *this; | |
100 | } | |
101 | ||
102 | //Insert an interval polygon id into the EventData | |
103 | inline void insert(const std::pair<Interval, int>& intervalId){ | |
104 | insert(intervalId.first.low(), intervalId.second); | |
105 | insert(intervalId.first.high(), intervalId.second); | |
106 | } | |
107 | ||
108 | //Insert an position and polygon id into EventData | |
109 | inline void insert(Unit pos, int id) { | |
110 | typename EventData::iterator lb = eventData_.lower_bound(pos); | |
111 | if(lb != eventData_.end() && lb->first == pos) { | |
112 | std::set<int>& mr (lb->second); | |
113 | std::set<int>::iterator mri = mr.find(id); | |
114 | if(mri == mr.end()) { | |
115 | mr.insert(id); | |
116 | } else { | |
117 | mr.erase(id); | |
118 | } | |
119 | } else { | |
120 | lb = eventData_.insert(lb, std::pair<Unit, std::set<int> >(pos, std::set<int>())); | |
121 | (*lb).second.insert(id); | |
122 | } | |
123 | } | |
124 | ||
125 | //merge this scan event with that by inserting its data | |
126 | inline void insert(const TouchScanEvent& that){ | |
127 | typename EventData::const_iterator itr; | |
128 | for(itr = that.eventData_.begin(); itr != that.eventData_.end(); ++itr) { | |
129 | eventData_[(*itr).first].insert(itr->second.begin(), itr->second.end()); | |
130 | } | |
131 | } | |
132 | ||
133 | //Get the begin iterator over event data | |
134 | inline iterator begin() const { | |
135 | //std::cout << "begin\n"; | |
136 | if(eventData_.empty()) return end(); | |
137 | typename EventData::const_iterator itr = eventData_.begin(); | |
138 | Unit pos = itr->first; | |
139 | const std::set<int>& idr = itr->second; | |
140 | ++itr; | |
141 | return iterator(itr, pos, itr->first, idr); | |
142 | } | |
143 | ||
144 | //Get the end iterator over event data | |
145 | inline iterator end() const { return iterator(eventData_.end(), 0, 0, std::set<int>()); } | |
146 | ||
147 | inline void clear() { eventData_.clear(); } | |
148 | ||
149 | inline Interval extents() const { | |
150 | if(eventData_.empty()) return Interval(); | |
151 | return Interval((*(eventData_.begin())).first, (*(eventData_.rbegin())).first); | |
152 | } | |
153 | }; | |
154 | ||
155 | //declaration of a map of scan events by coordinate value used to store all the | |
156 | //polygon data for a single layer input into the scanline algorithm | |
157 | typedef std::pair<std::map<Unit, TouchScanEvent>, std::map<Unit, TouchScanEvent> > TouchSetData; | |
158 | ||
159 | class TouchOp { | |
160 | public: | |
161 | typedef std::map<Unit, std::set<int> > ScanData; | |
162 | typedef std::pair<Unit, std::set<int> > ElementType; | |
163 | protected: | |
164 | ScanData scanData_; | |
165 | typename ScanData::iterator nextItr_; | |
166 | public: | |
167 | inline TouchOp () : scanData_(), nextItr_() { nextItr_ = scanData_.end(); } | |
168 | inline TouchOp (const TouchOp& that) : scanData_(that.scanData_), nextItr_() { nextItr_ = scanData_.begin(); } | |
169 | inline TouchOp& operator=(const TouchOp& that); | |
170 | ||
171 | //moves scanline forward | |
172 | inline void advanceScan() { nextItr_ = scanData_.begin(); } | |
173 | ||
174 | //proceses the given interval and std::set<int> data | |
175 | //the output data structre is a graph, the indicies in the vector correspond to graph nodes, | |
176 | //the integers in the set are vector indicies and are the nodes with which that node shares an edge | |
177 | template <typename graphT> | |
178 | inline void processInterval(graphT& outputContainer, Interval ivl, const std::set<int>& ids, bool leadingEdge) { | |
179 | //print(); | |
180 | typename ScanData::iterator lowItr = lookup_(ivl.low()); | |
181 | typename ScanData::iterator highItr = lookup_(ivl.high()); | |
182 | //std::cout << "Interval: " << ivl << std::endl; | |
183 | //for(std::set<int>::const_iterator itr = ids.begin(); itr != ids.end(); ++itr) | |
184 | // std::cout << (*itr) << " "; | |
185 | //std::cout << std::endl; | |
186 | //add interval to scan data if it is past the end | |
187 | if(lowItr == scanData_.end()) { | |
188 | //std::cout << "case0" << std::endl; | |
189 | lowItr = insert_(ivl.low(), ids); | |
190 | evaluateBorder_(outputContainer, ids, ids); | |
191 | highItr = insert_(ivl.high(), std::set<int>()); | |
192 | return; | |
193 | } | |
194 | //ensure that highItr points to the end of the ivl | |
195 | if(highItr == scanData_.end() || (*highItr).first > ivl.high()) { | |
196 | //std::cout << "case1" << std::endl; | |
197 | //std::cout << highItr->first << std::endl; | |
198 | std::set<int> value = std::set<int>(); | |
199 | if(highItr != scanData_.begin()) { | |
200 | --highItr; | |
201 | //std::cout << highItr->first << std::endl; | |
202 | //std::cout << "high set size " << highItr->second.size() << std::endl; | |
203 | value = highItr->second; | |
204 | } | |
205 | nextItr_ = highItr; | |
206 | highItr = insert_(ivl.high(), value); | |
207 | } else { | |
208 | //evaluate border with next higher interval | |
209 | //std::cout << "case1a" << std::endl; | |
210 | if(leadingEdge)evaluateBorder_(outputContainer, highItr->second, ids); | |
211 | } | |
212 | //split the low interval if needed | |
213 | if(lowItr->first > ivl.low()) { | |
214 | //std::cout << "case2" << std::endl; | |
215 | if(lowItr != scanData_.begin()) { | |
216 | //std::cout << "case3" << std::endl; | |
217 | --lowItr; | |
218 | nextItr_ = lowItr; | |
219 | //std::cout << lowItr->first << " " << lowItr->second.size() << std::endl; | |
220 | lowItr = insert_(ivl.low(), lowItr->second); | |
221 | } else { | |
222 | //std::cout << "case4" << std::endl; | |
223 | nextItr_ = lowItr; | |
224 | lowItr = insert_(ivl.low(), std::set<int>()); | |
225 | } | |
226 | } else { | |
227 | //evaluate border with next higher interval | |
228 | //std::cout << "case2a" << std::endl; | |
229 | typename ScanData::iterator nextLowerItr = lowItr; | |
230 | if(leadingEdge && nextLowerItr != scanData_.begin()){ | |
231 | --nextLowerItr; | |
232 | evaluateBorder_(outputContainer, nextLowerItr->second, ids); | |
233 | } | |
234 | } | |
235 | //std::cout << "low: " << lowItr->first << " high: " << highItr->first << std::endl; | |
236 | //print(); | |
237 | //process scan data intersecting interval | |
238 | for(typename ScanData::iterator itr = lowItr; itr != highItr; ){ | |
239 | //std::cout << "case5" << std::endl; | |
240 | //std::cout << itr->first << std::endl; | |
241 | std::set<int>& beforeIds = itr->second; | |
242 | ++itr; | |
243 | evaluateInterval_(outputContainer, beforeIds, ids, leadingEdge); | |
244 | } | |
245 | //print(); | |
246 | //merge the bottom interval with the one below if they have the same count | |
247 | if(lowItr != scanData_.begin()){ | |
248 | //std::cout << "case6" << std::endl; | |
249 | typename ScanData::iterator belowLowItr = lowItr; | |
250 | --belowLowItr; | |
251 | if(belowLowItr->second == lowItr->second) { | |
252 | //std::cout << "case7" << std::endl; | |
253 | scanData_.erase(lowItr); | |
254 | } | |
255 | } | |
256 | //merge the top interval with the one above if they have the same count | |
257 | if(highItr != scanData_.begin()) { | |
258 | //std::cout << "case8" << std::endl; | |
259 | typename ScanData::iterator beforeHighItr = highItr; | |
260 | --beforeHighItr; | |
261 | if(beforeHighItr->second == highItr->second) { | |
262 | //std::cout << "case9" << std::endl; | |
263 | scanData_.erase(highItr); | |
264 | highItr = beforeHighItr; | |
265 | ++highItr; | |
266 | } | |
267 | } | |
268 | //print(); | |
269 | nextItr_ = highItr; | |
270 | } | |
271 | ||
272 | // inline void print() const { | |
273 | // for(typename ScanData::const_iterator itr = scanData_.begin(); itr != scanData_.end(); ++itr) { | |
274 | // std::cout << itr->first << ": "; | |
275 | // for(std::set<int>::const_iterator sitr = itr->second.begin(); | |
276 | // sitr != itr->second.end(); ++sitr){ | |
277 | // std::cout << *sitr << " "; | |
278 | // } | |
279 | // std::cout << std::endl; | |
280 | // } | |
281 | // } | |
282 | ||
283 | private: | |
284 | inline typename ScanData::iterator lookup_(Unit pos){ | |
285 | if(nextItr_ != scanData_.end() && nextItr_->first >= pos) { | |
286 | return nextItr_; | |
287 | } | |
288 | return nextItr_ = scanData_.lower_bound(pos); | |
289 | } | |
290 | ||
291 | inline typename ScanData::iterator insert_(Unit pos, const std::set<int>& ids){ | |
292 | //std::cout << "inserting " << ids.size() << " ids at: " << pos << std::endl; | |
293 | return nextItr_ = scanData_.insert(nextItr_, std::pair<Unit, std::set<int> >(pos, ids)); | |
294 | } | |
295 | ||
296 | template <typename graphT> | |
297 | inline void evaluateInterval_(graphT& outputContainer, std::set<int>& ids, | |
298 | const std::set<int>& changingIds, bool leadingEdge) { | |
299 | for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){ | |
300 | //std::cout << "evaluateInterval " << (*ciditr) << std::endl; | |
301 | evaluateId_(outputContainer, ids, *ciditr, leadingEdge); | |
302 | } | |
303 | } | |
304 | template <typename graphT> | |
305 | inline void evaluateBorder_(graphT& outputContainer, const std::set<int>& ids, const std::set<int>& changingIds) { | |
306 | for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){ | |
307 | //std::cout << "evaluateBorder " << (*ciditr) << std::endl; | |
308 | evaluateBorderId_(outputContainer, ids, *ciditr); | |
309 | } | |
310 | } | |
311 | template <typename graphT> | |
312 | inline void evaluateBorderId_(graphT& outputContainer, const std::set<int>& ids, int changingId) { | |
313 | for(std::set<int>::const_iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) { | |
314 | //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl; | |
315 | if(changingId != *scanItr){ | |
316 | outputContainer[changingId].insert(*scanItr); | |
317 | outputContainer[*scanItr].insert(changingId); | |
318 | } | |
319 | } | |
320 | } | |
321 | template <typename graphT> | |
322 | inline void evaluateId_(graphT& outputContainer, std::set<int>& ids, int changingId, bool leadingEdge) { | |
323 | //std::cout << "changingId: " << changingId << std::endl; | |
324 | //for( std::set<int>::iterator itr = ids.begin(); itr != ids.end(); ++itr){ | |
325 | // std::cout << *itr << " "; | |
326 | //}std::cout << std::endl; | |
327 | std::set<int>::iterator lb = ids.lower_bound(changingId); | |
328 | if(lb == ids.end() || (*lb) != changingId) { | |
329 | if(leadingEdge) { | |
330 | //std::cout << "insert\n"; | |
331 | //insert and add to output | |
332 | for(std::set<int>::iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) { | |
333 | //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl; | |
334 | if(changingId != *scanItr){ | |
335 | outputContainer[changingId].insert(*scanItr); | |
336 | outputContainer[*scanItr].insert(changingId); | |
337 | } | |
338 | } | |
339 | ids.insert(changingId); | |
340 | } | |
341 | } else { | |
342 | if(!leadingEdge){ | |
343 | //std::cout << "erase\n"; | |
344 | ids.erase(lb); | |
345 | } | |
346 | } | |
347 | } | |
348 | }; | |
349 | ||
350 | template <typename graphT> | |
351 | static inline void processEvent(graphT& outputContainer, TouchOp& op, const TouchScanEvent& data, bool leadingEdge) { | |
352 | for(typename TouchScanEvent::iterator itr = data.begin(); itr != data.end(); ++itr) { | |
353 | //std::cout << "processInterval" << std::endl; | |
354 | op.processInterval(outputContainer, (*itr).first, (*itr).second, leadingEdge); | |
355 | } | |
356 | } | |
357 | ||
358 | template <typename graphT> | |
359 | static inline void performTouch(graphT& outputContainer, const TouchSetData& data) { | |
360 | typename std::map<Unit, TouchScanEvent>::const_iterator leftItr = data.first.begin(); | |
361 | typename std::map<Unit, TouchScanEvent>::const_iterator rightItr = data.second.begin(); | |
362 | typename std::map<Unit, TouchScanEvent>::const_iterator leftEnd = data.first.end(); | |
363 | typename std::map<Unit, TouchScanEvent>::const_iterator rightEnd = data.second.end(); | |
364 | TouchOp op; | |
365 | while(leftItr != leftEnd || rightItr != rightEnd) { | |
366 | //std::cout << "loop" << std::endl; | |
367 | op.advanceScan(); | |
368 | //rightItr cannont be at end if leftItr is not at end | |
369 | if(leftItr != leftEnd && rightItr != rightEnd && | |
370 | leftItr->first <= rightItr->first) { | |
371 | //std::cout << "case1" << std::endl; | |
372 | //std::cout << leftItr ->first << std::endl; | |
373 | processEvent(outputContainer, op, leftItr->second, true); | |
374 | ++leftItr; | |
375 | } else { | |
376 | //std::cout << "case2" << std::endl; | |
377 | //std::cout << rightItr ->first << std::endl; | |
378 | processEvent(outputContainer, op, rightItr->second, false); | |
379 | ++rightItr; | |
380 | } | |
381 | } | |
382 | } | |
383 | ||
384 | template <class iT> | |
385 | static inline void populateTouchSetData(TouchSetData& data, iT beginData, iT endData, int id) { | |
386 | Unit prevPos = ((std::numeric_limits<Unit>::max)()); | |
387 | Unit prevY = prevPos; | |
388 | int count = 0; | |
389 | for(iT itr = beginData; itr != endData; ++itr) { | |
390 | Unit pos = (*itr).first; | |
391 | if(pos != prevPos) { | |
392 | prevPos = pos; | |
393 | prevY = (*itr).second.first; | |
394 | count = (*itr).second.second; | |
395 | continue; | |
396 | } | |
397 | Unit y = (*itr).second.first; | |
398 | if(count != 0 && y != prevY) { | |
399 | std::pair<Interval, int> element(Interval(prevY, y), id); | |
400 | if(count > 0) { | |
401 | data.first[pos].insert(element); | |
402 | } else { | |
403 | data.second[pos].insert(element); | |
404 | } | |
405 | } | |
406 | prevY = y; | |
407 | count += (*itr).second.second; | |
408 | } | |
409 | } | |
410 | ||
411 | static inline void populateTouchSetData(TouchSetData& data, const std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputData, int id) { | |
412 | populateTouchSetData(data, inputData.begin(), inputData.end(), id); | |
413 | } | |
414 | ||
415 | }; | |
416 | } | |
417 | } | |
418 | #endif |