lemon/dim2.h
changeset 248 8fada33fc60a
parent 220 a5d8c039f218
child 250 d0aae16df1bb
equal deleted inserted replaced
6:3f65c25f8b26 7:2bbf50b8bebe
    18 
    18 
    19 #ifndef LEMON_DIM2_H
    19 #ifndef LEMON_DIM2_H
    20 #define LEMON_DIM2_H
    20 #define LEMON_DIM2_H
    21 
    21 
    22 #include <iostream>
    22 #include <iostream>
    23 #include <lemon/core.h>
       
    24 
    23 
    25 ///\ingroup misc
    24 ///\ingroup misc
    26 ///\file
    25 ///\file
    27 ///\brief A simple two dimensional vector and a bounding box implementation
    26 ///\brief A simple two dimensional vector and a bounding box implementation
    28 ///
    27 ///
    43   namespace dim2 {
    42   namespace dim2 {
    44 
    43 
    45   /// \addtogroup misc
    44   /// \addtogroup misc
    46   /// @{
    45   /// @{
    47 
    46 
    48   /// A simple two dimensional vector (plainvector) implementation
    47   /// A simple two dimensional vector (plain vector) implementation
    49 
    48 
    50   /// A simple two dimensional vector (plainvector) implementation
    49   /// A simple two dimensional vector (plain vector) implementation
    51   /// with the usual vector operations.
    50   /// with the usual vector operations.
    52   template<typename T>
    51   template<typename T>
    53     class Point {
    52     class Point {
    54 
    53 
    55     public:
    54     public:
   184   ///\relates Point
   183   ///\relates Point
   185   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
   184   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
   186     return x*u;
   185     return x*u;
   187   }
   186   }
   188 
   187 
   189   ///Read a plainvector from a stream
   188   ///Read a plain vector from a stream
   190 
   189 
   191   ///Read a plainvector from a stream.
   190   ///Read a plain vector from a stream.
   192   ///\relates Point
   191   ///\relates Point
   193   ///
   192   ///
   194   template<typename T>
   193   template<typename T>
   195   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
   194   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
   196     char c;
   195     char c;
   212       is.clear();
   211       is.clear();
   213     }
   212     }
   214     return is;
   213     return is;
   215   }
   214   }
   216 
   215 
   217   ///Write a plainvector to a stream
   216   ///Write a plain vector to a stream
   218 
   217 
   219   ///Write a plainvector to a stream.
   218   ///Write a plain vector to a stream.
   220   ///\relates Point
   219   ///\relates Point
   221   ///
   220   ///
   222   template<typename T>
   221   template<typename T>
   223   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
   222   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
   224   {
   223   {
   259     return Point<T>(z.y,-z.x);
   258     return Point<T>(z.y,-z.x);
   260   }
   259   }
   261 
   260 
   262 
   261 
   263 
   262 
   264   /// A class to calculate or store the bounding box of plainvectors.
   263     /// A class to calculate or store the bounding box of plain vectors.
   265 
   264 
   266   /// A class to calculate or store the bounding box of plainvectors.
   265     /// A class to calculate or store the bounding box of plain vectors.
   267   ///
   266     ///
   268     template<typename T>
   267     template<typename T>
   269     class BoundingBox {
   268     class BoundingBox {
   270       Point<T> bottom_left, top_right;
   269       Point<T> _bottom_left, _top_right;
   271       bool _empty;
   270       bool _empty;
   272     public:
   271     public:
   273 
   272 
   274       ///Default constructor: creates an empty bounding box
   273       ///Default constructor: creates an empty bounding box
   275       BoundingBox() { _empty = true; }
   274       BoundingBox() { _empty = true; }
   276 
   275 
   277       ///Construct an instance from one point
   276       ///Construct an instance from one point
   278       BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
   277       BoundingBox(Point<T> a) {
       
   278         _bottom_left = _top_right = a;
       
   279         _empty = false;
       
   280       }
   279 
   281 
   280       ///Construct an instance from two points
   282       ///Construct an instance from two points
   281 
   283 
   282       ///Construct an instance from two points.
   284       ///Construct an instance from two points.
   283       ///\param a The bottom left corner.
   285       ///\param a The bottom left corner.
   284       ///\param b The top right corner.
   286       ///\param b The top right corner.
   285       ///\warning The coordinates of the bottom left corner must be no more
   287       ///\warning The coordinates of the bottom left corner must be no more
   286       ///than those of the top right one.
   288       ///than those of the top right one.
   287       BoundingBox(Point<T> a,Point<T> b)
   289       BoundingBox(Point<T> a,Point<T> b)
   288       {
   290       {
   289         bottom_left=a;
   291         _bottom_left = a;
   290         top_right=b;
   292         _top_right = b;
   291         _empty = false;
   293         _empty = false;
   292       }
   294       }
   293 
   295 
   294       ///Construct an instance from four numbers
   296       ///Construct an instance from four numbers
   295 
   297 
   300       ///\param t The top of the box.
   302       ///\param t The top of the box.
   301       ///\warning The left side must be no more than the right side and
   303       ///\warning The left side must be no more than the right side and
   302       ///bottom must be no more than the top.
   304       ///bottom must be no more than the top.
   303       BoundingBox(T l,T b,T r,T t)
   305       BoundingBox(T l,T b,T r,T t)
   304       {
   306       {
   305         bottom_left=Point<T>(l,b);
   307         _bottom_left=Point<T>(l,b);
   306         top_right=Point<T>(r,t);
   308         _top_right=Point<T>(r,t);
   307         _empty = false;
   309         _empty = false;
   308       }
   310       }
   309 
   311 
   310       ///Return \c true if the bounding box is empty.
   312       ///Return \c true if the bounding box is empty.
   311 
   313 
   318         return _empty;
   320         return _empty;
   319       }
   321       }
   320 
   322 
   321       ///Make the BoundingBox empty
   323       ///Make the BoundingBox empty
   322       void clear() {
   324       void clear() {
   323         _empty=1;
   325         _empty = true;
   324       }
   326       }
   325 
   327 
   326       ///Give back the bottom left corner of the box
   328       ///Give back the bottom left corner of the box
   327 
   329 
   328       ///Give back the bottom left corner of the box.
   330       ///Give back the bottom left corner of the box.
   329       ///If the bounding box is empty, then the return value is not defined.
   331       ///If the bounding box is empty, then the return value is not defined.
   330       Point<T> bottomLeft() const {
   332       Point<T> bottomLeft() const {
   331         return bottom_left;
   333         return _bottom_left;
   332       }
   334       }
   333 
   335 
   334       ///Set the bottom left corner of the box
   336       ///Set the bottom left corner of the box
   335 
   337 
   336       ///Set the bottom left corner of the box.
   338       ///Set the bottom left corner of the box.
   337       ///It should only be used for non-empty box.
   339       ///\pre The box must not be empty.
   338       void bottomLeft(Point<T> p) {
   340       void bottomLeft(Point<T> p) {
   339         bottom_left = p;
   341         _bottom_left = p;
   340       }
   342       }
   341 
   343 
   342       ///Give back the top right corner of the box
   344       ///Give back the top right corner of the box
   343 
   345 
   344       ///Give back the top right corner of the box.
   346       ///Give back the top right corner of the box.
   345       ///If the bounding box is empty, then the return value is not defined.
   347       ///If the bounding box is empty, then the return value is not defined.
   346       Point<T> topRight() const {
   348       Point<T> topRight() const {
   347         return top_right;
   349         return _top_right;
   348       }
   350       }
   349 
   351 
   350       ///Set the top right corner of the box
   352       ///Set the top right corner of the box
   351 
   353 
   352       ///Set the top right corner of the box.
   354       ///Set the top right corner of the box.
   353       ///It should only be used for non-empty box.
   355       ///\pre The box must not be empty.
   354       void topRight(Point<T> p) {
   356       void topRight(Point<T> p) {
   355         top_right = p;
   357         _top_right = p;
   356       }
   358       }
   357 
   359 
   358       ///Give back the bottom right corner of the box
   360       ///Give back the bottom right corner of the box
   359 
   361 
   360       ///Give back the bottom right corner of the box.
   362       ///Give back the bottom right corner of the box.
   361       ///If the bounding box is empty, then the return value is not defined.
   363       ///If the bounding box is empty, then the return value is not defined.
   362       Point<T> bottomRight() const {
   364       Point<T> bottomRight() const {
   363         return Point<T>(top_right.x,bottom_left.y);
   365         return Point<T>(_top_right.x,_bottom_left.y);
   364       }
   366       }
   365 
   367 
   366       ///Set the bottom right corner of the box
   368       ///Set the bottom right corner of the box
   367 
   369 
   368       ///Set the bottom right corner of the box.
   370       ///Set the bottom right corner of the box.
   369       ///It should only be used for non-empty box.
   371       ///\pre The box must not be empty.
   370       void bottomRight(Point<T> p) {
   372       void bottomRight(Point<T> p) {
   371         top_right.x = p.x;
   373         _top_right.x = p.x;
   372         bottom_left.y = p.y;
   374         _bottom_left.y = p.y;
   373       }
   375       }
   374 
   376 
   375       ///Give back the top left corner of the box
   377       ///Give back the top left corner of the box
   376 
   378 
   377       ///Give back the top left corner of the box.
   379       ///Give back the top left corner of the box.
   378       ///If the bounding box is empty, then the return value is not defined.
   380       ///If the bounding box is empty, then the return value is not defined.
   379       Point<T> topLeft() const {
   381       Point<T> topLeft() const {
   380         return Point<T>(bottom_left.x,top_right.y);
   382         return Point<T>(_bottom_left.x,_top_right.y);
   381       }
   383       }
   382 
   384 
   383       ///Set the top left corner of the box
   385       ///Set the top left corner of the box
   384 
   386 
   385       ///Set the top left corner of the box.
   387       ///Set the top left corner of the box.
   386       ///It should only be used for non-empty box.
   388       ///\pre The box must not be empty.
   387       void topLeft(Point<T> p) {
   389       void topLeft(Point<T> p) {
   388         top_right.y = p.y;
   390         _top_right.y = p.y;
   389         bottom_left.x = p.x;
   391         _bottom_left.x = p.x;
   390       }
   392       }
   391 
   393 
   392       ///Give back the bottom of the box
   394       ///Give back the bottom of the box
   393 
   395 
   394       ///Give back the bottom of the box.
   396       ///Give back the bottom of the box.
   395       ///If the bounding box is empty, then the return value is not defined.
   397       ///If the bounding box is empty, then the return value is not defined.
   396       T bottom() const {
   398       T bottom() const {
   397         return bottom_left.y;
   399         return _bottom_left.y;
   398       }
   400       }
   399 
   401 
   400       ///Set the bottom of the box
   402       ///Set the bottom of the box
   401 
   403 
   402       ///Set the bottom of the box.
   404       ///Set the bottom of the box.
   403       ///It should only be used for non-empty box.
   405       ///\pre The box must not be empty.
   404       void bottom(T t) {
   406       void bottom(T t) {
   405         bottom_left.y = t;
   407         _bottom_left.y = t;
   406       }
   408       }
   407 
   409 
   408       ///Give back the top of the box
   410       ///Give back the top of the box
   409 
   411 
   410       ///Give back the top of the box.
   412       ///Give back the top of the box.
   411       ///If the bounding box is empty, then the return value is not defined.
   413       ///If the bounding box is empty, then the return value is not defined.
   412       T top() const {
   414       T top() const {
   413         return top_right.y;
   415         return _top_right.y;
   414       }
   416       }
   415 
   417 
   416       ///Set the top of the box
   418       ///Set the top of the box
   417 
   419 
   418       ///Set the top of the box.
   420       ///Set the top of the box.
   419       ///It should only be used for non-empty box.
   421       ///\pre The box must not be empty.
   420       void top(T t) {
   422       void top(T t) {
   421         top_right.y = t;
   423         _top_right.y = t;
   422       }
   424       }
   423 
   425 
   424       ///Give back the left side of the box
   426       ///Give back the left side of the box
   425 
   427 
   426       ///Give back the left side of the box.
   428       ///Give back the left side of the box.
   427       ///If the bounding box is empty, then the return value is not defined.
   429       ///If the bounding box is empty, then the return value is not defined.
   428       T left() const {
   430       T left() const {
   429         return bottom_left.x;
   431         return _bottom_left.x;
   430       }
   432       }
   431 
   433 
   432       ///Set the left side of the box
   434       ///Set the left side of the box
   433 
   435 
   434       ///Set the left side of the box.
   436       ///Set the left side of the box.
   435       ///It should only be used for non-empty box.
   437       ///\pre The box must not be empty.
   436       void left(T t) {
   438       void left(T t) {
   437         bottom_left.x = t;
   439         _bottom_left.x = t;
   438       }
   440       }
   439 
   441 
   440       /// Give back the right side of the box
   442       /// Give back the right side of the box
   441 
   443 
   442       /// Give back the right side of the box.
   444       /// Give back the right side of the box.
   443       ///If the bounding box is empty, then the return value is not defined.
   445       ///If the bounding box is empty, then the return value is not defined.
   444       T right() const {
   446       T right() const {
   445         return top_right.x;
   447         return _top_right.x;
   446       }
   448       }
   447 
   449 
   448       ///Set the right side of the box
   450       ///Set the right side of the box
   449 
   451 
   450       ///Set the right side of the box.
   452       ///Set the right side of the box.
   451       ///It should only be used for non-empty box.
   453       ///\pre The box must not be empty.
   452       void right(T t) {
   454       void right(T t) {
   453         top_right.x = t;
   455         _top_right.x = t;
   454       }
   456       }
   455 
   457 
   456       ///Give back the height of the box
   458       ///Give back the height of the box
   457 
   459 
   458       ///Give back the height of the box.
   460       ///Give back the height of the box.
   459       ///If the bounding box is empty, then the return value is not defined.
   461       ///If the bounding box is empty, then the return value is not defined.
   460       T height() const {
   462       T height() const {
   461         return top_right.y-bottom_left.y;
   463         return _top_right.y-_bottom_left.y;
   462       }
   464       }
   463 
   465 
   464       ///Give back the width of the box
   466       ///Give back the width of the box
   465 
   467 
   466       ///Give back the width of the box.
   468       ///Give back the width of the box.
   467       ///If the bounding box is empty, then the return value is not defined.
   469       ///If the bounding box is empty, then the return value is not defined.
   468       T width() const {
   470       T width() const {
   469         return top_right.x-bottom_left.x;
   471         return _top_right.x-_bottom_left.x;
   470       }
   472       }
   471 
   473 
   472       ///Checks whether a point is inside a bounding box
   474       ///Checks whether a point is inside a bounding box
   473       bool inside(const Point<T>& u) const {
   475       bool inside(const Point<T>& u) const {
   474         if (_empty)
   476         if (_empty)
   475           return false;
   477           return false;
   476         else{
   478         else {
   477           return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
   479           return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
   478               (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
   480                    (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
   479         }
   481         }
   480       }
   482       }
   481 
   483 
   482       ///Increments a bounding box with a point
   484       ///Increments a bounding box with a point
   483 
   485 
   484       ///Increments a bounding box with a point.
   486       ///Increments a bounding box with a point.
   485       ///
   487       ///
   486       BoundingBox& add(const Point<T>& u){
   488       BoundingBox& add(const Point<T>& u){
   487         if (_empty){
   489         if (_empty) {
   488           bottom_left=top_right=u;
   490           _bottom_left = _top_right = u;
   489           _empty = false;
   491           _empty = false;
   490         }
   492         }
   491         else{
   493         else {
   492           if (bottom_left.x > u.x) bottom_left.x = u.x;
   494           if (_bottom_left.x > u.x) _bottom_left.x = u.x;
   493           if (bottom_left.y > u.y) bottom_left.y = u.y;
   495           if (_bottom_left.y > u.y) _bottom_left.y = u.y;
   494           if (top_right.x < u.x) top_right.x = u.x;
   496           if (_top_right.x < u.x) _top_right.x = u.x;
   495           if (top_right.y < u.y) top_right.y = u.y;
   497           if (_top_right.y < u.y) _top_right.y = u.y;
   496         }
   498         }
   497         return *this;
   499         return *this;
   498       }
   500       }
   499 
   501 
   500       ///Increments a bounding box to contain another bounding box
   502       ///Increments a bounding box to contain another bounding box
   501 
   503 
   502       ///Increments a bounding box to contain another bounding box.
   504       ///Increments a bounding box to contain another bounding box.
   503       ///
   505       ///
   504       BoundingBox& add(const BoundingBox &u){
   506       BoundingBox& add(const BoundingBox &u){
   505         if ( !u.empty() ){
   507         if ( !u.empty() ){
   506           this->add(u.bottomLeft());
   508           add(u._bottom_left);
   507           this->add(u.topRight());
   509           add(u._top_right);
   508         }
   510         }
   509         return *this;
   511         return *this;
   510       }
   512       }
   511 
   513 
   512       ///Intersection of two bounding boxes
   514       ///Intersection of two bounding boxes
   513 
   515 
   514       ///Intersection of two bounding boxes.
   516       ///Intersection of two bounding boxes.
   515       ///
   517       ///
   516       BoundingBox operator&(const BoundingBox& u) const {
   518       BoundingBox operator&(const BoundingBox& u) const {
   517         BoundingBox b;
   519         BoundingBox b;
   518         if (this->_empty || u._empty) {
   520         if (_empty || u._empty) {
   519           b._empty = true;
   521           b._empty = true;
   520         } else {
   522         } else {
   521           b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
   523           b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
   522           b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
   524           b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
   523           b.top_right.x = std::min(this->top_right.x,u.top_right.x);
   525           b._top_right.x = std::min(_top_right.x, u._top_right.x);
   524           b.top_right.y = std::min(this->top_right.y,u.top_right.y);
   526           b._top_right.y = std::min(_top_right.y, u._top_right.y);
   525           b._empty = b.bottom_left.x > b.top_right.x ||
   527           b._empty = b._bottom_left.x > b._top_right.x ||
   526                      b.bottom_left.y > b.top_right.y;
   528                      b._bottom_left.y > b._top_right.y;
   527         }
   529         }
   528         return b;
   530         return b;
   529       }
   531       }
   530 
   532 
   531     };//class Boundingbox
   533     };//class Boundingbox