Gnash 0.8.10dev
|
00001 // 00002 // Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. 00003 // 00004 // This program is free software; you can redistribute it and/or modify 00005 // it under the terms of the GNU General Public License as published by 00006 // the Free Software Foundation; either version 3 of the License, or 00007 // (at your option) any later version. 00008 // 00009 // This program is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 // GNU General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with this program; if not, write to the Free Software 00016 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00017 // 00018 00019 #ifndef GNASH_SNAPPINGRANGE_H 00020 #define GNASH_SNAPPINGRANGE_H 00021 00022 #include "Range2d.h" 00023 00024 #include <vector> 00025 #include <iterator> 00026 #include <algorithm> 00027 #include <ostream> 00028 #include <boost/cstdint.hpp> 00029 00030 namespace gnash { 00031 00032 namespace geometry { 00033 00038 // 00068 00069 // Forward declarations. 00070 namespace { 00071 00073 template<typename T> inline bool snaptest( 00074 const geometry::Range2d<T>& range1, 00075 const geometry::Range2d<T>& range2, const float snapFactor); 00076 } 00077 00078 template <typename T> 00079 class SnappingRanges2d 00080 { 00081 public: 00082 typedef geometry::Range2d<T> RangeType; 00083 typedef std::vector<RangeType> RangeList; 00084 typedef typename RangeList::size_type size_type; 00085 00086 template<typename U> friend std::ostream& operator<<(std::ostream& os, 00087 const SnappingRanges2d<U>& r); 00088 00089 SnappingRanges2d() 00090 : 00091 _snapFactor(1.3f), 00092 _singleMode(false), 00093 _rangesLimit(50), 00094 _combineCounter(0) 00095 { 00096 } 00097 00099 template <typename U> 00100 SnappingRanges2d(const SnappingRanges2d<U>& from) 00101 : 00102 _snapFactor(from.getSnapFactor()), 00103 _singleMode(from.getSingleMode()), 00104 _rangesLimit(from.getRangeCountLimit()), 00105 _combineCounter(0) 00106 { 00107 if (from.isWorld()) setWorld(); 00108 else if (from.isNull()) setNull(); 00109 else { 00110 // TODO: can we safely assume that the 'from' parameter was 00111 // finalized ? 00112 00113 // TODO: use visitor pattern ! 00114 for (size_type i = 0, e = from.size(); i != e; ++i) { 00115 const Range2d<U>& r = from.getRange(i); 00116 RangeType rc(r); 00117 add(rc); 00118 } 00119 } 00120 } 00121 00124 void setSnapFactor(const float factor) { 00125 assert(factor > 1.0f); 00126 _snapFactor = factor; 00127 } 00128 00129 float getSnapFactor() const { 00130 return _snapFactor; 00131 } 00132 00134 void setSingleMode(const bool mode) { 00135 _singleMode = mode; 00136 } 00137 00138 bool getSingleMode() const { 00139 return _singleMode; 00140 } 00141 00144 void setRangeCountLimit(const size_type limit) { 00145 _rangesLimit = limit; 00146 } 00147 00148 size_type getRangeCountLimit() const { 00149 return _rangesLimit; 00150 } 00151 00154 void inheritConfig(const SnappingRanges2d<T>& from) { 00155 _snapFactor = from._snapFactor; 00156 _singleMode = from._singleMode; 00157 } 00158 00160 struct ExpandToIfSnap 00161 { 00162 public: 00163 ExpandToIfSnap(const RangeType& rt, const float snapFactor) 00164 : 00165 _rt(rt), 00166 _snapFactor(snapFactor) 00167 {} 00168 00169 bool operator()(RangeType& r) { 00170 if (snaptest(r, _rt, _snapFactor)) { 00171 r.expandTo(_rt); 00172 return false; 00173 } 00174 return true; 00175 } 00176 private: 00177 const RangeType& _rt; 00178 const float _snapFactor; 00179 }; 00180 00181 class Scale 00182 { 00183 public: 00184 Scale(const float scale) : _scale(scale) {} 00185 void operator()(RangeType& r) { 00186 r.scale(_scale); 00187 } 00188 private: 00189 const float _scale; 00190 }; 00191 00192 class GrowBy 00193 { 00194 public: 00195 GrowBy(const float factor) : _factor(factor) {} 00196 void operator()(RangeType& r) { 00197 r.growBy(_factor); 00198 } 00199 private: 00200 const float _factor; 00201 }; 00202 00203 class AddTo 00204 { 00205 public: 00206 AddTo(SnappingRanges2d<T>& us) : _this(us) {} 00207 void operator()(const RangeType& r) { 00208 _this.add(r); 00209 } 00210 private: 00211 SnappingRanges2d<T>& _this; 00212 }; 00213 00214 class IntersectsRange 00215 { 00216 public: 00217 IntersectsRange(const RangeType& range) : _range(range) {} 00218 bool operator()(const RangeType& us) { 00219 return us.intersects(_range); 00220 } 00221 private: 00222 const RangeType& _range; 00223 }; 00224 00225 class ContainsPoint 00226 { 00227 public: 00228 ContainsPoint(const T x, const T y) : _x(x), _y(y) {} 00229 bool operator()(const RangeType& us) { 00230 return us.contains(_x, _y); 00231 } 00232 private: 00233 const T _x, _y; 00234 }; 00235 00236 class ContainsRange 00237 { 00238 public: 00239 ContainsRange(const RangeType& range) : _range(range) {} 00240 bool operator()(const RangeType& us) { 00241 return us.contains(_range); 00242 } 00243 private: 00244 const RangeType& _range; 00245 }; 00246 00247 00249 void add(const RangeType& range) { 00250 if (range.isWorld()) { 00251 setWorld(); 00252 return; 00253 } 00254 00255 if (range.isNull()) return; 00256 00257 if (_singleMode) { 00258 if (_ranges.empty()) _ranges.resize(1); 00259 _ranges[0].expandTo(range); 00260 return; 00261 } 00262 00263 ExpandToIfSnap exp(range, _snapFactor); 00264 if (visit(exp)) return; 00265 00266 // reached this point we need a new range 00267 _ranges.push_back(range); 00268 00269 combineRangesLazy(); 00270 } 00271 00273 void add(const SnappingRanges2d<T>& other) { 00274 const RangeList& rl = other._ranges; 00275 std::for_each(rl.begin(), rl.end(), AddTo(*this)); 00276 } 00277 00279 void growBy(const T amount) { 00280 00281 if (isWorld() || isNull()) return; 00282 00283 std::for_each(_ranges.begin(), _ranges.end(), GrowBy(amount)); 00284 combineRangesLazy(); 00285 } 00286 00288 void scale(const float factor) { 00289 00290 if (isWorld() || isNull()) return; 00291 00292 std::for_each(_ranges.begin(), _ranges.end(), Scale(factor)); 00293 combineRangesLazy(); 00294 } 00295 00297 void setNull() { 00298 _ranges.clear(); 00299 } 00300 00302 void setWorld() { 00303 if (isWorld()) return; 00304 _ranges.resize(1); 00305 _ranges[0].setWorld(); 00306 } 00307 00309 bool isWorld() const { 00310 return ((size()==1) && (_ranges.front().isWorld())); 00311 } 00312 00314 bool isNull() const { 00315 return _ranges.empty(); 00316 } 00317 00319 size_type size() const { 00320 finalize(); 00321 return _ranges.size(); 00322 } 00323 00325 const RangeType& getRange(size_type index) const { 00326 finalize(); 00327 assert(index<size()); 00328 return _ranges[index]; 00329 } 00330 00333 RangeType getFullArea() const { 00334 RangeType range; 00335 00336 range.setNull(); 00337 00338 int rcount = _ranges.size(); 00339 00340 for (int rno=0; rno<rcount; rno++) 00341 range.expandTo(_ranges[rno]); 00342 00343 return range; 00344 } 00345 00346 00348 // 00352 bool intersects(const RangeType& r) const { 00353 00354 finalize(); 00355 return std::find_if(_ranges.begin(), _ranges.end(), IntersectsRange(r)) 00356 != _ranges.end(); 00357 } 00358 00360 bool contains(T x, T y) const { 00361 00362 finalize(); 00363 return std::find_if(_ranges.begin(), _ranges.end(), ContainsPoint(x, y)) 00364 != _ranges.end(); 00365 } 00366 00368 // 00372 bool contains(const RangeType& r) const { 00373 00374 finalize(); 00375 return std::find_if(_ranges.begin(), _ranges.end(), ContainsRange(r)) 00376 != _ranges.end(); 00377 } 00378 00387 bool contains(const SnappingRanges2d<T>& o) const 00388 { 00389 00390 finalize(); 00391 // o.finalize(); // should I finalize the other range too ? 00392 00393 // Null range set doesn't contain and isn't contained by anything 00394 if ( isNull() ) return false; 00395 if ( o.isNull() ) return false; 00396 00397 // World range contains everything (except null ranges) 00398 if ( isWorld() ) return true; 00399 00400 // This snappingrange is neither NULL nor WORLD 00401 // The other can still be WORLD, but in that case the 00402 // first iteration would return false 00403 // 00405 for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) 00406 { 00407 RangeType r = o.getRange(rno); 00408 if ( ! contains(r) ) 00409 { 00410 return false; 00411 } 00412 } 00413 00414 return true; 00415 00416 } 00417 00418 00424 void intersect(const SnappingRanges2d<T>& o) 00425 { 00426 if (o.isNull()) { 00427 setNull(); 00428 return; 00429 } 00430 00431 if (o.isWorld()) return; 00432 00433 // We create a new ranges set for each range in "o" and 00434 // then update ourselves with the *union* of these ranges. 00435 // Anybody knows a better method (in terms of efficieny) ? 00436 00437 std::vector<SnappingRanges2d<T> > list; 00438 list.reserve(o.size()); 00439 00440 //TODO: use a visitor ! 00441 for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) { 00442 00443 // add a copy of ourselves to the list 00444 list.push_back(*this); 00445 00446 // intersect that copy with the single range 00447 list.back().intersect(o.getRange(rno)); 00448 00449 } 00450 00451 // update ourselves with the union of the "list" 00452 setNull(); 00453 for (size_type lno=0, lcount=list.size(); lno<lcount; lno++) { 00454 add(list[lno]); 00455 } 00456 00457 } 00458 00459 00462 void intersect(const RangeType& r) 00463 { 00464 00465 finalize(); 00466 00467 if (isWorld()) { // world intersection with X = X 00468 setNull(); 00469 add(r); 00470 return; 00471 } 00472 00473 if (isNull()) return; // NULL will always remain NULL 00474 00475 if (r.isNull()) { // X intersection with NULL = NULL 00476 setNull(); 00477 return; 00478 } 00479 00480 if (r.isWorld()) return; // X intersection with WORLD = X 00481 00482 // TODO: use a vector (remember to walk in reverse dir.) 00483 for (int rno=_ranges.size()-1; rno>=0; rno--) { 00484 00485 RangeType newrange = Intersection(_ranges[rno], r); 00486 00487 if (newrange.isNull()) 00488 _ranges.erase(_ranges.begin() + rno); 00489 else 00490 _ranges[rno] = newrange; 00491 } 00492 } 00493 00496 void combineRanges() const { 00497 00498 // makes no sense in single mode 00499 if (_singleMode) return; 00500 00501 bool restart = true; 00502 00503 _combineCounter = 0; 00504 00505 while (restart) { 00506 00507 int rcount = _ranges.size(); 00508 00509 restart=false; 00510 00511 for (int i=0; i<rcount; i++) { 00512 00513 for (int j=i+1; j<rcount; j++) { 00514 00515 if (snaptest(_ranges[i], _ranges[j], _snapFactor)) { 00516 // merge i + j 00517 _ranges[i].expandTo(_ranges[j]); 00518 00519 _ranges.erase(_ranges.begin() + j); 00520 00521 restart=true; // restart from beginning 00522 break; 00523 00524 } 00525 } 00526 00527 if (restart) break; 00528 } 00529 } 00530 00531 // limit number of ranges 00532 if (_ranges.size() > _rangesLimit) { 00533 00534 // We found way too much ranges, so reduce to just one single range. 00535 // We could also double the factor and try again, but that probably 00536 // won't make much difference, so we avoid the trouble... 00537 00538 RangeType single = getFullArea(); 00539 _ranges.resize(1); 00540 _ranges[0] = single; 00541 00542 } 00543 00544 } 00545 00547 // 00556 template<class V> inline bool visit(V& visitor) const 00557 { 00558 typename RangeList::iterator it, e; 00559 for (it = _ranges.begin(), e = _ranges.end(); it != e; ++it) { 00560 if (!visitor(*it)) break; 00561 } 00562 return it != _ranges.end(); 00563 } 00564 00566 // 00572 template<class V> inline void visitAll(V& visitor) const 00573 { 00574 for_each(_ranges.begin(), _ranges.end(), visitor); 00575 } 00576 00577 private: 00578 00579 00582 void combineRangesLazy() { 00583 const size_type max = 5; 00584 ++_combineCounter; 00585 if (_combineCounter > max) combineRanges(); 00586 } 00587 00588 void finalize() const { 00589 if (_combineCounter > 0) combineRanges(); 00590 } 00591 00593 // 00596 mutable RangeList _ranges; 00597 00599 float _snapFactor; 00600 00602 bool _singleMode; 00603 00605 size_type _rangesLimit; 00606 00608 mutable size_type _combineCounter; 00609 00610 }; 00611 00612 template <class T> 00613 std::ostream& 00614 operator<< (std::ostream& os, const SnappingRanges2d<T>& r) 00615 { 00616 if ( r.isNull() ) return os << "NULL"; 00617 if ( r.isWorld() ) return os << "WORLD"; 00618 00619 typedef typename SnappingRanges2d<T>::RangeList R; 00620 00621 const R& ranges = r._ranges; 00622 00623 std::copy(ranges.begin(), ranges.end(), 00624 std::ostream_iterator<typename R::value_type>(os, ",")); 00625 00626 return os; 00627 } 00628 00629 namespace { 00630 00631 template<typename T> 00632 inline bool snaptest(const geometry::Range2d<T>& range1, 00633 const geometry::Range2d<T>& range2, const float snapFactor) 00634 { 00635 00636 // when they intersect anyway, they should of course be merged! 00637 // TODO: not really, a "+" style ranges list might be worth to 00638 // remain unmerged (but needs special handling, i.e. create three 00639 // ranges out of two)... 00640 if (range1.intersects(range2)) return true; 00641 00642 geometry::Range2d<T> temp = range1; 00643 temp.expandTo(range2); 00644 00645 return (range1.getArea() + range2.getArea()) * snapFactor > 00646 temp.getArea(); 00647 00648 } 00649 00650 } // anonymous namespace 00651 } // namespace geometry 00652 00654 typedef geometry::SnappingRanges2d<boost::int32_t> InvalidatedRanges; 00655 00656 } //namespace gnash 00657 00658 #endif