2 Copyright 2008 Intel Corporation
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).
8 #ifndef BOOST_POLYGON_POLYGON_90_TOUCH_HPP
9 #define BOOST_POLYGON_POLYGON_90_TOUCH_HPP
10 namespace boost { namespace polygon{
12 template <typename Unit>
13 struct touch_90_operation {
14 typedef interval_data<Unit> Interval;
16 class TouchScanEvent {
18 typedef std::map<Unit, std::set<int> > EventData;
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.
28 typename EventData::const_iterator itr_;
29 std::pair<Interval, std::set<int> > ivlIds_;
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);
38 inline iterator(const iterator& that) : itr_(), ivlIds_(), incremented_(false) { (*this) = that; }
39 inline iterator& operator=(const iterator& that) {
41 ivlIds_.first = that.ivlIds_.first;
42 ivlIds_.second = that.ivlIds_.second;
43 incremented_ = that.incremented_;
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);
62 ivlIds_.second.insert(*itr);
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;
71 //ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
75 inline const iterator operator++(int){
76 iterator tmpItr(*this);
80 inline std::pair<Interval, std::set<int> >& operator*() {
81 if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
83 if(ivlIds_.second.empty())(++(*this));
84 if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
89 inline TouchScanEvent() : eventData_() {}
91 inline TouchScanEvent(iT begin, iT end) : eventData_() {
92 for( ; begin != end; ++begin){
96 inline TouchScanEvent(const TouchScanEvent& that) : eventData_(that.eventData_) {}
97 inline TouchScanEvent& operator=(const TouchScanEvent& that){
98 eventData_ = that.eventData_;
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);
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()) {
120 lb = eventData_.insert(lb, std::pair<Unit, std::set<int> >(pos, std::set<int>()));
121 (*lb).second.insert(id);
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());
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;
141 return iterator(itr, pos, itr->first, idr);
144 //Get the end iterator over event data
145 inline iterator end() const { return iterator(eventData_.end(), 0, 0, std::set<int>()); }
147 inline void clear() { eventData_.clear(); }
149 inline Interval extents() const {
150 if(eventData_.empty()) return Interval();
151 return Interval((*(eventData_.begin())).first, (*(eventData_.rbegin())).first);
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;
161 typedef std::map<Unit, std::set<int> > ScanData;
162 typedef std::pair<Unit, std::set<int> > ElementType;
165 typename ScanData::iterator nextItr_;
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);
171 //moves scanline forward
172 inline void advanceScan() { nextItr_ = scanData_.begin(); }
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) {
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>());
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()) {
201 //std::cout << highItr->first << std::endl;
202 //std::cout << "high set size " << highItr->second.size() << std::endl;
203 value = highItr->second;
206 highItr = insert_(ivl.high(), value);
208 //evaluate border with next higher interval
209 //std::cout << "case1a" << std::endl;
210 if(leadingEdge)evaluateBorder_(outputContainer, highItr->second, ids);
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;
219 //std::cout << lowItr->first << " " << lowItr->second.size() << std::endl;
220 lowItr = insert_(ivl.low(), lowItr->second);
222 //std::cout << "case4" << std::endl;
224 lowItr = insert_(ivl.low(), std::set<int>());
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()){
232 evaluateBorder_(outputContainer, nextLowerItr->second, ids);
235 //std::cout << "low: " << lowItr->first << " high: " << highItr->first << std::endl;
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;
243 evaluateInterval_(outputContainer, beforeIds, ids, leadingEdge);
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;
251 if(belowLowItr->second == lowItr->second) {
252 //std::cout << "case7" << std::endl;
253 scanData_.erase(lowItr);
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;
261 if(beforeHighItr->second == highItr->second) {
262 //std::cout << "case9" << std::endl;
263 scanData_.erase(highItr);
264 highItr = beforeHighItr;
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 << " ";
279 // std::cout << std::endl;
284 inline typename ScanData::iterator lookup_(Unit pos){
285 if(nextItr_ != scanData_.end() && nextItr_->first >= pos) {
288 return nextItr_ = scanData_.lower_bound(pos);
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));
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);
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);
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);
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) {
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);
339 ids.insert(changingId);
343 //std::cout << "erase\n";
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);
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();
365 while(leftItr != leftEnd || rightItr != rightEnd) {
366 //std::cout << "loop" << std::endl;
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);
376 //std::cout << "case2" << std::endl;
377 //std::cout << rightItr ->first << std::endl;
378 processEvent(outputContainer, op, rightItr->second, false);
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;
389 for(iT itr = beginData; itr != endData; ++itr) {
390 Unit pos = (*itr).first;
393 prevY = (*itr).second.first;
394 count = (*itr).second.second;
397 Unit y = (*itr).second.first;
398 if(count != 0 && y != prevY) {
399 std::pair<Interval, int> element(Interval(prevY, y), id);
401 data.first[pos].insert(element);
403 data.second[pos].insert(element);
407 count += (*itr).second.second;
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);