Gnash 0.8.10dev
Range2d.h
Go to the documentation of this file.
00001 // 
00002 //   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010,
00003 //   2011 Free Software Foundation, Inc
00004 // 
00005 // This program is free software; you can redistribute it and/or modify
00006 // it under the terms of the GNU General Public License as published by
00007 // the Free Software Foundation; either version 3 of the License, or
00008 // (at your option) any later version.
00009 // 
00010 // This program is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013 // GNU General Public License for more details.
00014 // 
00015 // You should have received a copy of the GNU General Public License
00016 // along with this program; if not, write to the Free Software
00017 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00018 
00019 //
00020 // Original author: Sandro Santilli <strk@keybit.net>
00021 //
00022 
00023 
00024 
00025 #ifndef GNASH_RANGE2D_H
00026 #define GNASH_RANGE2D_H
00027 
00028 #include <ostream>
00029 #include <limits>
00030 #include <algorithm>
00031 #include <cassert> // for inlines
00032 #include <cmath> // for floor / ceil
00033 
00034 namespace gnash {
00035 
00036 namespace geometry {
00037 
00039 enum RangeKind {
00041         finiteRange,
00042 
00044         nullRange,
00045 
00049         // 
00053         worldRange
00054 };
00055 
00057 //
00070 template <typename T>
00071 class Range2d
00072 {
00073 private:
00074 
00075         T _xmin, _xmax, _ymin, _ymax;
00076 
00077         T scaleMin(T min, float scale)
00078         {
00079                 return roundMin(static_cast<float>(min) * scale);
00080         }
00081 
00082         T scaleMax(T max, float scale)
00083         {
00084                 return roundMax(static_cast<float>(max) * scale);
00085         }
00086 
00087         T roundMin(float v)
00088         {
00089                 return static_cast<T>(v);
00090         }
00091 
00092         T roundMax(float v)
00093         {
00094                 return static_cast<T>(v);
00095         }
00096 
00097 public:
00098 
00100         template <typename U>
00101         friend std::ostream& operator<< (std::ostream& os, const Range2d<U>& rect);
00102 
00104         //
00109         template <typename U>
00110         friend bool operator== (const Range2d<U>& r1, const Range2d<U>& r2);
00111 
00113         //
00118         template <typename U>
00119         friend bool operator!= (const Range2d<U>& r1, const Range2d<U>& r2);
00120 
00122         //
00125         template <typename U> friend Range2d<U>
00126         Intersection(const Range2d<U>& r1, const Range2d<U>& r2);
00127 
00129         template <typename U> friend Range2d<U>
00130         Union(const Range2d<U>& r1, const Range2d<U>& r2);
00131 
00133         //
00140         Range2d(RangeKind kind=nullRange)
00141                 :
00142                 _xmin(T()),
00143                 _xmax(T()),
00144                 _ymin(T()),
00145                 _ymax(T())
00146         {
00147                 switch ( kind )
00148                 {
00149                         case worldRange:
00150                                 setWorld();
00151                                 break;
00152                         case nullRange:
00153                                 setNull();
00154                                 break;
00155                         default:
00156                         case finiteRange:
00157                                 break;
00158                 }
00159         }
00160 
00162         //
00169         Range2d(T xmin, T ymin, T xmax, T ymax)
00170                 :
00171                 _xmin(xmin),
00172                 _xmax(xmax),
00173                 _ymin(ymin),
00174                 _ymax(ymax)
00175         {
00176                 // use the default ctor to make a NULL Range2d
00177                 assert(_xmin <= _xmax);
00178                 assert(_ymin <= _ymax);
00179                 // .. or should we raise an exception .. ?
00180         }
00181 
00183         template <typename U>
00184         Range2d(const Range2d<U>& from)
00185         {
00186                 if ( from.isWorld() ) {
00187                         setWorld();
00188                 } else if ( from.isNull() ) {
00189                         setNull();
00190                 } else {
00191                         _xmin = roundMin(from.getMinX());
00192                         _ymin = roundMin(from.getMinY());
00193                         _xmax = roundMax(from.getMaxX());
00194                         _ymax = roundMax(from.getMaxY());
00195                 }
00196         }
00197 
00199         bool isNull() const
00200         {
00201                 return _xmax < _xmin;
00202         }
00203 
00205         //
00208         Range2d<T>& setNull()
00209         {
00210                 _xmin = std::numeric_limits<T>::max();
00211                 _xmax = std::numeric_limits<T>::min();
00212                 return *this;
00213         }
00214 
00216         bool isWorld() const
00217         {
00218                 return _xmax == std::numeric_limits<T>::max()
00219                         && _xmin == std::numeric_limits<T>::min();
00220         }
00221 
00223         //
00226         bool isFinite() const
00227         {
00228                 return ( ! isNull() && ! isWorld() );
00229         }
00230 
00232         //
00240         Range2d<T>& setWorld()
00241         {
00242                 _xmin = std::numeric_limits<T>::min();
00243                 _xmax = std::numeric_limits<T>::max();
00244                 return *this;
00245         }
00246 
00250         //
00254         template <typename U>
00255         bool contains(U x, U y) const
00256         {
00257                 if ( isNull() ) return false;
00258                 if ( isWorld() ) return true;
00259                 if (x < _xmin || x > _xmax || y < _ymin || y > _ymax)
00260                 {
00261                         return false;
00262                 }
00263                 return true;
00264         }
00265 
00268         //
00276         bool contains(const Range2d<T>& other) const
00277         {
00278                 if ( isNull() || other.isNull() ) return false;
00279                 if ( isWorld() ) return true;
00280                 if ( other.isWorld() ) return false;
00281 
00282                 return _xmin <= other._xmin &&
00283                         _xmax >= other._xmax &&
00284                         _ymin <= other._ymin &&
00285                         _ymax >= other._ymax;
00286         }
00287 
00291         //
00295         bool intersects(const Range2d<T>& other) const
00296         {
00297                 if ( isNull() || other.isNull() ) return false;
00298                 if ( isWorld() || other.isWorld() ) return true;
00299 
00300                 if ( _xmin > other._xmax ) return false;
00301                 if ( _xmax < other._xmin ) return false;
00302                 if ( _ymin > other._ymax ) return false;
00303                 if ( _ymax < other._ymin ) return false;
00304                 return true;
00305         }
00306 
00308         //
00311         Range2d<T>& expandTo(T x, T y)
00312         {
00313                 // A WORLD range already enclose every point
00314                 if ( isWorld() ) return *this;
00315 
00316                 if ( isNull() ) 
00317                 {
00318                         setTo(x,y);
00319                 }
00320                 else
00321                 {
00322                         _xmin = std::min(_xmin, x);
00323                         _ymin = std::min(_ymin, y);
00324                         _xmax = std::max(_xmax, x);
00325                         _ymax = std::max(_ymax, y);
00326                 }
00327 
00328                 return *this;
00329         }
00330 
00332         //
00335         Range2d<T>& expandToCircle(T x, T y, T radius)
00336         {
00337                 // A WORLD range already enclose every point
00338                 if ( isWorld() ) return *this;
00339 
00340         expandTo(x-radius, y);
00341         expandTo(x+radius, y);
00342 
00343         expandTo(x, y-radius);
00344         expandTo(x, y+radius);
00345 
00346                 return *this;
00347         }
00348 
00350         //
00353         Range2d<T>& setTo(T x, T y)
00354         {
00355                 _xmin = _xmax = x;
00356                 _ymin = _ymax = y;
00357                 return *this;
00358         }
00359 
00361         //
00367         //
00370         Range2d<T>& setTo(T xmin, T ymin, T xmax, T ymax)
00371         {
00372                 _xmin = xmin;
00373                 _xmax = xmax;
00374                 _ymin = ymin;
00375                 _ymax = ymax;
00376 
00377                 // use the default ctor to make a NULL Range2d
00378                 assert(_xmin <= _xmax);
00379                 assert(_ymin <= _ymax);
00380 
00381                 return *this;
00382         }
00383 
00385         //
00388         T width() const
00389         {
00390                 assert ( ! isWorld() );
00391                 if ( isNull() ) return 0;
00392                 return _xmax-_xmin;
00393         }
00394 
00396         //
00399         T height() const
00400         {
00401                 assert ( ! isWorld() );
00402                 if ( isNull() ) return 0;
00403                 return _ymax-_ymin;
00404         }
00405 
00407         //
00415         Range2d<T>& shiftX(T offset)
00416         {
00417                 if ( isNull() || isWorld() ) return *this;
00418                 _xmin += offset;
00419                 _xmax += offset;
00420                 return *this;
00421         }
00422 
00424         //
00432         Range2d<T>& shiftY(T offset)
00433         {
00434                 if ( isNull() || isWorld() ) return *this;
00435                 _ymin += offset;
00436                 _ymax += offset;
00437                 return *this;
00438         }
00439 
00441         Range2d<T>& scaleX(float factor)
00442         {
00443                 return scale(factor, 1);
00444         }
00445 
00447         Range2d<T>& scaleY(float factor)
00448         {
00449                 return scale(1, factor);
00450         }
00451 
00453         //
00485         Range2d<T>& scale(float xfactor, float yfactor)
00486         {
00487                 assert(xfactor >= 0 && yfactor >= 0);
00488 
00489                 if ( ! isFinite() ) return *this;
00490 
00491                 if ( xfactor == 0 || yfactor == 0 )
00492                 {
00493                         return setNull();
00494                 }
00495 
00496                 if ( xfactor != 1 )
00497                 {
00498                         _xmin = scaleMin(_xmin, xfactor);
00499                         _xmax = scaleMax(_xmax, xfactor);
00500                         assert(_xmin <= _xmax); // in case of overflow...
00501                 }
00502 
00503                 if ( yfactor != 1 )
00504                 {
00505                         _ymin = scaleMin(_ymin, yfactor);
00506                         _ymax = scaleMax(_ymax, yfactor);
00507                         assert(_ymin <= _ymax); // in case of overflow...
00508                 }
00509 
00510                 return *this;
00511         }
00512 
00514         Range2d<T>& scale(float factor)
00515         {
00516                 return scale(factor, factor);
00517         }
00518 
00520         //
00534         Range2d<T>& growBy(T amount)
00535         {
00536                 if ( isNull() || isWorld() || amount==0 ) return *this;
00537 
00538                 // NOTE: triggers a compiler warning when T is an unsigned type
00539                 if ( amount < 0 ) return shrinkBy(-amount);
00540 
00541                 T newxmin = _xmin - amount;
00542                 if (newxmin > _xmin ) return setWorld();
00543                 else _xmin = newxmin;
00544 
00545                 T newxmax = _xmax + amount;
00546                 if (newxmax < _xmax ) return setWorld();
00547                 else _xmax = newxmax;
00548 
00549                 T newymin = _ymin - amount;
00550                 if (newymin > _ymin ) return setWorld();
00551                 else _ymin = newymin;
00552 
00553                 T newymax = _ymax + amount;
00554                 if (newymax < _ymax ) return setWorld();
00555                 else _ymax = newymax;
00556 
00557                 return *this;
00558 
00559         }
00560 
00562         //
00585         Range2d<T>& shrinkBy(T amount)
00586         {
00587                 if ( isNull() || isWorld() || amount==0 ) return *this;
00588 
00589                 // NOTE: whith will likely trigger a compiler
00590                 //       warning when T is an unsigned type
00591                 if ( amount < 0 ) return growBy(-amount);
00592 
00593                 // Turn this range into the NULL range
00594                 // if any dimension collapses.
00595                 // Don't use width() and height() to 
00596                 // avoid superflous checks.
00597 
00598                 if ( _xmax - _xmin <= amount ) return setNull();
00599                 if ( _ymax - _ymin <= amount ) return setNull();
00600 
00601                 _xmin += amount;
00602                 _ymin += amount;
00603                 _xmax -= amount;
00604                 _ymax -= amount;
00605 
00606                 return *this;
00607 
00608         }
00609 
00611         //
00614         T getMinX() const
00615         {
00616                 assert ( isFinite() );
00617                 return _xmin;
00618         }
00619 
00621         //
00624         T getMaxX() const
00625         {
00626                 assert ( isFinite() );
00627                 return _xmax;
00628         }
00629 
00631         //
00634         T getMinY() const
00635         {
00636                 assert ( isFinite() );
00637                 return _ymin;
00638         }
00639 
00641         //
00644         T getMaxY() const
00645         {
00646                 assert ( isFinite() );
00647                 return _ymax;
00648         }
00649         
00650         
00653         T getArea() const
00654   {
00655     assert ( !isWorld() );
00656     if ( isNull() ) return 0;
00657     return (_xmax - _xmin) * (_ymax - _ymin);
00658     // this implementation is for float types, see specialization below
00659     // for ints... 
00660   } 
00661 
00663         //
00667         void  expandTo(const Range2d<T>& r)
00668         {
00669                 if ( r.isNull() )
00670                 {
00671                         // the given range will add nothing
00672                         return; 
00673                 }
00674 
00675                 if ( isNull() ) 
00676                 {
00677                         // being null ourself, we'll equal the given range
00678                         *this = r;
00679                         return;
00680                 }
00681 
00682                 if ( isWorld() || r.isWorld() )
00683                 {
00684                         // union with world is always world...
00685                         setWorld();
00686                         return;
00687                 }
00688 
00689                 _xmin = std::min(_xmin, r._xmin);
00690                 _xmax = std::max(_xmax, r._xmax);
00691                 _ymin = std::min(_ymin, r._ymin);
00692                 _ymax = std::max(_ymax, r._ymax);
00693 
00694         }
00695 
00696 
00697 };
00698 
00699 template <typename T> inline std::ostream&
00700 operator<< (std::ostream& os, const Range2d<T>& rect)
00701 {
00702         if ( rect.isNull() ) return os << "Null range";
00703         if ( rect.isWorld() ) return os << "World range";
00704 
00705         return os << "Finite range (" << rect._xmin << "," << rect._ymin
00706                 << " " << rect._xmax << "," << rect._ymax << ")";
00707 }
00708 
00709 template <typename T> inline bool
00710 operator== (const Range2d<T>& r1, const Range2d<T>& r2)
00711 {
00712         // These checks are needed becase
00713         // we don't initialize *all* memebers
00714         // when setting to Null or World
00715 
00716         if ( r1.isNull() ) return r2.isNull();
00717         if ( r2.isNull() ) return r1.isNull();
00718         if ( r1.isWorld() ) return r2.isWorld();
00719         if ( r2.isWorld() ) return r1.isWorld();
00720 
00721         return r1._xmin == r2._xmin && r1._ymin == r2._ymin &&
00722                 r1._xmax == r2._xmax && r1._ymax == r2._ymax;
00723 }
00724 
00725 template <typename T> inline bool
00726 operator!= (const Range2d<T>& r1, const Range2d<T>& r2)
00727 {
00728         return ! ( r1 == r2 );
00729 }
00730 
00732 template <typename T> inline bool
00733 Intersect(const Range2d<T>& r1, const Range2d<T>& r2)
00734 {
00735         return r1.intersects(r2);
00736 }
00737 
00739 template <typename T> inline Range2d<T>
00740 Union(const Range2d<T>& r1, const Range2d<T>& r2)
00741 {
00742         Range2d<T> ret = r1;
00743         ret.expandTo(r2);
00744         return ret;
00745 }
00746 
00748 //
00751 template <typename T> inline Range2d<T>
00752 Intersection(const Range2d<T>& r1, const Range2d<T>& r2)
00753 {
00754         if ( r1.isNull() || r2.isNull() ) {
00755                 // NULL ranges intersect nothing
00756                 return Range2d<T>(nullRange); 
00757         }
00758 
00759         if ( r1.isWorld() ) {
00760                 // WORLD range intersect everything
00761                 return r2;
00762         }
00763 
00764         if ( r2.isWorld() ) {
00765                 // WORLD range intersect everything
00766                 return r1;
00767         }
00768 
00769         if ( ! r1.intersects(r2) ) {
00770                 // No intersection results in a NULL range
00771                 return Range2d<T>(nullRange); 
00772         }
00773 
00774         return Range2d<T> (
00775                 std::max(r1._xmin, r2._xmin), // xmin
00776                 std::max(r1._ymin, r2._ymin), // ymin
00777                 std::min(r1._xmax, r2._xmax), // xmax
00778                 std::min(r1._ymax, r2._ymax)  // ymax
00779         );
00780 
00781 }
00782 
00784 //
00787 template <> inline int
00788 Range2d<int>::roundMin(float min)
00789 {
00790         return static_cast<int>(std::floor(min));
00791 }
00792 
00794 //
00797 template <> inline unsigned int
00798 Range2d<unsigned int>::roundMin(float min)
00799 {
00800         return static_cast<unsigned int>(std::floor(min));
00801 }
00802 
00804 //
00807 template <> inline int
00808 Range2d<int>::roundMax(float max)
00809 {
00810         return static_cast<int>(std::ceil(max));
00811 }
00812 
00814 //
00817 template <> inline unsigned int
00818 Range2d<unsigned int>::roundMax(float max)
00819 {
00820         return static_cast<unsigned int>(std::ceil(static_cast<float>(max)));
00821 }
00822 
00824 //
00827 template <> inline int
00828 Range2d<int>::getArea() const
00829 {
00830   assert ( !isWorld() );
00831   if ( isNull() ) return 0;
00832   return (_xmax - _xmin + 1) * (_ymax - _ymin + 1);
00833 }
00834 
00836 //
00839 template <> inline unsigned int
00840 Range2d<unsigned int>::getArea() const
00841 {
00842   assert ( isFinite() );
00843   return (_xmax - _xmin + 1) * (_ymax - _ymin + 1);
00844 }
00845 
00846 
00847 } // namespace gnash::geometry
00848 } // namespace gnash
00849 
00850 #endif // GNASH_RANGE2D_H
00851 
00852 
00853 // Local Variables:
00854 // mode: C++
00855 // indent-tabs-mode: t
00856 // End: