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

Range2d.h

Go to the documentation of this file.
00001 // 
00002 //   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 Free Software
00003 //   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 <iostream> // temporary include for debugging
00033 #include <cmath> // for floor / ceil
00034 
00035 namespace gnash {
00036 
00037 namespace geometry {
00038 
00040 enum RangeKind {
00042         finiteRange,
00043 
00045         nullRange,
00046 
00050         // 
00054         worldRange
00055 };
00056 
00058 //
00071 template <typename T>
00072 class Range2d
00073 {
00074 private:
00075 
00076         T _xmin, _xmax, _ymin, _ymax;
00077 
00078         T scaleMin(T min, float scale)
00079         {
00080                 return roundMin(static_cast<float>(min) * scale);
00081         }
00082 
00083         T scaleMax(T max, float scale)
00084         {
00085                 return roundMax(static_cast<float>(max) * scale);
00086         }
00087 
00088         T roundMin(float v)
00089         {
00090                 return static_cast<T>(v);
00091         }
00092 
00093         T roundMax(float v)
00094         {
00095                 return static_cast<T>(v);
00096         }
00097 
00098 public:
00099 
00101         template <typename U>
00102         friend std::ostream& operator<< (std::ostream& os, const Range2d<U>& rect);
00103 
00105         //
00110         template <typename U>
00111         friend bool operator== (const Range2d<U>& r1, const Range2d<U>& r2);
00112 
00114         //
00119         template <typename U>
00120         friend bool operator!= (const Range2d<U>& r1, const Range2d<U>& r2);
00121 
00123         //
00126         template <typename U> friend Range2d<U>
00127         Intersection(const Range2d<U>& r1, const Range2d<U>& r2);
00128 
00130         template <typename U> friend Range2d<U>
00131         Union(const Range2d<U>& r1, const Range2d<U>& r2);
00132 
00134         //
00141         Range2d(RangeKind kind=nullRange)
00142                 :
00143                 _xmin(T()),
00144                 _xmax(T()),
00145                 _ymin(T()),
00146                 _ymax(T())
00147         {
00148                 switch ( kind )
00149                 {
00150                         case worldRange:
00151                                 setWorld();
00152                                 break;
00153                         case nullRange:
00154                                 setNull();
00155                                 break;
00156                         default:
00157                         case finiteRange:
00158                                 break;
00159                 }
00160         }
00161 
00163         //
00170         Range2d(T xmin, T ymin, T xmax, T ymax)
00171                 :
00172                 _xmin(xmin),
00173                 _xmax(xmax),
00174                 _ymin(ymin),
00175                 _ymax(ymax)
00176         {
00177                 // use the default ctor to make a NULL Range2d
00178                 assert(_xmin <= _xmax);
00179                 assert(_ymin <= _ymax);
00180                 // .. or should we raise an exception .. ?
00181         }
00182 
00184         template <typename U>
00185         Range2d(const Range2d<U>& from)
00186         {
00187                 if ( from.isWorld() ) {
00188                         setWorld();
00189                 } else if ( from.isNull() ) {
00190                         setNull();
00191                 } else {
00192                         _xmin = roundMin(from.getMinX());
00193                         _ymin = roundMin(from.getMinY());
00194                         _xmax = roundMax(from.getMaxX());
00195                         _ymax = roundMax(from.getMaxY());
00196                 }
00197         }
00198 
00200         bool isNull() const
00201         {
00202                 return _xmax < _xmin;
00203         }
00204 
00206         //
00209         Range2d<T>& setNull()
00210         {
00211                 _xmin = std::numeric_limits<T>::max();
00212                 _xmax = std::numeric_limits<T>::min();
00213                 return *this;
00214         }
00215 
00217         bool isWorld() const
00218         {
00219                 return _xmax == std::numeric_limits<T>::max()
00220                         && _xmin == std::numeric_limits<T>::min();
00221         }
00222 
00224         //
00227         bool isFinite() const
00228         {
00229                 return ( ! isNull() && ! isWorld() );
00230         }
00231 
00233         //
00241         Range2d<T>& setWorld()
00242         {
00243                 _xmin = std::numeric_limits<T>::min();
00244                 _xmax = std::numeric_limits<T>::max();
00245                 return *this;
00246         }
00247 
00251         //
00255         template <typename U>
00256         bool contains(U x, U y) const
00257         {
00258                 if ( isNull() ) return false;
00259                 if ( isWorld() ) return true;
00260                 if (x < _xmin || x > _xmax || y < _ymin || y > _ymax)
00261                 {
00262                         return false;
00263                 }
00264                 return true;
00265         }
00266 
00269         //
00277         bool contains(const Range2d<T>& other) const
00278         {
00279                 if ( isNull() || other.isNull() ) return false;
00280                 if ( isWorld() ) return true;
00281                 if ( other.isWorld() ) return false;
00282 
00283                 return _xmin <= other._xmin &&
00284                         _xmax >= other._xmax &&
00285                         _ymin <= other._ymin &&
00286                         _ymax >= other._ymax;
00287         }
00288 
00292         //
00296         bool intersects(const Range2d<T>& other) const
00297         {
00298                 if ( isNull() || other.isNull() ) return false;
00299                 if ( isWorld() || other.isWorld() ) return true;
00300 
00301                 if ( _xmin > other._xmax ) return false;
00302                 if ( _xmax < other._xmin ) return false;
00303                 if ( _ymin > other._ymax ) return false;
00304                 if ( _ymax < other._ymin ) return false;
00305                 return true;
00306         }
00307 
00309         //
00312         Range2d<T>& expandTo(T x, T y)
00313         {
00314                 // A WORLD range already enclose every point
00315                 if ( isWorld() ) return *this;
00316 
00317                 if ( isNull() ) 
00318                 {
00319                         setTo(x,y);
00320                 }
00321                 else
00322                 {
00323                         _xmin = std::min(_xmin, x);
00324                         _ymin = std::min(_ymin, y);
00325                         _xmax = std::max(_xmax, x);
00326                         _ymax = std::max(_ymax, y);
00327                 }
00328 
00329                 return *this;
00330         }
00331 
00333         //
00336         Range2d<T>& expandToCircle(T x, T y, T radius)
00337         {
00338                 // A WORLD range already enclose every point
00339                 if ( isWorld() ) return *this;
00340 
00341         expandTo(x-radius, y);
00342         expandTo(x+radius, y);
00343 
00344         expandTo(x, y-radius);
00345         expandTo(x, y+radius);
00346 
00347                 return *this;
00348         }
00349 
00351         //
00354         Range2d<T>& setTo(T x, T y)
00355         {
00356                 _xmin = _xmax = x;
00357                 _ymin = _ymax = y;
00358                 return *this;
00359         }
00360 
00362         //
00368         //
00371         Range2d<T>& setTo(T xmin, T ymin, T xmax, T ymax)
00372         {
00373                 _xmin = xmin;
00374                 _xmax = xmax;
00375                 _ymin = ymin;
00376                 _ymax = ymax;
00377 
00378                 // use the default ctor to make a NULL Range2d
00379                 assert(_xmin <= _xmax);
00380                 assert(_ymin <= _ymax);
00381 
00382                 return *this;
00383         }
00384 
00386         //
00389         T width() const
00390         {
00391                 assert ( ! isWorld() );
00392                 if ( isNull() ) return 0;
00393                 return _xmax-_xmin;
00394         }
00395 
00397         //
00400         T height() const
00401         {
00402                 assert ( ! isWorld() );
00403                 if ( isNull() ) return 0;
00404                 return _ymax-_ymin;
00405         }
00406 
00408         //
00416         Range2d<T>& shiftX(T offset)
00417         {
00418                 if ( isNull() || isWorld() ) return *this;
00419                 _xmin += offset;
00420                 _xmax += offset;
00421                 return *this;
00422         }
00423 
00425         //
00433         Range2d<T>& shiftY(T offset)
00434         {
00435                 if ( isNull() || isWorld() ) return *this;
00436                 _ymin += offset;
00437                 _ymax += offset;
00438                 return *this;
00439         }
00440 
00442         Range2d<T>& scaleX(float factor)
00443         {
00444                 return scale(factor, 1);
00445         }
00446 
00448         Range2d<T>& scaleY(float factor)
00449         {
00450                 return scale(1, factor);
00451         }
00452 
00454         //
00486         Range2d<T>& scale(float xfactor, float yfactor)
00487         {
00488                 assert(xfactor >= 0 && yfactor >= 0);
00489 
00490                 if ( ! isFinite() ) return *this;
00491 
00492                 if ( xfactor == 0 || yfactor == 0 )
00493                 {
00494                         return setNull();
00495                 }
00496 
00497                 if ( xfactor != 1 )
00498                 {
00499                         _xmin = scaleMin(_xmin, xfactor);
00500                         _xmax = scaleMax(_xmax, xfactor);
00501                         assert(_xmin <= _xmax); // in case of overflow...
00502                 }
00503 
00504                 if ( yfactor != 1 )
00505                 {
00506                         _ymin = scaleMin(_ymin, yfactor);
00507                         _ymax = scaleMax(_ymax, yfactor);
00508                         assert(_ymin <= _ymax); // in case of overflow...
00509                 }
00510 
00511                 return *this;
00512         }
00513 
00515         Range2d<T>& scale(float factor)
00516         {
00517                 return scale(factor, factor);
00518         }
00519 
00521         //
00535         Range2d<T>& growBy(T amount)
00536         {
00537                 if ( isNull() || isWorld() || amount==0 ) return *this;
00538 
00539                 // NOTE: triggers a compiler warning when T is an unsigned type
00540                 if ( amount < 0 ) return shrinkBy(-amount);
00541 
00542                 T newxmin = _xmin - amount;
00543                 if (newxmin > _xmin ) return setWorld();
00544                 else _xmin = newxmin;
00545 
00546                 T newxmax = _xmax + amount;
00547                 if (newxmax < _xmax ) return setWorld();
00548                 else _xmax = newxmax;
00549 
00550                 T newymin = _ymin - amount;
00551                 if (newymin > _ymin ) return setWorld();
00552                 else _ymin = newymin;
00553 
00554                 T newymax = _ymax + amount;
00555                 if (newymax < _ymax ) return setWorld();
00556                 else _ymax = newymax;
00557 
00558                 return *this;
00559 
00560         }
00561 
00563         //
00586         Range2d<T>& shrinkBy(T amount)
00587         {
00588                 if ( isNull() || isWorld() || amount==0 ) return *this;
00589 
00590                 // NOTE: whith will likely trigger a compiler
00591                 //       warning when T is an unsigned type
00592                 if ( amount < 0 ) return growBy(-amount);
00593 
00594                 // Turn this range into the NULL range
00595                 // if any dimension collapses.
00596                 // Don't use width() and height() to 
00597                 // avoid superflous checks.
00598 
00599                 if ( _xmax - _xmin <= amount ) return setNull();
00600                 if ( _ymax - _ymin <= amount ) return setNull();
00601 
00602                 _xmin += amount;
00603                 _ymin += amount;
00604                 _xmax -= amount;
00605                 _ymax -= amount;
00606 
00607                 return *this;
00608 
00609         }
00610 
00612         //
00615         T getMinX() const
00616         {
00617                 assert ( isFinite() );
00618                 return _xmin;
00619         }
00620 
00622         //
00625         T getMaxX() const
00626         {
00627                 assert ( isFinite() );
00628                 return _xmax;
00629         }
00630 
00632         //
00635         T getMinY() const
00636         {
00637                 assert ( isFinite() );
00638                 return _ymin;
00639         }
00640 
00642         //
00645         T getMaxY() const
00646         {
00647                 assert ( isFinite() );
00648                 return _ymax;
00649         }
00650         
00651         
00654         T getArea() const
00655   {
00656     assert ( !isWorld() );
00657     if ( isNull() ) return 0;
00658     return (_xmax - _xmin) * (_ymax - _ymin);
00659     // this implementation is for float types, see specialization below
00660     // for ints... 
00661   } 
00662 
00664         //
00668         void  expandTo(const Range2d<T>& r)
00669         {
00670                 if ( r.isNull() )
00671                 {
00672                         // the given range will add nothing
00673                         return; 
00674                 }
00675 
00676                 if ( isNull() ) 
00677                 {
00678                         // being null ourself, we'll equal the given range
00679                         *this = r;
00680                         return;
00681                 }
00682 
00683                 if ( isWorld() || r.isWorld() )
00684                 {
00685                         // union with world is always world...
00686                         setWorld();
00687                         return;
00688                 }
00689 
00690                 _xmin = std::min(_xmin, r._xmin);
00691                 _xmax = std::max(_xmax, r._xmax);
00692                 _ymin = std::min(_ymin, r._ymin);
00693                 _ymax = std::max(_ymax, r._ymax);
00694 
00695         }
00696 
00697 
00698 };
00699 
00700 template <typename T> inline std::ostream&
00701 operator<< (std::ostream& os, const Range2d<T>& rect)
00702 {
00703         if ( rect.isNull() ) return os << "Null range";
00704         if ( rect.isWorld() ) return os << "World range";
00705 
00706         return os << "Finite range (" << rect._xmin << "," << rect._ymin
00707                 << " " << rect._xmax << "," << rect._ymax << ")";
00708 }
00709 
00710 template <typename T> inline bool
00711 operator== (const Range2d<T>& r1, const Range2d<T>& r2)
00712 {
00713         // These checks are needed becase
00714         // we don't initialize *all* memebers
00715         // when setting to Null or World
00716 
00717         if ( r1.isNull() ) return r2.isNull();
00718         if ( r2.isNull() ) return r1.isNull();
00719         if ( r1.isWorld() ) return r2.isWorld();
00720         if ( r2.isWorld() ) return r1.isWorld();
00721 
00722         return r1._xmin == r2._xmin && r1._ymin == r2._ymin &&
00723                 r1._xmax == r2._xmax && r1._ymax == r2._ymax;
00724 }
00725 
00726 template <typename T> inline bool
00727 operator!= (const Range2d<T>& r1, const Range2d<T>& r2)
00728 {
00729         return ! ( r1 == r2 );
00730 }
00731 
00733 template <typename T> inline bool
00734 Intersect(const Range2d<T>& r1, const Range2d<T>& r2)
00735 {
00736         return r1.intersects(r2);
00737 }
00738 
00740 template <typename T> inline Range2d<T>
00741 Union(const Range2d<T>& r1, const Range2d<T>& r2)
00742 {
00743         Range2d<T> ret = r1;
00744         ret.expandTo(r2);
00745         return ret;
00746 }
00747 
00749 //
00752 template <typename T> inline Range2d<T>
00753 Intersection(const Range2d<T>& r1, const Range2d<T>& r2)
00754 {
00755         if ( r1.isNull() || r2.isNull() ) {
00756                 // NULL ranges intersect nothing
00757                 return Range2d<T>(nullRange); 
00758         }
00759 
00760         if ( r1.isWorld() ) {
00761                 // WORLD range intersect everything
00762                 return r2;
00763         }
00764 
00765         if ( r2.isWorld() ) {
00766                 // WORLD range intersect everything
00767                 return r1;
00768         }
00769 
00770         if ( ! r1.intersects(r2) ) {
00771                 // No intersection results in a NULL range
00772                 return Range2d<T>(nullRange); 
00773         }
00774 
00775         return Range2d<T> (
00776                 std::max(r1._xmin, r2._xmin), // xmin
00777                 std::max(r1._ymin, r2._ymin), // ymin
00778                 std::min(r1._xmax, r2._xmax), // xmax
00779                 std::min(r1._ymax, r2._ymax)  // ymax
00780         );
00781 
00782 }
00783 
00785 //
00788 template <> inline int
00789 Range2d<int>::roundMin(float min)
00790 {
00791         return static_cast<int>(std::floor(min));
00792 }
00793 
00795 //
00798 template <> inline unsigned int
00799 Range2d<unsigned int>::roundMin(float min)
00800 {
00801         return static_cast<unsigned int>(std::floor(min));
00802 }
00803 
00805 //
00808 template <> inline int
00809 Range2d<int>::roundMax(float max)
00810 {
00811         return static_cast<int>(std::ceil(max));
00812 }
00813 
00815 //
00818 template <> inline unsigned int
00819 Range2d<unsigned int>::roundMax(float max)
00820 {
00821         return static_cast<unsigned int>(std::ceil(static_cast<float>(max)));
00822 }
00823 
00825 //
00828 template <> inline int
00829 Range2d<int>::getArea() const
00830 {
00831   assert ( !isWorld() );
00832   if ( isNull() ) return 0;
00833   return (_xmax - _xmin + 1) * (_ymax - _ymin + 1);
00834 }
00835 
00837 //
00840 template <> inline unsigned int
00841 Range2d<unsigned int>::getArea() const
00842 {
00843   assert ( isFinite() );
00844   return (_xmax - _xmin + 1) * (_ymax - _ymin + 1);
00845 }
00846 
00847 
00848 } // namespace gnash::geometry
00849 } // namespace gnash
00850 
00851 #endif // GNASH_RANGE2D_H
00852 
00853 
00854 // Local Variables:
00855 // mode: C++
00856 // indent-tabs-mode: t
00857 // End:

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