]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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_BOOLEAN_OP_HPP | |
9 | #define BOOST_POLYGON_BOOLEAN_OP_HPP | |
10 | namespace boost { namespace polygon{ | |
11 | namespace boolean_op { | |
12 | ||
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. | |
18 | //T must cast to int | |
19 | template <class T, typename Unit> | |
20 | class BooleanOp { | |
21 | public: | |
22 | typedef std::map<Unit, T> ScanData; | |
23 | typedef std::pair<Unit, T> ElementType; | |
24 | protected: | |
25 | ScanData scanData_; | |
26 | typename ScanData::iterator nextItr_; | |
27 | T nullT_; | |
28 | public: | |
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); | |
34 | ||
35 | //moves scanline forward | |
36 | inline void advanceScan() { nextItr_ = scanData_.begin(); } | |
37 | ||
38 | //proceses the given interval and T data | |
39 | //appends output edges to cT | |
40 | template <class cT> | |
41 | inline void processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount); | |
42 | ||
43 | private: | |
44 | inline typename ScanData::iterator lookup_(Unit pos){ | |
45 | if(nextItr_ != scanData_.end() && nextItr_->first >= pos) { | |
46 | return nextItr_; | |
47 | } | |
48 | return nextItr_ = scanData_.lower_bound(pos); | |
49 | } | |
50 | inline typename ScanData::iterator insert_(Unit pos, T count){ | |
51 | return nextItr_ = scanData_.insert(nextItr_, ElementType(pos, count)); | |
52 | } | |
53 | template <class cT> | |
54 | inline void evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl, T beforeCount, T afterCount); | |
55 | }; | |
56 | ||
57 | class BinaryAnd { | |
58 | public: | |
59 | inline BinaryAnd() {} | |
60 | inline bool operator()(int a, int b) { return (a > 0) & (b > 0); } | |
61 | }; | |
62 | class BinaryOr { | |
63 | public: | |
64 | inline BinaryOr() {} | |
65 | inline bool operator()(int a, int b) { return (a > 0) | (b > 0); } | |
66 | }; | |
67 | class BinaryNot { | |
68 | public: | |
69 | inline BinaryNot() {} | |
70 | inline bool operator()(int a, int b) { return (a > 0) & !(b > 0); } | |
71 | }; | |
72 | class BinaryXor { | |
73 | public: | |
74 | inline BinaryXor() {} | |
75 | inline bool operator()(int a, int b) { return (a > 0) ^ (b > 0); } | |
76 | }; | |
77 | ||
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. | |
85 | template <class T> | |
86 | class BinaryCount { | |
87 | public: | |
88 | inline BinaryCount() | |
89 | #ifndef BOOST_POLYGON_MSVC | |
90 | : counts_() | |
91 | #endif | |
92 | { counts_[0] = counts_[1] = 0; } | |
93 | // constructs from two integers | |
94 | inline BinaryCount(int countL, int countR) | |
95 | #ifndef BOOST_POLYGON_MSVC | |
96 | : counts_() | |
97 | #endif | |
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 | |
103 | : counts_() | |
104 | #endif | |
105 | { *this = that; } | |
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]; } | |
114 | ||
115 | //cast to int operator evaluates data using T binary functor | |
116 | inline operator int() const { return T()(counts_[0], counts_[1]); } | |
117 | private: | |
118 | int counts_[2]; | |
119 | }; | |
120 | ||
121 | class UnaryCount { | |
122 | public: | |
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; } | |
136 | ||
137 | //cast to int operator evaluates data using T binary functor | |
138 | inline operator int() const { return count_ % 2; } | |
139 | private: | |
140 | int count_; | |
141 | }; | |
142 | ||
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_; | |
148 | return *this; | |
149 | } | |
150 | ||
151 | //appends output edges to cT | |
152 | template <class T, typename Unit> | |
153 | template <class cT> | |
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); | |
162 | return; | |
163 | } | |
164 | //ensure that highItr points to the end of the ivl | |
165 | if(highItr == scanData_.end() || (*highItr).first > ivl.high()) { | |
166 | T value = nullT_; | |
167 | if(highItr != scanData_.begin()) { | |
168 | --highItr; | |
169 | value = highItr->second; | |
170 | } | |
171 | nextItr_ = highItr; | |
172 | highItr = insert_(ivl.high(), value); | |
173 | } | |
174 | //split the low interval if needed | |
175 | if(lowItr->first > ivl.low()) { | |
176 | if(lowItr != scanData_.begin()) { | |
177 | --lowItr; | |
178 | nextItr_ = lowItr; | |
179 | lowItr = insert_(ivl.low(), lowItr->second); | |
180 | } else { | |
181 | nextItr_ = lowItr; | |
182 | lowItr = insert_(ivl.low(), nullT_); | |
183 | } | |
184 | } | |
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; | |
190 | ++itr; | |
191 | Unit high = itr->first; | |
192 | evaluateInterval_(outputContainer, interval_data<Unit>(low, high), beforeCount, afterCount); | |
193 | } | |
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; | |
197 | --belowLowItr; | |
198 | if(belowLowItr->second == lowItr->second) { | |
199 | scanData_.erase(lowItr); | |
200 | } | |
201 | } | |
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; | |
205 | --beforeHighItr; | |
206 | if(beforeHighItr->second == highItr->second) { | |
207 | scanData_.erase(highItr); | |
208 | highItr = beforeHighItr; | |
209 | ++highItr; | |
210 | } | |
211 | } | |
212 | nextItr_ = highItr; | |
213 | } | |
214 | ||
215 | template <class T, typename Unit> | |
216 | template <class cT> | |
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); | |
222 | if(value) { | |
223 | outputContainer.insert(outputContainer.end(), std::pair<interval_data<Unit>, int>(ivl, value)); | |
224 | } | |
225 | } | |
226 | ||
227 | template <class T> | |
228 | inline BinaryCount<T>& BinaryCount<T>::operator=(const BinaryCount<T>& that) { | |
229 | counts_[0] = that.counts_[0]; | |
230 | counts_[1] = that.counts_[1]; | |
231 | return *this; | |
232 | } | |
233 | template <class T> | |
234 | inline bool BinaryCount<T>::operator==(const BinaryCount<T>& that) const { | |
235 | return counts_[0] == that.counts_[0] && | |
236 | counts_[1] == that.counts_[1]; | |
237 | } | |
238 | template <class T> | |
239 | inline BinaryCount<T>& BinaryCount<T>::operator+=(const BinaryCount<T>& that) { | |
240 | counts_[0] += that.counts_[0]; | |
241 | counts_[1] += that.counts_[1]; | |
242 | return *this; | |
243 | } | |
244 | template <class T> | |
245 | inline BinaryCount<T>& BinaryCount<T>::operator-=(const BinaryCount<T>& that) { | |
246 | counts_[0] += that.counts_[0]; | |
247 | counts_[1] += that.counts_[1]; | |
248 | return *this; | |
249 | } | |
250 | template <class T> | |
251 | inline BinaryCount<T> BinaryCount<T>::operator+(const BinaryCount<T>& that) const { | |
252 | BinaryCount retVal(*this); | |
253 | retVal += that; | |
254 | return retVal; | |
255 | } | |
256 | template <class T> | |
257 | inline BinaryCount<T> BinaryCount<T>::operator-(const BinaryCount<T>& that) const { | |
258 | BinaryCount retVal(*this); | |
259 | retVal -= that; | |
260 | return retVal; | |
261 | } | |
262 | template <class T> | |
263 | inline BinaryCount<T> BinaryCount<T>::operator-() const { | |
264 | return BinaryCount<T>() - *this; | |
265 | } | |
266 | ||
267 | ||
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, | |
274 | T defaultCount) { | |
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())); | |
280 | ||
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; | |
291 | } | |
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; | |
299 | ++itr2; | |
300 | } else if((*itr2).first == prevCoord && (*itr2).second.first == prevPosition) { | |
301 | count[1] += (*itr2).second.second; | |
302 | ++itr2; | |
303 | if(itr1 != itr1_end) ++itr1; | |
304 | } else { | |
305 | if(itr1 != itr1_end) ++itr1; | |
306 | } | |
307 | } else { | |
308 | if(itr1 != itr1_end) ++itr1; | |
309 | } | |
310 | ||
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; | |
319 | } | |
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; | |
327 | ++itr2; | |
328 | } else if((*itr2).first == curCoord && (*itr2).second.first == curPosition) { | |
329 | curCount[1] += (*itr2).second.second; | |
330 | ++itr2; | |
331 | if(itr1 != itr1_end) ++itr1; | |
332 | } else { | |
333 | if(itr1 != itr1_end) ++itr1; | |
334 | } | |
335 | } else { | |
336 | ++itr1; | |
337 | } | |
338 | ||
339 | if(prevCoord != curCoord) { | |
340 | boolean.advanceScan(); | |
341 | prevCoord = curCoord; | |
342 | prevPosition = curPosition; | |
343 | count = curCount; | |
344 | continue; | |
345 | } | |
346 | if(curPosition != prevPosition && count != defaultCount) { | |
347 | interval_data<Unit> ivl(prevPosition, curPosition); | |
348 | container.clear(); | |
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) { | |
355 | output.pop_back(); | |
356 | } else { | |
357 | output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.low(), | |
358 | element.second))); | |
359 | } | |
360 | output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.high(), | |
361 | element.second * -1))); | |
362 | } | |
363 | } | |
364 | prevPosition = curPosition; | |
365 | count += curCount; | |
366 | } | |
367 | } | |
368 | ||
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, | |
372 | T defaultCount) { | |
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> > >(); | |
377 | } else { | |
378 | inputOutput.clear(); | |
379 | } | |
380 | inputOutput.insert(inputOutput.end(), output.begin(), output.end()); | |
381 | } | |
382 | ||
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; | |
395 | int count = 0; | |
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; | |
400 | if(pos != prevPos) { | |
401 | booleanOr.advanceScan(); | |
402 | prevPos = pos; | |
403 | prevY = y; | |
404 | count = (*itr).second.second; | |
405 | continue; | |
406 | } | |
407 | if(y != prevY && count != 0) { | |
408 | interval_data<Unit> ivl(prevY, y); | |
409 | container.clear(); | |
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) { | |
416 | output.pop_back(); | |
417 | } else { | |
418 | output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.low(), | |
419 | element.second))); | |
420 | } | |
421 | output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.high(), | |
422 | element.second * -1))); | |
423 | } | |
424 | } | |
425 | prevY = y; | |
426 | count += (*itr).second.second; | |
427 | } | |
428 | if(output.size() < input.size() / 2) { | |
429 | input = std::vector<std::pair<Unit, std::pair<Unit, int> > >(); | |
430 | } else { | |
431 | input.clear(); | |
432 | } | |
433 | input.insert(input.end(), output.begin(), output.end()); | |
434 | } | |
435 | }; | |
436 | ||
437 | } | |
438 | ||
439 | } | |
440 | ||
441 | } | |
442 | #endif |