| /* | |
| Copyright 2008 Intel Corporation | |
| Use, modification and distribution are subject to the Boost Software License, | |
| Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
| http://www.boost.org/LICENSE_1_0.txt). | |
| */ | |
| #ifndef BOOST_POLYGON_BOOLEAN_OP_HPP | |
| #define BOOST_POLYGON_BOOLEAN_OP_HPP | |
| namespace boost { namespace polygon{ | |
| namespace boolean_op { | |
| //BooleanOp is the generic boolean operation scanline algorithm that provides | |
| //all the simple boolean set operations on manhattan data. By templatizing | |
| //the intersection count of the input and algorithm internals it is extensible | |
| //to multi-layer scans, properties and other advanced scanline operations above | |
| //and beyond simple booleans. | |
| //T must cast to int | |
| template <class T, typename Unit> | |
| class BooleanOp { | |
| public: | |
| typedef std::map<Unit, T> ScanData; | |
| typedef std::pair<Unit, T> ElementType; | |
| protected: | |
| ScanData scanData_; | |
| typename ScanData::iterator nextItr_; | |
| T nullT_; | |
| public: | |
| inline BooleanOp () : scanData_(), nextItr_(), nullT_() { nextItr_ = scanData_.end(); nullT_ = 0; } | |
| inline BooleanOp (T nullT) : scanData_(), nextItr_(), nullT_(nullT) { nextItr_ = scanData_.end(); } | |
| inline BooleanOp (const BooleanOp& that) : scanData_(that.scanData_), nextItr_(), | |
| nullT_(that.nullT_) { nextItr_ = scanData_.begin(); } | |
| inline BooleanOp& operator=(const BooleanOp& that); | |
| //moves scanline forward | |
| inline void advanceScan() { nextItr_ = scanData_.begin(); } | |
| //proceses the given interval and T data | |
| //appends output edges to cT | |
| template <class cT> | |
| inline void processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount); | |
| private: | |
| inline typename ScanData::iterator lookup_(Unit pos){ | |
| if(nextItr_ != scanData_.end() && nextItr_->first >= pos) { | |
| return nextItr_; | |
| } | |
| return nextItr_ = scanData_.lower_bound(pos); | |
| } | |
| inline typename ScanData::iterator insert_(Unit pos, T count){ | |
| return nextItr_ = scanData_.insert(nextItr_, ElementType(pos, count)); | |
| } | |
| template <class cT> | |
| inline void evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl, T beforeCount, T afterCount); | |
| }; | |
| class BinaryAnd { | |
| public: | |
| inline BinaryAnd() {} | |
| inline bool operator()(int a, int b) { return (a > 0) & (b > 0); } | |
| }; | |
| class BinaryOr { | |
| public: | |
| inline BinaryOr() {} | |
| inline bool operator()(int a, int b) { return (a > 0) | (b > 0); } | |
| }; | |
| class BinaryNot { | |
| public: | |
| inline BinaryNot() {} | |
| inline bool operator()(int a, int b) { return (a > 0) & !(b > 0); } | |
| }; | |
| class BinaryXor { | |
| public: | |
| inline BinaryXor() {} | |
| inline bool operator()(int a, int b) { return (a > 0) ^ (b > 0); } | |
| }; | |
| //BinaryCount is an array of two deltaCounts coming from two different layers | |
| //of scan event data. It is the merged count of the two suitable for consumption | |
| //as the template argument of the BooleanOp algorithm because BinaryCount casts to int. | |
| //T is a binary functor object that evaluates the array of counts and returns a logical | |
| //result of some operation on those values. | |
| //BinaryCount supports many of the operators that work with int, particularly the | |
| //binary operators, but cannot support less than or increment. | |
| template <class T> | |
| class BinaryCount { | |
| public: | |
| inline BinaryCount() | |
| #ifndef BOOST_POLYGON_MSVC | |
| : counts_() | |
| #endif | |
| { counts_[0] = counts_[1] = 0; } | |
| // constructs from two integers | |
| inline BinaryCount(int countL, int countR) | |
| #ifndef BOOST_POLYGON_MSVC | |
| : counts_() | |
| #endif | |
| { counts_[0] = countL, counts_[1] = countR; } | |
| inline BinaryCount& operator=(int count) { counts_[0] = count, counts_[1] = count; return *this; } | |
| inline BinaryCount& operator=(const BinaryCount& that); | |
| inline BinaryCount(const BinaryCount& that) | |
| #ifndef BOOST_POLYGON_MSVC | |
| : counts_() | |
| #endif | |
| { *this = that; } | |
| inline bool operator==(const BinaryCount& that) const; | |
| inline bool operator!=(const BinaryCount& that) const { return !((*this) == that);} | |
| inline BinaryCount& operator+=(const BinaryCount& that); | |
| inline BinaryCount& operator-=(const BinaryCount& that); | |
| inline BinaryCount operator+(const BinaryCount& that) const; | |
| inline BinaryCount operator-(const BinaryCount& that) const; | |
| inline BinaryCount operator-() const; | |
| inline int& operator[](bool index) { return counts_[index]; } | |
| //cast to int operator evaluates data using T binary functor | |
| inline operator int() const { return T()(counts_[0], counts_[1]); } | |
| private: | |
| int counts_[2]; | |
| }; | |
| class UnaryCount { | |
| public: | |
| inline UnaryCount() : count_(0) {} | |
| // constructs from two integers | |
| inline explicit UnaryCount(int count) : count_(count) {} | |
| inline UnaryCount& operator=(int count) { count_ = count; return *this; } | |
| inline UnaryCount& operator=(const UnaryCount& that) { count_ = that.count_; return *this; } | |
| inline UnaryCount(const UnaryCount& that) : count_(that.count_) {} | |
| inline bool operator==(const UnaryCount& that) const { return count_ == that.count_; } | |
| inline bool operator!=(const UnaryCount& that) const { return !((*this) == that);} | |
| inline UnaryCount& operator+=(const UnaryCount& that) { count_ += that.count_; return *this; } | |
| inline UnaryCount& operator-=(const UnaryCount& that) { count_ -= that.count_; return *this; } | |
| inline UnaryCount operator+(const UnaryCount& that) const { UnaryCount tmp(*this); tmp += that; return tmp; } | |
| inline UnaryCount operator-(const UnaryCount& that) const { UnaryCount tmp(*this); tmp -= that; return tmp; } | |
| inline UnaryCount operator-() const { UnaryCount tmp; return tmp - *this; } | |
| //cast to int operator evaluates data using T binary functor | |
| inline operator int() const { return count_ % 2; } | |
| private: | |
| int count_; | |
| }; | |
| template <class T, typename Unit> | |
| inline BooleanOp<T, Unit>& BooleanOp<T, Unit>::operator=(const BooleanOp& that) { | |
| scanData_ = that.scanData_; | |
| nextItr_ = scanData_.begin(); | |
| nullT_ = that.nullT_; | |
| return *this; | |
| } | |
| //appends output edges to cT | |
| template <class T, typename Unit> | |
| template <class cT> | |
| inline void BooleanOp<T, Unit>::processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount) { | |
| typename ScanData::iterator lowItr = lookup_(ivl.low()); | |
| typename ScanData::iterator highItr = lookup_(ivl.high()); | |
| //add interval to scan data if it is past the end | |
| if(lowItr == scanData_.end()) { | |
| lowItr = insert_(ivl.low(), deltaCount); | |
| highItr = insert_(ivl.high(), nullT_); | |
| evaluateInterval_(outputContainer, ivl, nullT_, deltaCount); | |
| return; | |
| } | |
| //ensure that highItr points to the end of the ivl | |
| if(highItr == scanData_.end() || (*highItr).first > ivl.high()) { | |
| T value = nullT_; | |
| if(highItr != scanData_.begin()) { | |
| --highItr; | |
| value = highItr->second; | |
| } | |
| nextItr_ = highItr; | |
| highItr = insert_(ivl.high(), value); | |
| } | |
| //split the low interval if needed | |
| if(lowItr->first > ivl.low()) { | |
| if(lowItr != scanData_.begin()) { | |
| --lowItr; | |
| nextItr_ = lowItr; | |
| lowItr = insert_(ivl.low(), lowItr->second); | |
| } else { | |
| nextItr_ = lowItr; | |
| lowItr = insert_(ivl.low(), nullT_); | |
| } | |
| } | |
| //process scan data intersecting interval | |
| for(typename ScanData::iterator itr = lowItr; itr != highItr; ){ | |
| T beforeCount = itr->second; | |
| T afterCount = itr->second += deltaCount; | |
| Unit low = itr->first; | |
| ++itr; | |
| Unit high = itr->first; | |
| evaluateInterval_(outputContainer, interval_data<Unit>(low, high), beforeCount, afterCount); | |
| } | |
| //merge the bottom interval with the one below if they have the same count | |
| if(lowItr != scanData_.begin()){ | |
| typename ScanData::iterator belowLowItr = lowItr; | |
| --belowLowItr; | |
| if(belowLowItr->second == lowItr->second) { | |
| scanData_.erase(lowItr); | |
| } | |
| } | |
| //merge the top interval with the one above if they have the same count | |
| if(highItr != scanData_.begin()) { | |
| typename ScanData::iterator beforeHighItr = highItr; | |
| --beforeHighItr; | |
| if(beforeHighItr->second == highItr->second) { | |
| scanData_.erase(highItr); | |
| highItr = beforeHighItr; | |
| ++highItr; | |
| } | |
| } | |
| nextItr_ = highItr; | |
| } | |
| template <class T, typename Unit> | |
| template <class cT> | |
| inline void BooleanOp<T, Unit>::evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl, | |
| T beforeCount, T afterCount) { | |
| bool before = (int)beforeCount > 0; | |
| bool after = (int)afterCount > 0; | |
| int value = (!before & after) - (before & !after); | |
| if(value) { | |
| outputContainer.insert(outputContainer.end(), std::pair<interval_data<Unit>, int>(ivl, value)); | |
| } | |
| } | |
| template <class T> | |
| inline BinaryCount<T>& BinaryCount<T>::operator=(const BinaryCount<T>& that) { | |
| counts_[0] = that.counts_[0]; | |
| counts_[1] = that.counts_[1]; | |
| return *this; | |
| } | |
| template <class T> | |
| inline bool BinaryCount<T>::operator==(const BinaryCount<T>& that) const { | |
| return counts_[0] == that.counts_[0] && | |
| counts_[1] == that.counts_[1]; | |
| } | |
| template <class T> | |
| inline BinaryCount<T>& BinaryCount<T>::operator+=(const BinaryCount<T>& that) { | |
| counts_[0] += that.counts_[0]; | |
| counts_[1] += that.counts_[1]; | |
| return *this; | |
| } | |
| template <class T> | |
| inline BinaryCount<T>& BinaryCount<T>::operator-=(const BinaryCount<T>& that) { | |
| counts_[0] += that.counts_[0]; | |
| counts_[1] += that.counts_[1]; | |
| return *this; | |
| } | |
| template <class T> | |
| inline BinaryCount<T> BinaryCount<T>::operator+(const BinaryCount<T>& that) const { | |
| BinaryCount retVal(*this); | |
| retVal += that; | |
| return retVal; | |
| } | |
| template <class T> | |
| inline BinaryCount<T> BinaryCount<T>::operator-(const BinaryCount<T>& that) const { | |
| BinaryCount retVal(*this); | |
| retVal -= that; | |
| return retVal; | |
| } | |
| template <class T> | |
| inline BinaryCount<T> BinaryCount<T>::operator-() const { | |
| return BinaryCount<T>() - *this; | |
| } | |
| template <class T, typename Unit, typename iterator_type_1, typename iterator_type_2> | |
| inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& output, | |
| //const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input1, | |
| //const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2, | |
| iterator_type_1 itr1, iterator_type_1 itr1_end, | |
| iterator_type_2 itr2, iterator_type_2 itr2_end, | |
| T defaultCount) { | |
| BooleanOp<T, Unit> boolean(defaultCount); | |
| //typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr1 = input1.begin(); | |
| //typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr2 = input2.begin(); | |
| std::vector<std::pair<interval_data<Unit>, int> > container; | |
| //output.reserve((std::max)(input1.size(), input2.size())); | |
| //consider eliminating dependecy on limits with bool flag for initial state | |
| Unit UnitMax = (std::numeric_limits<Unit>::max)(); | |
| Unit prevCoord = UnitMax; | |
| Unit prevPosition = UnitMax; | |
| T count(defaultCount); | |
| //define the starting point | |
| if(itr1 != itr1_end) { | |
| prevCoord = (*itr1).first; | |
| prevPosition = (*itr1).second.first; | |
| count[0] += (*itr1).second.second; | |
| } | |
| if(itr2 != itr2_end) { | |
| if((*itr2).first < prevCoord || | |
| ((*itr2).first == prevCoord && (*itr2).second.first < prevPosition)) { | |
| prevCoord = (*itr2).first; | |
| prevPosition = (*itr2).second.first; | |
| count = defaultCount; | |
| count[1] += (*itr2).second.second; | |
| ++itr2; | |
| } else if((*itr2).first == prevCoord && (*itr2).second.first == prevPosition) { | |
| count[1] += (*itr2).second.second; | |
| ++itr2; | |
| if(itr1 != itr1_end) ++itr1; | |
| } else { | |
| if(itr1 != itr1_end) ++itr1; | |
| } | |
| } else { | |
| if(itr1 != itr1_end) ++itr1; | |
| } | |
| while(itr1 != itr1_end || itr2 != itr2_end) { | |
| Unit curCoord = UnitMax; | |
| Unit curPosition = UnitMax; | |
| T curCount(defaultCount); | |
| if(itr1 != itr1_end) { | |
| curCoord = (*itr1).first; | |
| curPosition = (*itr1).second.first; | |
| curCount[0] += (*itr1).second.second; | |
| } | |
| if(itr2 != itr2_end) { | |
| if((*itr2).first < curCoord || | |
| ((*itr2).first == curCoord && (*itr2).second.first < curPosition)) { | |
| curCoord = (*itr2).first; | |
| curPosition = (*itr2).second.first; | |
| curCount = defaultCount; | |
| curCount[1] += (*itr2).second.second; | |
| ++itr2; | |
| } else if((*itr2).first == curCoord && (*itr2).second.first == curPosition) { | |
| curCount[1] += (*itr2).second.second; | |
| ++itr2; | |
| if(itr1 != itr1_end) ++itr1; | |
| } else { | |
| if(itr1 != itr1_end) ++itr1; | |
| } | |
| } else { | |
| ++itr1; | |
| } | |
| if(prevCoord != curCoord) { | |
| boolean.advanceScan(); | |
| prevCoord = curCoord; | |
| prevPosition = curPosition; | |
| count = curCount; | |
| continue; | |
| } | |
| if(curPosition != prevPosition && count != defaultCount) { | |
| interval_data<Unit> ivl(prevPosition, curPosition); | |
| container.clear(); | |
| boolean.processInterval(container, ivl, count); | |
| for(std::size_t i = 0; i < container.size(); ++i) { | |
| std::pair<interval_data<Unit>, int>& element = container[i]; | |
| if(!output.empty() && output.back().first == prevCoord && | |
| output.back().second.first == element.first.low() && | |
| output.back().second.second == element.second * -1) { | |
| output.pop_back(); | |
| } else { | |
| output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.low(), | |
| element.second))); | |
| } | |
| output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.high(), | |
| element.second * -1))); | |
| } | |
| } | |
| prevPosition = curPosition; | |
| count += curCount; | |
| } | |
| } | |
| template <class T, typename Unit> | |
| inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputOutput, | |
| const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2, | |
| T defaultCount) { | |
| std::vector<std::pair<Unit, std::pair<Unit, int> > > output; | |
| applyBooleanBinaryOp(output, inputOutput, input2, defaultCount); | |
| if(output.size() < inputOutput.size() / 2) { | |
| inputOutput = std::vector<std::pair<Unit, std::pair<Unit, int> > >(); | |
| } else { | |
| inputOutput.clear(); | |
| } | |
| inputOutput.insert(inputOutput.end(), output.begin(), output.end()); | |
| } | |
| template <typename Unit> | |
| inline void applyUnaryXOr(std::vector<std::pair<Unit, std::pair<Unit, int> > >& input) { | |
| BooleanOp<UnaryCount, Unit> booleanXOr; | |
| } | |
| template <typename count_type = int> | |
| struct default_arg_workaround { | |
| template <typename Unit> | |
| static inline void applyBooleanOr(std::vector<std::pair<Unit, std::pair<Unit, int> > >& input) { | |
| BooleanOp<count_type, Unit> booleanOr; | |
| std::vector<std::pair<interval_data<Unit>, int> > container; | |
| std::vector<std::pair<Unit, std::pair<Unit, int> > > output; | |
| output.reserve(input.size()); | |
| //consider eliminating dependecy on limits with bool flag for initial state | |
| Unit UnitMax = (std::numeric_limits<Unit>::max)(); | |
| Unit prevPos = UnitMax; | |
| Unit prevY = UnitMax; | |
| int count = 0; | |
| for(typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::iterator itr = input.begin(); | |
| itr != input.end(); ++itr) { | |
| Unit pos = (*itr).first; | |
| Unit y = (*itr).second.first; | |
| if(pos != prevPos) { | |
| booleanOr.advanceScan(); | |
| prevPos = pos; | |
| prevY = y; | |
| count = (*itr).second.second; | |
| continue; | |
| } | |
| if(y != prevY && count != 0) { | |
| interval_data<Unit> ivl(prevY, y); | |
| container.clear(); | |
| booleanOr.processInterval(container, ivl, count_type(count)); | |
| for(std::size_t i = 0; i < container.size(); ++i) { | |
| std::pair<interval_data<Unit>, int>& element = container[i]; | |
| if(!output.empty() && output.back().first == prevPos && | |
| output.back().second.first == element.first.low() && | |
| output.back().second.second == element.second * -1) { | |
| output.pop_back(); | |
| } else { | |
| output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.low(), | |
| element.second))); | |
| } | |
| output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.high(), | |
| element.second * -1))); | |
| } | |
| } | |
| prevY = y; | |
| count += (*itr).second.second; | |
| } | |
| if(output.size() < input.size() / 2) { | |
| input = std::vector<std::pair<Unit, std::pair<Unit, int> > >(); | |
| } else { | |
| input.clear(); | |
| } | |
| input.insert(input.end(), output.begin(), output.end()); | |
| } | |
| }; | |
| } | |
| } | |
| } | |
| #endif |