← Back to branch summary

~ubuntu-branches/debian/sid/boost1.49/sid

« back to all changes in this revision

Viewing changes to boost/polygon/detail/polygon_90_touch.hpp

  • Committer: Package Import Robot
  • Author(s): Steve M. Robbins
  • Date: 2012-02-26 00:31:44 UTC
  • Revision ID: package-import@ubuntu.com-20120226003144-eaytp12cbf6ubpms
Tags: upstream-1.49.0
Import upstream version 1.49.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
boost/polygon/detail/polygon_90_touch.hpp
 
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