• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • Examples
  • File List
  • File Members

snappingrange.h

Go to the documentation of this file.
00001 // 
00002 //   Copyright (C) 2007, 2008, 2009, 2010 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

Generated on Thu Sep 30 2010 14:35:02 for Gnash by  doxygen 1.7.1