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_BOOLEAN_OP_HPP
9 #define BOOST_POLYGON_BOOLEAN_OP_HPP
10 namespace boost { namespace polygon{
11 namespace boolean_op {
13 //BooleanOp is the generic boolean operation scanline algorithm that provides
14 //all the simple boolean set operations on manhattan data. By templatizing
15 //the intersection count of the input and algorithm internals it is extensible
16 //to multi-layer scans, properties and other advanced scanline operations above
17 //and beyond simple booleans.
19 template <class T, typename Unit>
22 typedef std::map<Unit, T> ScanData;
23 typedef std::pair<Unit, T> ElementType;
26 typename ScanData::iterator nextItr_;
29 inline BooleanOp () : scanData_(), nextItr_(), nullT_() { nextItr_ = scanData_.end(); nullT_ = 0; }
30 inline BooleanOp (T nullT) : scanData_(), nextItr_(), nullT_(nullT) { nextItr_ = scanData_.end(); }
31 inline BooleanOp (const BooleanOp& that) : scanData_(that.scanData_), nextItr_(),
32 nullT_(that.nullT_) { nextItr_ = scanData_.begin(); }
33 inline BooleanOp& operator=(const BooleanOp& that);
35 //moves scanline forward
36 inline void advanceScan() { nextItr_ = scanData_.begin(); }
38 //proceses the given interval and T data
39 //appends output edges to cT
41 inline void processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount);
44 inline typename ScanData::iterator lookup_(Unit pos){
45 if(nextItr_ != scanData_.end() && nextItr_->first >= pos) {
48 return nextItr_ = scanData_.lower_bound(pos);
50 inline typename ScanData::iterator insert_(Unit pos, T count){
51 return nextItr_ = scanData_.insert(nextItr_, ElementType(pos, count));
54 inline void evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl, T beforeCount, T afterCount);
60 inline bool operator()(int a, int b) { return (a > 0) & (b > 0); }
65 inline bool operator()(int a, int b) { return (a > 0) | (b > 0); }
70 inline bool operator()(int a, int b) { return (a > 0) & !(b > 0); }
75 inline bool operator()(int a, int b) { return (a > 0) ^ (b > 0); }
78 //BinaryCount is an array of two deltaCounts coming from two different layers
79 //of scan event data. It is the merged count of the two suitable for consumption
80 //as the template argument of the BooleanOp algorithm because BinaryCount casts to int.
81 //T is a binary functor object that evaluates the array of counts and returns a logical
82 //result of some operation on those values.
83 //BinaryCount supports many of the operators that work with int, particularly the
84 //binary operators, but cannot support less than or increment.
89 #ifndef BOOST_POLYGON_MSVC
92 { counts_[0] = counts_[1] = 0; }
93 // constructs from two integers
94 inline BinaryCount(int countL, int countR)
95 #ifndef BOOST_POLYGON_MSVC
98 { counts_[0] = countL, counts_[1] = countR; }
99 inline BinaryCount& operator=(int count) { counts_[0] = count, counts_[1] = count; return *this; }
100 inline BinaryCount& operator=(const BinaryCount& that);
101 inline BinaryCount(const BinaryCount& that)
102 #ifndef BOOST_POLYGON_MSVC
106 inline bool operator==(const BinaryCount& that) const;
107 inline bool operator!=(const BinaryCount& that) const { return !((*this) == that);}
108 inline BinaryCount& operator+=(const BinaryCount& that);
109 inline BinaryCount& operator-=(const BinaryCount& that);
110 inline BinaryCount operator+(const BinaryCount& that) const;
111 inline BinaryCount operator-(const BinaryCount& that) const;
112 inline BinaryCount operator-() const;
113 inline int& operator[](bool index) { return counts_[index]; }
115 //cast to int operator evaluates data using T binary functor
116 inline operator int() const { return T()(counts_[0], counts_[1]); }
123 inline UnaryCount() : count_(0) {}
124 // constructs from two integers
125 inline explicit UnaryCount(int count) : count_(count) {}
126 inline UnaryCount& operator=(int count) { count_ = count; return *this; }
127 inline UnaryCount& operator=(const UnaryCount& that) { count_ = that.count_; return *this; }
128 inline UnaryCount(const UnaryCount& that) : count_(that.count_) {}
129 inline bool operator==(const UnaryCount& that) const { return count_ == that.count_; }
130 inline bool operator!=(const UnaryCount& that) const { return !((*this) == that);}
131 inline UnaryCount& operator+=(const UnaryCount& that) { count_ += that.count_; return *this; }
132 inline UnaryCount& operator-=(const UnaryCount& that) { count_ -= that.count_; return *this; }
133 inline UnaryCount operator+(const UnaryCount& that) const { UnaryCount tmp(*this); tmp += that; return tmp; }
134 inline UnaryCount operator-(const UnaryCount& that) const { UnaryCount tmp(*this); tmp -= that; return tmp; }
135 inline UnaryCount operator-() const { UnaryCount tmp; return tmp - *this; }
137 //cast to int operator evaluates data using T binary functor
138 inline operator int() const { return count_ % 2; }
143 template <class T, typename Unit>
144 inline BooleanOp<T, Unit>& BooleanOp<T, Unit>::operator=(const BooleanOp& that) {
145 scanData_ = that.scanData_;
146 nextItr_ = scanData_.begin();
147 nullT_ = that.nullT_;
151 //appends output edges to cT
152 template <class T, typename Unit>
154 inline void BooleanOp<T, Unit>::processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount) {
155 typename ScanData::iterator lowItr = lookup_(ivl.low());
156 typename ScanData::iterator highItr = lookup_(ivl.high());
157 //add interval to scan data if it is past the end
158 if(lowItr == scanData_.end()) {
159 lowItr = insert_(ivl.low(), deltaCount);
160 highItr = insert_(ivl.high(), nullT_);
161 evaluateInterval_(outputContainer, ivl, nullT_, deltaCount);
164 //ensure that highItr points to the end of the ivl
165 if(highItr == scanData_.end() || (*highItr).first > ivl.high()) {
167 if(highItr != scanData_.begin()) {
169 value = highItr->second;
172 highItr = insert_(ivl.high(), value);
174 //split the low interval if needed
175 if(lowItr->first > ivl.low()) {
176 if(lowItr != scanData_.begin()) {
179 lowItr = insert_(ivl.low(), lowItr->second);
182 lowItr = insert_(ivl.low(), nullT_);
185 //process scan data intersecting interval
186 for(typename ScanData::iterator itr = lowItr; itr != highItr; ){
187 T beforeCount = itr->second;
188 T afterCount = itr->second += deltaCount;
189 Unit low = itr->first;
191 Unit high = itr->first;
192 evaluateInterval_(outputContainer, interval_data<Unit>(low, high), beforeCount, afterCount);
194 //merge the bottom interval with the one below if they have the same count
195 if(lowItr != scanData_.begin()){
196 typename ScanData::iterator belowLowItr = lowItr;
198 if(belowLowItr->second == lowItr->second) {
199 scanData_.erase(lowItr);
202 //merge the top interval with the one above if they have the same count
203 if(highItr != scanData_.begin()) {
204 typename ScanData::iterator beforeHighItr = highItr;
206 if(beforeHighItr->second == highItr->second) {
207 scanData_.erase(highItr);
208 highItr = beforeHighItr;
215 template <class T, typename Unit>
217 inline void BooleanOp<T, Unit>::evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl,
218 T beforeCount, T afterCount) {
219 bool before = (int)beforeCount > 0;
220 bool after = (int)afterCount > 0;
221 int value = (!before & after) - (before & !after);
223 outputContainer.insert(outputContainer.end(), std::pair<interval_data<Unit>, int>(ivl, value));
228 inline BinaryCount<T>& BinaryCount<T>::operator=(const BinaryCount<T>& that) {
229 counts_[0] = that.counts_[0];
230 counts_[1] = that.counts_[1];
234 inline bool BinaryCount<T>::operator==(const BinaryCount<T>& that) const {
235 return counts_[0] == that.counts_[0] &&
236 counts_[1] == that.counts_[1];
239 inline BinaryCount<T>& BinaryCount<T>::operator+=(const BinaryCount<T>& that) {
240 counts_[0] += that.counts_[0];
241 counts_[1] += that.counts_[1];
245 inline BinaryCount<T>& BinaryCount<T>::operator-=(const BinaryCount<T>& that) {
246 counts_[0] += that.counts_[0];
247 counts_[1] += that.counts_[1];
251 inline BinaryCount<T> BinaryCount<T>::operator+(const BinaryCount<T>& that) const {
252 BinaryCount retVal(*this);
257 inline BinaryCount<T> BinaryCount<T>::operator-(const BinaryCount<T>& that) const {
258 BinaryCount retVal(*this);
263 inline BinaryCount<T> BinaryCount<T>::operator-() const {
264 return BinaryCount<T>() - *this;
268 template <class T, typename Unit, typename iterator_type_1, typename iterator_type_2>
269 inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& output,
270 //const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input1,
271 //const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2,
272 iterator_type_1 itr1, iterator_type_1 itr1_end,
273 iterator_type_2 itr2, iterator_type_2 itr2_end,
275 BooleanOp<T, Unit> boolean(defaultCount);
276 //typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr1 = input1.begin();
277 //typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr2 = input2.begin();
278 std::vector<std::pair<interval_data<Unit>, int> > container;
279 //output.reserve((std::max)(input1.size(), input2.size()));
281 //consider eliminating dependecy on limits with bool flag for initial state
282 Unit UnitMax = (std::numeric_limits<Unit>::max)();
283 Unit prevCoord = UnitMax;
284 Unit prevPosition = UnitMax;
285 T count(defaultCount);
286 //define the starting point
287 if(itr1 != itr1_end) {
288 prevCoord = (*itr1).first;
289 prevPosition = (*itr1).second.first;
290 count[0] += (*itr1).second.second;
292 if(itr2 != itr2_end) {
293 if((*itr2).first < prevCoord ||
294 ((*itr2).first == prevCoord && (*itr2).second.first < prevPosition)) {
295 prevCoord = (*itr2).first;
296 prevPosition = (*itr2).second.first;
297 count = defaultCount;
298 count[1] += (*itr2).second.second;
300 } else if((*itr2).first == prevCoord && (*itr2).second.first == prevPosition) {
301 count[1] += (*itr2).second.second;
303 if(itr1 != itr1_end) ++itr1;
305 if(itr1 != itr1_end) ++itr1;
308 if(itr1 != itr1_end) ++itr1;
311 while(itr1 != itr1_end || itr2 != itr2_end) {
312 Unit curCoord = UnitMax;
313 Unit curPosition = UnitMax;
314 T curCount(defaultCount);
315 if(itr1 != itr1_end) {
316 curCoord = (*itr1).first;
317 curPosition = (*itr1).second.first;
318 curCount[0] += (*itr1).second.second;
320 if(itr2 != itr2_end) {
321 if((*itr2).first < curCoord ||
322 ((*itr2).first == curCoord && (*itr2).second.first < curPosition)) {
323 curCoord = (*itr2).first;
324 curPosition = (*itr2).second.first;
325 curCount = defaultCount;
326 curCount[1] += (*itr2).second.second;
328 } else if((*itr2).first == curCoord && (*itr2).second.first == curPosition) {
329 curCount[1] += (*itr2).second.second;
331 if(itr1 != itr1_end) ++itr1;
333 if(itr1 != itr1_end) ++itr1;
339 if(prevCoord != curCoord) {
340 boolean.advanceScan();
341 prevCoord = curCoord;
342 prevPosition = curPosition;
346 if(curPosition != prevPosition && count != defaultCount) {
347 interval_data<Unit> ivl(prevPosition, curPosition);
349 boolean.processInterval(container, ivl, count);
350 for(std::size_t i = 0; i < container.size(); ++i) {
351 std::pair<interval_data<Unit>, int>& element = container[i];
352 if(!output.empty() && output.back().first == prevCoord &&
353 output.back().second.first == element.first.low() &&
354 output.back().second.second == element.second * -1) {
357 output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.low(),
360 output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.high(),
361 element.second * -1)));
364 prevPosition = curPosition;
369 template <class T, typename Unit>
370 inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputOutput,
371 const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2,
373 std::vector<std::pair<Unit, std::pair<Unit, int> > > output;
374 applyBooleanBinaryOp(output, inputOutput, input2, defaultCount);
375 if(output.size() < inputOutput.size() / 2) {
376 inputOutput = std::vector<std::pair<Unit, std::pair<Unit, int> > >();
380 inputOutput.insert(inputOutput.end(), output.begin(), output.end());
383 template <typename count_type = int>
384 struct default_arg_workaround {
385 template <typename Unit>
386 static inline void applyBooleanOr(std::vector<std::pair<Unit, std::pair<Unit, int> > >& input) {
387 BooleanOp<count_type, Unit> booleanOr;
388 std::vector<std::pair<interval_data<Unit>, int> > container;
389 std::vector<std::pair<Unit, std::pair<Unit, int> > > output;
390 output.reserve(input.size());
391 //consider eliminating dependecy on limits with bool flag for initial state
392 Unit UnitMax = (std::numeric_limits<Unit>::max)();
393 Unit prevPos = UnitMax;
394 Unit prevY = UnitMax;
396 for(typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::iterator itr = input.begin();
397 itr != input.end(); ++itr) {
398 Unit pos = (*itr).first;
399 Unit y = (*itr).second.first;
401 booleanOr.advanceScan();
404 count = (*itr).second.second;
407 if(y != prevY && count != 0) {
408 interval_data<Unit> ivl(prevY, y);
410 booleanOr.processInterval(container, ivl, count_type(count));
411 for(std::size_t i = 0; i < container.size(); ++i) {
412 std::pair<interval_data<Unit>, int>& element = container[i];
413 if(!output.empty() && output.back().first == prevPos &&
414 output.back().second.first == element.first.low() &&
415 output.back().second.second == element.second * -1) {
418 output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.low(),
421 output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.high(),
422 element.second * -1)));
426 count += (*itr).second.second;
428 if(output.size() < input.size() / 2) {
429 input = std::vector<std::pair<Unit, std::pair<Unit, int> > >();
433 input.insert(input.end(), output.begin(), output.end());