Gnash  0.8.11dev
Range2d.h
Go to the documentation of this file.
1 //
2 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 // Free Software Foundation, Inc
4 //
5 // This program is free software; you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation; either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program; if not, write to the Free Software
17 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 
19 //
20 // Original author: Sandro Santilli <strk@keybit.net>
21 //
22 
23 #ifndef GNASH_RANGE2D_H
24 #define GNASH_RANGE2D_H
25 
26 #include <ostream>
27 #include <limits>
28 #include <algorithm>
29 #include <cassert> // for inlines
30 #include <cmath> // for floor / ceil
31 
32 namespace gnash {
33 
34 namespace geometry {
35 
37 enum RangeKind {
40 
43 
47  //
52 };
53 
55 //
68 template <typename T>
69 class Range2d
70 {
71 public:
72 
74  template <typename U>
75  friend std::ostream& operator<< (std::ostream& os, const Range2d<U>& rect);
76 
78  //
83  template <typename U>
84  friend bool operator== (const Range2d<U>& r1, const Range2d<U>& r2);
85 
87  //
92  template <typename U>
93  friend bool operator!= (const Range2d<U>& r1, const Range2d<U>& r2);
94 
96  //
99  template <typename U> friend Range2d<U>
100  Intersection(const Range2d<U>& r1, const Range2d<U>& r2);
101 
103  template <typename U> friend Range2d<U>
104  Union(const Range2d<U>& r1, const Range2d<U>& r2);
105 
107  //
115  :
116  _xmin(T()),
117  _xmax(T()),
118  _ymin(T()),
119  _ymax(T())
120  {
121  switch ( kind )
122  {
123  case worldRange:
124  setWorld();
125  break;
126  case nullRange:
127  setNull();
128  break;
129  default:
130  case finiteRange:
131  break;
132  }
133  }
134 
136  //
143  Range2d(T xmin, T ymin, T xmax, T ymax)
144  :
145  _xmin(xmin),
146  _xmax(xmax),
147  _ymin(ymin),
148  _ymax(ymax)
149  {
150  // use the default ctor to make a NULL Range2d
151  assert(_xmin <= _xmax);
152  assert(_ymin <= _ymax);
153  // .. or should we raise an exception .. ?
154  }
155 
157  template <typename U>
158  Range2d(const Range2d<U>& from)
159  {
160  if ( from.isWorld() ) {
161  setWorld();
162  } else if ( from.isNull() ) {
163  setNull();
164  } else {
165  _xmin = roundMin(from.getMinX());
166  _ymin = roundMin(from.getMinY());
167  _xmax = roundMax(from.getMaxX());
168  _ymax = roundMax(from.getMaxY());
169  }
170  }
171 
173  bool isNull() const
174  {
175  return _xmax < _xmin;
176  }
177 
179  //
183  {
184  _xmin = std::numeric_limits<T>::max();
185  _xmax = std::numeric_limits<T>::min();
186  return *this;
187  }
188 
190  bool isWorld() const
191  {
192  return _xmax == std::numeric_limits<T>::max()
193  && _xmin == std::numeric_limits<T>::min();
194  }
195 
197  //
200  bool isFinite() const
201  {
202  return ( ! isNull() && ! isWorld() );
203  }
204 
206  //
215  {
216  _xmin = std::numeric_limits<T>::min();
217  _xmax = std::numeric_limits<T>::max();
218  return *this;
219  }
220 
224  //
228  template <typename U>
229  bool contains(U x, U y) const
230  {
231  if ( isNull() ) return false;
232  if ( isWorld() ) return true;
233  if (x < _xmin || x > _xmax || y < _ymin || y > _ymax)
234  {
235  return false;
236  }
237  return true;
238  }
239 
242  //
250  bool contains(const Range2d<T>& other) const
251  {
252  if ( isNull() || other.isNull() ) return false;
253  if ( isWorld() ) return true;
254  if ( other.isWorld() ) return false;
255 
256  return _xmin <= other._xmin &&
257  _xmax >= other._xmax &&
258  _ymin <= other._ymin &&
259  _ymax >= other._ymax;
260  }
261 
265  //
269  bool intersects(const Range2d<T>& other) const
270  {
271  if ( isNull() || other.isNull() ) return false;
272  if ( isWorld() || other.isWorld() ) return true;
273 
274  if ( _xmin > other._xmax ) return false;
275  if ( _xmax < other._xmin ) return false;
276  if ( _ymin > other._ymax ) return false;
277  if ( _ymax < other._ymin ) return false;
278  return true;
279  }
280 
282  //
286  {
287  // A WORLD range already enclose every point
288  if ( isWorld() ) return *this;
289 
290  if ( isNull() )
291  {
292  setTo(x,y);
293  }
294  else
295  {
296  _xmin = std::min(_xmin, x);
297  _ymin = std::min(_ymin, y);
298  _xmax = std::max(_xmax, x);
299  _ymax = std::max(_ymax, y);
300  }
301 
302  return *this;
303  }
304 
306  //
310  {
311  // A WORLD range already enclose every point
312  if ( isWorld() ) return *this;
313 
314  expandTo(x-radius, y);
315  expandTo(x+radius, y);
316 
317  expandTo(x, y-radius);
318  expandTo(x, y+radius);
319 
320  return *this;
321  }
322 
324  //
328  {
329  _xmin = _xmax = x;
330  _ymin = _ymax = y;
331  return *this;
332  }
333 
335  //
341  //
344  Range2d<T>& setTo(T xmin, T ymin, T xmax, T ymax)
345  {
346  _xmin = xmin;
347  _xmax = xmax;
348  _ymin = ymin;
349  _ymax = ymax;
350 
351  // use the default ctor to make a NULL Range2d
352  assert(_xmin <= _xmax);
353  assert(_ymin <= _ymax);
354 
355  return *this;
356  }
357 
359  //
362  T width() const
363  {
364  assert ( ! isWorld() );
365  if ( isNull() ) return 0;
366  return _xmax-_xmin;
367  }
368 
370  //
373  T height() const
374  {
375  assert ( ! isWorld() );
376  if ( isNull() ) return 0;
377  return _ymax-_ymin;
378  }
379 
381  //
389  Range2d<T>& shiftX(T offset)
390  {
391  if ( isNull() || isWorld() ) return *this;
392  _xmin += offset;
393  _xmax += offset;
394  return *this;
395  }
396 
398  //
406  Range2d<T>& shiftY(T offset)
407  {
408  if ( isNull() || isWorld() ) return *this;
409  _ymin += offset;
410  _ymax += offset;
411  return *this;
412  }
413 
415  Range2d<T>& scaleX(float factor)
416  {
417  return scale(factor, 1);
418  }
419 
421  Range2d<T>& scaleY(float factor)
422  {
423  return scale(1, factor);
424  }
425 
427  //
459  Range2d<T>& scale(float xfactor, float yfactor)
460  {
461  assert(xfactor >= 0 && yfactor >= 0);
462 
463  if ( ! isFinite() ) return *this;
464 
465  if ( xfactor == 0 || yfactor == 0 )
466  {
467  return setNull();
468  }
469 
470  if ( xfactor != 1 )
471  {
472  _xmin = scaleMin(_xmin, xfactor);
473  _xmax = scaleMax(_xmax, xfactor);
474  assert(_xmin <= _xmax); // in case of overflow...
475  }
476 
477  if ( yfactor != 1 )
478  {
479  _ymin = scaleMin(_ymin, yfactor);
480  _ymax = scaleMax(_ymax, yfactor);
481  assert(_ymin <= _ymax); // in case of overflow...
482  }
483 
484  return *this;
485  }
486 
488  Range2d<T>& scale(float factor)
489  {
490  return scale(factor, factor);
491  }
492 
494  //
508  Range2d<T>& growBy(T amount)
509  {
510  if ( isNull() || isWorld() || amount==0 ) return *this;
511 
512  // NOTE: triggers a compiler warning when T is an unsigned type
513  if ( amount < 0 ) return shrinkBy(-amount);
514 
515  T newxmin = _xmin - amount;
516  if (newxmin > _xmin ) return setWorld();
517  else _xmin = newxmin;
518 
519  T newxmax = _xmax + amount;
520  if (newxmax < _xmax ) return setWorld();
521  else _xmax = newxmax;
522 
523  T newymin = _ymin - amount;
524  if (newymin > _ymin ) return setWorld();
525  else _ymin = newymin;
526 
527  T newymax = _ymax + amount;
528  if (newymax < _ymax ) return setWorld();
529  else _ymax = newymax;
530 
531  return *this;
532 
533  }
534 
536  //
560  {
561  if ( isNull() || isWorld() || amount==0 ) return *this;
562 
563  // NOTE: whith will likely trigger a compiler
564  // warning when T is an unsigned type
565  if ( amount < 0 ) return growBy(-amount);
566 
567  // Turn this range into the NULL range
568  // if any dimension collapses.
569  // Don't use width() and height() to
570  // avoid superflous checks.
571 
572  if ( _xmax - _xmin <= amount ) return setNull();
573  if ( _ymax - _ymin <= amount ) return setNull();
574 
575  _xmin += amount;
576  _ymin += amount;
577  _xmax -= amount;
578  _ymax -= amount;
579 
580  return *this;
581 
582  }
583 
585  //
588  T getMinX() const
589  {
590  assert ( isFinite() );
591  return _xmin;
592  }
593 
595  //
598  T getMaxX() const
599  {
600  assert ( isFinite() );
601  return _xmax;
602  }
603 
605  //
608  T getMinY() const
609  {
610  assert ( isFinite() );
611  return _ymin;
612  }
613 
615  //
618  T getMaxY() const
619  {
620  assert ( isFinite() );
621  return _ymax;
622  }
623 
626  T getArea() const {
627  assert ( !isWorld() );
628  if ( isNull() ) return 0;
629  return (_xmax - _xmin) * (_ymax - _ymin);
630  // this implementation is for float types, see specialization below
631  // for ints...
632  }
633 
635  //
639  void expandTo(const Range2d<T>& r)
640  {
641  if ( r.isNull() )
642  {
643  // the given range will add nothing
644  return;
645  }
646 
647  if ( isNull() )
648  {
649  // being null ourself, we'll equal the given range
650  *this = r;
651  return;
652  }
653 
654  if ( isWorld() || r.isWorld() )
655  {
656  // union with world is always world...
657  setWorld();
658  return;
659  }
660 
661  _xmin = std::min(_xmin, r._xmin);
662  _xmax = std::max(_xmax, r._xmax);
663  _ymin = std::min(_ymin, r._ymin);
664  _ymax = std::max(_ymax, r._ymax);
665 
666  }
667 
668 private:
669 
670  T _xmin, _xmax, _ymin, _ymax;
671 
672  T scaleMin(T min, float scale) const {
673  return roundMin(static_cast<float>(min) * scale);
674  }
675 
676  T scaleMax(T max, float scale) const {
677  return roundMax(static_cast<float>(max) * scale);
678  }
679 
680  T roundMin(float v) const {
681  return static_cast<T>(v);
682  }
683 
684  T roundMax(float v) const {
685  return static_cast<T>(v);
686  }
687 
688 
689 };
690 
691 template <typename T> inline std::ostream&
692 operator<< (std::ostream& os, const Range2d<T>& rect)
693 {
694  if ( rect.isNull() ) return os << "Null range";
695  if ( rect.isWorld() ) return os << "World range";
696 
697  return os << "Finite range (" << rect._xmin << "," << rect._ymin
698  << " " << rect._xmax << "," << rect._ymax << ")";
699 }
700 
701 template <typename T> inline bool
702 operator== (const Range2d<T>& r1, const Range2d<T>& r2)
703 {
704  // These checks are needed becase
705  // we don't initialize *all* memebers
706  // when setting to Null or World
707 
708  if ( r1.isNull() ) return r2.isNull();
709  if ( r2.isNull() ) return r1.isNull();
710  if ( r1.isWorld() ) return r2.isWorld();
711  if ( r2.isWorld() ) return r1.isWorld();
712 
713  return r1._xmin == r2._xmin && r1._ymin == r2._ymin &&
714  r1._xmax == r2._xmax && r1._ymax == r2._ymax;
715 }
716 
717 template <typename T> inline bool
718 operator!= (const Range2d<T>& r1, const Range2d<T>& r2)
719 {
720  return ! ( r1 == r2 );
721 }
722 
724 template <typename T> inline bool
725 Intersect(const Range2d<T>& r1, const Range2d<T>& r2)
726 {
727  return r1.intersects(r2);
728 }
729 
731 template <typename T> inline Range2d<T>
732 Union(const Range2d<T>& r1, const Range2d<T>& r2)
733 {
734  Range2d<T> ret = r1;
735  ret.expandTo(r2);
736  return ret;
737 }
738 
740 //
743 template <typename T> inline Range2d<T>
744 Intersection(const Range2d<T>& r1, const Range2d<T>& r2)
745 {
746  if ( r1.isNull() || r2.isNull() ) {
747  // NULL ranges intersect nothing
748  return Range2d<T>(nullRange);
749  }
750 
751  if ( r1.isWorld() ) {
752  // WORLD range intersect everything
753  return r2;
754  }
755 
756  if ( r2.isWorld() ) {
757  // WORLD range intersect everything
758  return r1;
759  }
760 
761  if ( ! r1.intersects(r2) ) {
762  // No intersection results in a NULL range
763  return Range2d<T>(nullRange);
764  }
765 
766  return Range2d<T> (
767  std::max(r1._xmin, r2._xmin), // xmin
768  std::max(r1._ymin, r2._ymin), // ymin
769  std::min(r1._xmax, r2._xmax), // xmax
770  std::min(r1._ymax, r2._ymax) // ymax
771  );
772 
773 }
774 
776 //
779 template<> inline int
780 Range2d<int>::roundMin(float min) const
781 {
782  return static_cast<int>(std::floor(min));
783 }
784 
786 //
789 template<> inline unsigned int
790 Range2d<unsigned int>::roundMin(float min) const
791 {
792  return static_cast<unsigned int>(std::floor(min));
793 }
794 
796 //
799 template<> inline int
800 Range2d<int>::roundMax(float max) const
801 {
802  return static_cast<int>(std::ceil(max));
803 }
804 
806 //
809 template<> inline unsigned int
810 Range2d<unsigned int>::roundMax(float max) const
811 {
812  return static_cast<unsigned int>(std::ceil(max));
813 }
814 
816 //
819 template<> inline int
821 {
822  assert ( !isWorld() );
823  if ( isNull() ) return 0;
824  return (_xmax - _xmin + 1) * (_ymax - _ymin + 1);
825 }
826 
828 //
831 template<> inline unsigned int
833 {
834  assert ( isFinite() );
835  return (_xmax - _xmin + 1) * (_ymax - _ymin + 1);
836 }
837 
838 
839 } // namespace gnash::geometry
840 } // namespace gnash
841 
842 #endif // GNASH_RANGE2D_H
843 
844 
845 // Local Variables:
846 // mode: C++
847 // indent-tabs-mode: t
848 // End:
Range2d< T > & shiftY(T offset)
Shift this Range2dangle vertically.
Definition: Range2d.h:406
bool operator==(const Range2d< T > &r1, const Range2d< T > &r2)
Definition: Range2d.h:702
A NULL range is a range enclosing NO points.
Definition: Range2d.h:42
Range2d< T > & setNull()
Set the Range2d to the NULL value.
Definition: Range2d.h:182
A WORLD range2d is a range including all points on the plane.
Definition: Range2d.h:51
bool isFinite() const
Returns true if this is a finite Range2d.
Definition: Range2d.h:200
bool intersects(const Range2d< T > &other) const
Return true if this rectangle intersects the point with given coordinates (boundaries are inclusive)...
Definition: Range2d.h:269
friend bool operator==(const Range2d< U > &r1, const Range2d< U > &r2)
Equality operator.
T getMinY() const
Get min Y ordinate.
Definition: Range2d.h:608
2d Range template class
Definition: Range2d.h:69
bool contains(const Range2d< T > &other) const
Return true if this rectangle contains the given rectangle.
Definition: Range2d.h:250
Range2d< T > Union(const Range2d< T > &r1, const Range2d< T > &r2)
Return a rectangle being the union of the two rectangles.
Definition: Range2d.h:732
Definition: GnashKey.h:164
Range2d< T > & setTo(T x, T y)
Set ourself to bound the given point.
Definition: Range2d.h:327
Range2d< T > Intersection(const Range2d< T > &r1, const Range2d< T > &r2)
Return a rectangle being the intersetion of the two rectangles.
Definition: Range2d.h:744
Range2d< T > & scale(float xfactor, float yfactor)
Scale this Range2d.
Definition: Range2d.h:459
T getMaxX() const
Get max X ordinate.
Definition: Range2d.h:598
bool Intersect(const Range2d< T > &r1, const Range2d< T > &r2)
Return true of the two ranges intersect (boundaries included)
Definition: Range2d.h:725
Range2d< T > & expandToCircle(T x, T y, T radius)
Expand this Range2d to enclose the given circle.
Definition: Range2d.h:309
bool contains(U x, U y) const
Return true if this rectangle contains the point with given coordinates (boundaries are inclusive)...
Definition: Range2d.h:229
bool isFinite(double d)
Definition: GnashNumeric.h:48
Range2d< T > & scaleY(float factor)
Scale this Range2d vertically.
Definition: Range2d.h:421
Range2d(T xmin, T ymin, T xmax, T ymax)
Construct a finite Range2d with the given values.
Definition: Range2d.h:143
friend Range2d< U > Union(const Range2d< U > &r1, const Range2d< U > &r2)
Return a rectangle being the union of the two rectangles.
T width() const
Return width this Range2d.
Definition: Range2d.h:362
tuple v
Definition: test.py:11
boost::int32_t x
Definition: BitmapData_as.cpp:434
RangeKind
Kinds of a range.
Definition: Range2d.h:37
T getArea() const
Definition: Range2d.h:626
Range2d< T > & expandTo(T x, T y)
Expand this Range2d to enclose the given point.
Definition: Range2d.h:285
Range2d< T > & shiftX(T offset)
Shift this Range2dangle horizontally.
Definition: Range2d.h:389
Definition: GnashKey.h:133
Range2d< T > & scaleX(float factor)
Scale this Range2d horizontally.
Definition: Range2d.h:415
Range2d(const Range2d< U > &from)
Templated copy constructor, for casting between range types.
Definition: Range2d.h:158
Definition: GnashKey.h:132
friend Range2d< U > Intersection(const Range2d< U > &r1, const Range2d< U > &r2)
Return a rectangle being the intersetion of the two rectangles.
Range2d< T > & growBy(T amount)
Grow this range by the given amout in all directions.
Definition: Range2d.h:508
boost::int32_t y
Definition: BitmapData_as.cpp:435
Range2d< T > & setWorld()
Set the Range2d to the WORLD value.
Definition: Range2d.h:214
T getMinX() const
Get min X ordinate.
Definition: Range2d.h:588
Range2d< T > & setTo(T xmin, T ymin, T xmax, T ymax)
Set coordinates to given values.
Definition: Range2d.h:344
Range2d(RangeKind kind=nullRange)
Construct a Range2d of the given kind.
Definition: Range2d.h:114
Range2d< T > & shrinkBy(T amount)
Shirnk this range by the given amout in all directions.
Definition: Range2d.h:559
Valid range, using finite values.
Definition: Range2d.h:39
friend bool operator!=(const Range2d< U > &r1, const Range2d< U > &r2)
Inequality operator.
bool isWorld() const
Returns true if this is the WORLD Range2d.
Definition: Range2d.h:190
bool isNull() const
Returns true if this is the NULL Range2d.
Definition: Range2d.h:173
T height() const
Return height this Range2dangle.
Definition: Range2d.h:373
Range2d< T > & scale(float factor)
Scale this Range2d in both directions with the same factor.
Definition: Range2d.h:488
void expandTo(const Range2d< T > &r)
Expand this range to include the given Range2d.
Definition: Range2d.h:639
T getMaxY() const
Get max Y ordinate.
Definition: Range2d.h:618
bool operator!=(const Range2d< T > &r1, const Range2d< T > &r2)
Definition: Range2d.h:718