polygon/detail/polygon_90_touch.hpp

0001 /*
0002   Copyright 2008 Intel Corporation
0003
0004   Use, modification and distribution are subject to the Boost Software License,
0005   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008 #ifndef BOOST_POLYGON_POLYGON_90_TOUCH_HPP
0009 #define BOOST_POLYGON_POLYGON_90_TOUCH_HPP
0010 namespace boost { namespace polygon{
0011
0012   template <typename Unit>
0013   struct touch_90_operation {
0014     typedef interval_data<Unit> Interval;
0015
0016     class TouchScanEvent {
0017     private:
0018       typedef std::map<Unit, std::set<int> > EventData;
0019       EventData eventData_;
0020     public:
0021
0022       // The TouchScanEvent::iterator is a lazy algorithm that accumulates
0023       // polygon ids in a set as it is incremented through the
0024       // scan event data structure.
0025       // The iterator provides a forward iterator semantic only.
0026       class iterator {
0027       private:
0028         typename EventData::const_iterator itr_;
0029         std::pair<Interval, std::set<int> > ivlIds_;
0030         bool incremented_;
0031       public:
0032         inline iterator() : itr_(), ivlIds_(), incremented_(false) {}
0033         inline iterator(typename EventData::const_iterator itr,
0034                         Unit prevPos, Unit curPos, const std::set<int>& ivlIds) : itr_(itr), ivlIds_(), incremented_(false) {
0035           ivlIds_.second = ivlIds;
0036           ivlIds_.first = Interval(prevPos, curPos);
0037         }
0038         inline iterator(const iterator& that) : itr_(), ivlIds_(), incremented_(false) { (*this) = that; }
0039         inline iterator& operator=(const iterator& that) {
0040           itr_ = that.itr_;
0041           ivlIds_.first = that.ivlIds_.first;
0042           ivlIds_.second = that.ivlIds_.second;
0043           incremented_ = that.incremented_;
0044           return *this;
0045         }
0046         inline bool operator==(const iterator& that) { return itr_ == that.itr_; }
0047         inline bool operator!=(const iterator& that) { return itr_ != that.itr_; }
0048         inline iterator& operator++() {
0049           //std::cout << "increment\n";
0050           //std::cout << "state\n";
0051           //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
0052           //   std::cout << (*itr) << " ";
0053           //} std::cout << std::endl;
0054           //std::cout << "update\n";
0055           for(std::set<int>::const_iterator itr = (*itr_).second.begin();
0056               itr != (*itr_).second.end(); ++itr) {
0057             //std::cout << (*itr) <<  " ";
0058             std::set<int>::iterator lb = ivlIds_.second.find(*itr);
0059             if(lb != ivlIds_.second.end()) {
0060               ivlIds_.second.erase(lb);
0061             } else {
0062               ivlIds_.second.insert(*itr);
0063             }
0064           }
0065           //std::cout << std::endl;
0066           //std::cout << "new state\n";
0067           //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
0068           //   std::cout << (*itr) << " ";
0069           //} std::cout << std::endl;
0070           ++itr_;
0071           //ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
0072           incremented_ = true;
0073           return *this;
0074         }
0075         inline const iterator operator++(int){
0076           iterator tmpItr(*this);
0077           ++(*this);
0078           return tmpItr;
0079         }
0080         inline std::pair<Interval, std::set<int> >& operator*() {
0081           if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
0082           incremented_ = false;
0083           if(ivlIds_.second.empty())(++(*this));
0084           if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
0085           incremented_ = false;
0086           return ivlIds_; }
0087       };
0088
0089       inline TouchScanEvent() : eventData_() {}
0090       template<class iT>
0091       inline TouchScanEvent(iT begin, iT end) : eventData_() {
0092         for( ; begin != end; ++begin){
0093           insert(*begin);
0094         }
0095       }
0096       inline TouchScanEvent(const TouchScanEvent& that) : eventData_(that.eventData_) {}
0097       inline TouchScanEvent& operator=(const TouchScanEvent& that){
0098         eventData_ = that.eventData_;
0099         return *this;
0100       }
0101
0102       //Insert an interval polygon id into the EventData
0103       inline void insert(const std::pair<Interval, int>& intervalId){
0104         insert(intervalId.first.low(), intervalId.second);
0105         insert(intervalId.first.high(), intervalId.second);
0106       }
0107
0108       //Insert an position and polygon id into EventData
0109       inline void insert(Unit pos, int id) {
0110         typename EventData::iterator lb = eventData_.lower_bound(pos);
0111         if(lb != eventData_.end() && lb->first == pos) {
0112           std::set<int>& mr (lb->second);
0113           std::set<int>::iterator mri = mr.find(id);
0114           if(mri == mr.end()) {
0115             mr.insert(id);
0116           } else {
0117             mr.erase(id);
0118           }
0119         } else {
0120           lb = eventData_.insert(lb, std::pair<Unit, std::set<int> >(pos, std::set<int>()));
0121           (*lb).second.insert(id);
0122         }
0123       }
0124
0125       //merge this scan event with that by inserting its data
0126       inline void insert(const TouchScanEvent& that){
0127         typename EventData::const_iterator itr;
0128         for(itr = that.eventData_.begin(); itr != that.eventData_.end(); ++itr) {
0129           eventData_[(*itr).first].insert(itr->second.begin(), itr->second.end());
0130         }
0131       }
0132
0133       //Get the begin iterator over event data
0134       inline iterator begin() const {
0135         //std::cout << "begin\n";
0136         if(eventData_.empty()) return end();
0137         typename EventData::const_iterator itr = eventData_.begin();
0138         Unit pos = itr->first;
0139         const std::set<int>& idr = itr->second;
0140         ++itr;
0141         return iterator(itr, pos, itr->first, idr);
0142       }
0143
0144       //Get the end iterator over event data
0145       inline iterator end() const { return iterator(eventData_.end(), 0, 0, std::set<int>()); }
0146
0147       inline void clear() { eventData_.clear(); }
0148
0149       inline Interval extents() const {
0150         if(eventData_.empty()) return Interval();
0151         return Interval((*(eventData_.begin())).first, (*(eventData_.rbegin())).first);
0152       }
0153     };
0154
0155     //declaration of a map of scan events by coordinate value used to store all the
0156     //polygon data for a single layer input into the scanline algorithm
0157     typedef std::pair<std::map<Unit, TouchScanEvent>, std::map<Unit, TouchScanEvent> > TouchSetData;
0158
0159     class TouchOp {
0160     public:
0161       typedef std::map<Unit, std::set<int> > ScanData;
0162       typedef std::pair<Unit, std::set<int> > ElementType;
0163     protected:
0164       ScanData scanData_;
0165       typename ScanData::iterator nextItr_;
0166     public:
0167       inline TouchOp () : scanData_(), nextItr_() { nextItr_ = scanData_.end(); }
0168       inline TouchOp (const TouchOp& that) : scanData_(that.scanData_), nextItr_() { nextItr_ = scanData_.begin(); }
0169       inline TouchOp& operator=(const TouchOp& that);
0170
0171       //moves scanline forward
0172       inline void advanceScan() { nextItr_ = scanData_.begin(); }
0173
0174       //proceses the given interval and std::set<int> data
0175       //the output data structre is a graph, the indicies in the vector correspond to graph nodes,
0176       //the integers in the set are vector indicies and are the nodes with which that node shares an edge
0177       template <typename graphT>
0178       inline void processInterval(graphT& outputContainer, Interval ivl, const std::set<int>& ids, bool leadingEdge) {
0179         //print();
0180         typename ScanData::iterator lowItr = lookup_(ivl.low());
0181         typename ScanData::iterator highItr = lookup_(ivl.high());
0182         //std::cout << "Interval: " << ivl << std::endl;
0183         //for(std::set<int>::const_iterator itr = ids.begin(); itr != ids.end(); ++itr)
0184         //   std::cout << (*itr) << " ";
0185         //std::cout << std::endl;
0186         //add interval to scan data if it is past the end
0187         if(lowItr == scanData_.end()) {
0188           //std::cout << "case0" << std::endl;
0189           lowItr = insert_(ivl.low(), ids);
0190           evaluateBorder_(outputContainer, ids, ids);
0191           highItr = insert_(ivl.high(), std::set<int>());
0192           return;
0193         }
0194         //ensure that highItr points to the end of the ivl
0195         if(highItr == scanData_.end() || (*highItr).first > ivl.high()) {
0196           //std::cout << "case1" << std::endl;
0197           //std::cout << highItr->first << std::endl;
0198           std::set<int> value = std::set<int>();
0199           if(highItr != scanData_.begin()) {
0200             --highItr;
0201             //std::cout << highItr->first << std::endl;
0202             //std::cout << "high set size " << highItr->second.size() << std::endl;
0203             value = highItr->second;
0204           }
0205           nextItr_ = highItr;
0206           highItr = insert_(ivl.high(), value);
0207         } else {
0208           //evaluate border with next higher interval
0209           //std::cout << "case1a" << std::endl;
0210           if(leadingEdge)evaluateBorder_(outputContainer, highItr->second, ids);
0211         }
0212         //split the low interval if needed
0213         if(lowItr->first > ivl.low()) {
0214           //std::cout << "case2" << std::endl;
0215           if(lowItr != scanData_.begin()) {
0216             //std::cout << "case3" << std::endl;
0217             --lowItr;
0218             nextItr_ = lowItr;
0219             //std::cout << lowItr->first << " " << lowItr->second.size() << std::endl;
0220             lowItr = insert_(ivl.low(), lowItr->second);
0221           } else {
0222             //std::cout << "case4" << std::endl;
0223             nextItr_ = lowItr;
0224             lowItr = insert_(ivl.low(), std::set<int>());
0225           }
0226         } else {
0227           //evaluate border with next higher interval
0228           //std::cout << "case2a" << std::endl;
0229           typename ScanData::iterator nextLowerItr = lowItr;
0230           if(leadingEdge && nextLowerItr != scanData_.begin()){
0231             --nextLowerItr;
0232             evaluateBorder_(outputContainer, nextLowerItr->second, ids);
0233           }
0234         }
0235         //std::cout << "low: " << lowItr->first << " high: " << highItr->first << std::endl;
0236         //print();
0237         //process scan data intersecting interval
0238         for(typename ScanData::iterator itr = lowItr; itr != highItr; ){
0239           //std::cout << "case5" << std::endl;
0240           //std::cout << itr->first << std::endl;
0241           std::set<int>& beforeIds = itr->second;
0242           ++itr;
0243           evaluateInterval_(outputContainer, beforeIds, ids, leadingEdge);
0244         }
0245         //print();
0246         //merge the bottom interval with the one below if they have the same count
0247         if(lowItr != scanData_.begin()){
0248           //std::cout << "case6" << std::endl;
0249           typename ScanData::iterator belowLowItr = lowItr;
0250           --belowLowItr;
0251           if(belowLowItr->second == lowItr->second) {
0252             //std::cout << "case7" << std::endl;
0253             scanData_.erase(lowItr);
0254           }
0255         }
0256         //merge the top interval with the one above if they have the same count
0257         if(highItr != scanData_.begin()) {
0258           //std::cout << "case8" << std::endl;
0259           typename ScanData::iterator beforeHighItr = highItr;
0260           --beforeHighItr;
0261           if(beforeHighItr->second == highItr->second) {
0262             //std::cout << "case9" << std::endl;
0263             scanData_.erase(highItr);
0264             highItr = beforeHighItr;
0265             ++highItr;
0266           }
0267         }
0268         //print();
0269         nextItr_ = highItr;
0270       }
0271
0272 //       inline void print() const {
0273 //         for(typename ScanData::const_iterator itr = scanData_.begin(); itr != scanData_.end(); ++itr) {
0274 //           std::cout << itr->first << ": ";
0275 //           for(std::set<int>::const_iterator sitr = itr->second.begin();
0276 //               sitr != itr->second.end(); ++sitr){
0277 //             std::cout << *sitr << " ";
0278 //           }
0279 //           std::cout << std::endl;
0280 //         }
0281 //       }
0282
0283     private:
0284       inline typename ScanData::iterator lookup_(Unit pos){
0285         if(nextItr_ != scanData_.end() && nextItr_->first >= pos) {
0286           return nextItr_;
0287         }
0288         return nextItr_ = scanData_.lower_bound(pos);
0289       }
0290
0291       inline typename ScanData::iterator insert_(Unit pos, const std::set<int>& ids){
0292         //std::cout << "inserting " << ids.size() << " ids at: " << pos << std::endl;
0293         return nextItr_ = scanData_.insert(nextItr_, std::pair<Unit, std::set<int> >(pos, ids));
0294       }
0295
0296       template <typename graphT>
0297       inline void evaluateInterval_(graphT& outputContainer, std::set<int>& ids,
0298                                     const std::set<int>& changingIds, bool leadingEdge) {
0299         for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
0300           //std::cout << "evaluateInterval " << (*ciditr) << std::endl;
0301           evaluateId_(outputContainer, ids, *ciditr, leadingEdge);
0302         }
0303       }
0304       template <typename graphT>
0305       inline void evaluateBorder_(graphT& outputContainer, const std::set<int>& ids, const std::set<int>& changingIds) {
0306         for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
0307           //std::cout << "evaluateBorder " << (*ciditr) << std::endl;
0308           evaluateBorderId_(outputContainer, ids, *ciditr);
0309         }
0310       }
0311       template <typename graphT>
0312       inline void evaluateBorderId_(graphT& outputContainer, const std::set<int>& ids, int changingId) {
0313         for(std::set<int>::const_iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
0314           //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
0315           if(changingId != *scanItr){
0316             outputContainer[changingId].insert(*scanItr);
0317             outputContainer[*scanItr].insert(changingId);
0318           }
0319         }
0320       }
0321       template <typename graphT>
0322       inline void evaluateId_(graphT& outputContainer, std::set<int>& ids, int changingId, bool leadingEdge) {
0323         //std::cout << "changingId: " << changingId << std::endl;
0324         //for( std::set<int>::iterator itr = ids.begin(); itr != ids.end(); ++itr){
0325         //   std::cout << *itr << " ";
0326         //}std::cout << std::endl;
0327         std::set<int>::iterator lb = ids.lower_bound(changingId);
0328         if(lb == ids.end() || (*lb) != changingId) {
0329           if(leadingEdge) {
0330             //std::cout << "insert\n";
0331             //insert and add to output
0332             for(std::set<int>::iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
0333               //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
0334               if(changingId != *scanItr){
0335                 outputContainer[changingId].insert(*scanItr);
0336                 outputContainer[*scanItr].insert(changingId);
0337               }
0338             }
0339             ids.insert(changingId);
0340           }
0341         } else {
0342           if(!leadingEdge){
0343             //std::cout << "erase\n";
0344             ids.erase(lb);
0345           }
0346         }
0347       }
0348     };
0349
0350     template <typename graphT>
0351     static inline void processEvent(graphT& outputContainer, TouchOp& op, const TouchScanEvent& data, bool leadingEdge) {
0352       for(typename TouchScanEvent::iterator itr = data.begin(); itr != data.end(); ++itr) {
0353         //std::cout << "processInterval" << std::endl;
0354         op.processInterval(outputContainer, (*itr).first, (*itr).second, leadingEdge);
0355       }
0356     }
0357
0358     template <typename graphT>
0359     static inline void performTouch(graphT& outputContainer, const TouchSetData& data) {
0360       typename std::map<Unit, TouchScanEvent>::const_iterator leftItr = data.first.begin();
0361       typename std::map<Unit, TouchScanEvent>::const_iterator rightItr = data.second.begin();
0362       typename std::map<Unit, TouchScanEvent>::const_iterator leftEnd = data.first.end();
0363       typename std::map<Unit, TouchScanEvent>::const_iterator rightEnd = data.second.end();
0364       TouchOp op;
0365       while(leftItr != leftEnd || rightItr != rightEnd) {
0366         //std::cout << "loop" << std::endl;
0367         op.advanceScan();
0368         //rightItr cannont be at end if leftItr is not at end
0369         if(leftItr != leftEnd && rightItr != rightEnd &&
0370            leftItr->first <= rightItr->first) {
0371           //std::cout << "case1" << std::endl;
0372           //std::cout << leftItr ->first << std::endl;
0373           processEvent(outputContainer, op, leftItr->second, true);
0374           ++leftItr;
0375         } else {
0376           //std::cout << "case2" << std::endl;
0377           //std::cout << rightItr ->first << std::endl;
0378           processEvent(outputContainer, op, rightItr->second, false);
0379           ++rightItr;
0380         }
0381       }
0382     }
0383
0384     template <class iT>
0385     static inline void populateTouchSetData(TouchSetData& data, iT beginData, iT endData, int id) {
0386       Unit prevPos = ((std::numeric_limits<Unit>::max)());
0387       Unit prevY = prevPos;
0388       int count = 0;
0389       for(iT itr = beginData; itr != endData; ++itr) {
0390         Unit pos = (*itr).first;
0391         if(pos != prevPos) {
0392           prevPos = pos;
0393           prevY = (*itr).second.first;
0394           count = (*itr).second.second;
0395           continue;
0396         }
0397         Unit y = (*itr).second.first;
0398         if(count != 0 && y != prevY) {
0399           std::pair<Interval, int> element(Interval(prevY, y), id);
0400           if(count > 0) {
0401             data.first[pos].insert(element);
0402           } else {
0403             data.second[pos].insert(element);
0404           }
0405         }
0406         prevY = y;
0407         count += (*itr).second.second;
0408       }
0409     }
0410
0411     static inline void populateTouchSetData(TouchSetData& data, const std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputData, int id) {
0412       populateTouchSetData(data, inputData.begin(), inputData.end(), id);
0413     }
0414
0415   };
0416 }
0417 }
0418 #endif