lemon/dim2.h
changeset 307 47ec522b838e
parent 250 d0aae16df1bb
child 313 64f8f7cc6168
equal deleted inserted replaced
8:dd9c19843b40 9:6f3cb84bd930
    26 ///\brief A simple two dimensional vector and a bounding box implementation
    26 ///\brief A simple two dimensional vector and a bounding box implementation
    27 ///
    27 ///
    28 /// The class \ref lemon::dim2::Point "dim2::Point" implements
    28 /// The class \ref lemon::dim2::Point "dim2::Point" implements
    29 /// a two dimensional vector with the usual operations.
    29 /// a two dimensional vector with the usual operations.
    30 ///
    30 ///
    31 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    31 /// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
    32 /// can be used to determine
       
    33 /// the rectangular bounding box of a set of
    32 /// the rectangular bounding box of a set of
    34 /// \ref lemon::dim2::Point "dim2::Point"'s.
    33 /// \ref lemon::dim2::Point "dim2::Point"'s.
    35 
    34 
    36 namespace lemon {
    35 namespace lemon {
    37 
    36 
    42   namespace dim2 {
    41   namespace dim2 {
    43 
    42 
    44   /// \addtogroup misc
    43   /// \addtogroup misc
    45   /// @{
    44   /// @{
    46 
    45 
    47   /// A simple two dimensional vector (plain vector) implementation
    46   /// Two dimensional vector (plain vector)
    48 
    47 
    49   /// A simple two dimensional vector (plain vector) implementation
    48   /// A simple two dimensional vector (plain vector) implementation
    50   /// with the usual vector operations.
    49   /// with the usual vector operations.
    51   template<typename T>
    50   template<typename T>
    52     class Point {
    51     class Point {
   258     return Point<T>(z.y,-z.x);
   257     return Point<T>(z.y,-z.x);
   259   }
   258   }
   260 
   259 
   261 
   260 
   262 
   261 
   263     /// A class to calculate or store the bounding box of plain vectors.
   262   /// Bounding box of plain vectors (\ref Point points).
   264 
   263 
   265     /// A class to calculate or store the bounding box of plain vectors.
   264   /// A class to calculate or store the bounding box of plain vectors
   266     ///
   265   /// (\ref Point points).
   267     template<typename T>
   266   template<typename T>
   268     class BoundingBox {
   267   class Box {
   269       Point<T> _bottom_left, _top_right;
   268       Point<T> _bottom_left, _top_right;
   270       bool _empty;
   269       bool _empty;
   271     public:
   270     public:
   272 
   271 
   273       ///Default constructor: creates an empty bounding box
   272       ///Default constructor: creates an empty box
   274       BoundingBox() { _empty = true; }
   273       Box() { _empty = true; }
   275 
   274 
   276       ///Construct an instance from one point
   275       ///Construct a box from one point
   277       BoundingBox(Point<T> a) {
   276       Box(Point<T> a) {
   278         _bottom_left = _top_right = a;
   277         _bottom_left = _top_right = a;
   279         _empty = false;
   278         _empty = false;
   280       }
   279       }
   281 
   280 
   282       ///Construct an instance from two points
   281       ///Construct a box from two points
   283 
   282 
   284       ///Construct an instance from two points.
   283       ///Construct a box from two points.
   285       ///\param a The bottom left corner.
   284       ///\param a The bottom left corner.
   286       ///\param b The top right corner.
   285       ///\param b The top right corner.
   287       ///\warning The coordinates of the bottom left corner must be no more
   286       ///\warning The coordinates of the bottom left corner must be no more
   288       ///than those of the top right one.
   287       ///than those of the top right one.
   289       BoundingBox(Point<T> a,Point<T> b)
   288       Box(Point<T> a,Point<T> b)
   290       {
   289       {
   291         _bottom_left = a;
   290         _bottom_left = a;
   292         _top_right = b;
   291         _top_right = b;
   293         _empty = false;
   292         _empty = false;
   294       }
   293       }
   295 
   294 
   296       ///Construct an instance from four numbers
   295       ///Construct a box from four numbers
   297 
   296 
   298       ///Construct an instance from four numbers.
   297       ///Construct a box from four numbers.
   299       ///\param l The left side of the box.
   298       ///\param l The left side of the box.
   300       ///\param b The bottom of the box.
   299       ///\param b The bottom of the box.
   301       ///\param r The right side of the box.
   300       ///\param r The right side of the box.
   302       ///\param t The top of the box.
   301       ///\param t The top of the box.
   303       ///\warning The left side must be no more than the right side and
   302       ///\warning The left side must be no more than the right side and
   304       ///bottom must be no more than the top.
   303       ///bottom must be no more than the top.
   305       BoundingBox(T l,T b,T r,T t)
   304       Box(T l,T b,T r,T t)
   306       {
   305       {
   307         _bottom_left=Point<T>(l,b);
   306         _bottom_left=Point<T>(l,b);
   308         _top_right=Point<T>(r,t);
   307         _top_right=Point<T>(r,t);
   309         _empty = false;
   308         _empty = false;
   310       }
   309       }
   311 
   310 
   312       ///Return \c true if the bounding box is empty.
   311       ///Return \c true if the box is empty.
   313 
   312 
   314       ///Return \c true if the bounding box is empty (i.e. return \c false
   313       ///Return \c true if the box is empty (i.e. return \c false
   315       ///if at least one point was added to the box or the coordinates of
   314       ///if at least one point was added to the box or the coordinates of
   316       ///the box were set).
   315       ///the box were set).
   317       ///
   316       ///
   318       ///The coordinates of an empty bounding box are not defined.
   317       ///The coordinates of an empty box are not defined.
   319       bool empty() const {
   318       bool empty() const {
   320         return _empty;
   319         return _empty;
   321       }
   320       }
   322 
   321 
   323       ///Make the BoundingBox empty
   322       ///Make the box empty
   324       void clear() {
   323       void clear() {
   325         _empty = true;
   324         _empty = true;
   326       }
   325       }
   327 
   326 
   328       ///Give back the bottom left corner of the box
   327       ///Give back the bottom left corner of the box
   329 
   328 
   330       ///Give back the bottom left corner of the box.
   329       ///Give back the bottom left corner of the box.
   331       ///If the bounding box is empty, then the return value is not defined.
   330       ///If the box is empty, then the return value is not defined.
   332       Point<T> bottomLeft() const {
   331       Point<T> bottomLeft() const {
   333         return _bottom_left;
   332         return _bottom_left;
   334       }
   333       }
   335 
   334 
   336       ///Set the bottom left corner of the box
   335       ///Set the bottom left corner of the box
   342       }
   341       }
   343 
   342 
   344       ///Give back the top right corner of the box
   343       ///Give back the top right corner of the box
   345 
   344 
   346       ///Give back the top right corner of the box.
   345       ///Give back the top right corner of the box.
   347       ///If the bounding box is empty, then the return value is not defined.
   346       ///If the box is empty, then the return value is not defined.
   348       Point<T> topRight() const {
   347       Point<T> topRight() const {
   349         return _top_right;
   348         return _top_right;
   350       }
   349       }
   351 
   350 
   352       ///Set the top right corner of the box
   351       ///Set the top right corner of the box
   358       }
   357       }
   359 
   358 
   360       ///Give back the bottom right corner of the box
   359       ///Give back the bottom right corner of the box
   361 
   360 
   362       ///Give back the bottom right corner of the box.
   361       ///Give back the bottom right corner of the box.
   363       ///If the bounding box is empty, then the return value is not defined.
   362       ///If the box is empty, then the return value is not defined.
   364       Point<T> bottomRight() const {
   363       Point<T> bottomRight() const {
   365         return Point<T>(_top_right.x,_bottom_left.y);
   364         return Point<T>(_top_right.x,_bottom_left.y);
   366       }
   365       }
   367 
   366 
   368       ///Set the bottom right corner of the box
   367       ///Set the bottom right corner of the box
   375       }
   374       }
   376 
   375 
   377       ///Give back the top left corner of the box
   376       ///Give back the top left corner of the box
   378 
   377 
   379       ///Give back the top left corner of the box.
   378       ///Give back the top left corner of the box.
   380       ///If the bounding box is empty, then the return value is not defined.
   379       ///If the box is empty, then the return value is not defined.
   381       Point<T> topLeft() const {
   380       Point<T> topLeft() const {
   382         return Point<T>(_bottom_left.x,_top_right.y);
   381         return Point<T>(_bottom_left.x,_top_right.y);
   383       }
   382       }
   384 
   383 
   385       ///Set the top left corner of the box
   384       ///Set the top left corner of the box
   392       }
   391       }
   393 
   392 
   394       ///Give back the bottom of the box
   393       ///Give back the bottom of the box
   395 
   394 
   396       ///Give back the bottom of the box.
   395       ///Give back the bottom of the box.
   397       ///If the bounding box is empty, then the return value is not defined.
   396       ///If the box is empty, then the return value is not defined.
   398       T bottom() const {
   397       T bottom() const {
   399         return _bottom_left.y;
   398         return _bottom_left.y;
   400       }
   399       }
   401 
   400 
   402       ///Set the bottom of the box
   401       ///Set the bottom of the box
   408       }
   407       }
   409 
   408 
   410       ///Give back the top of the box
   409       ///Give back the top of the box
   411 
   410 
   412       ///Give back the top of the box.
   411       ///Give back the top of the box.
   413       ///If the bounding box is empty, then the return value is not defined.
   412       ///If the box is empty, then the return value is not defined.
   414       T top() const {
   413       T top() const {
   415         return _top_right.y;
   414         return _top_right.y;
   416       }
   415       }
   417 
   416 
   418       ///Set the top of the box
   417       ///Set the top of the box
   424       }
   423       }
   425 
   424 
   426       ///Give back the left side of the box
   425       ///Give back the left side of the box
   427 
   426 
   428       ///Give back the left side of the box.
   427       ///Give back the left side of the box.
   429       ///If the bounding box is empty, then the return value is not defined.
   428       ///If the box is empty, then the return value is not defined.
   430       T left() const {
   429       T left() const {
   431         return _bottom_left.x;
   430         return _bottom_left.x;
   432       }
   431       }
   433 
   432 
   434       ///Set the left side of the box
   433       ///Set the left side of the box
   440       }
   439       }
   441 
   440 
   442       /// Give back the right side of the box
   441       /// Give back the right side of the box
   443 
   442 
   444       /// Give back the right side of the box.
   443       /// Give back the right side of the box.
   445       ///If the bounding box is empty, then the return value is not defined.
   444       ///If the box is empty, then the return value is not defined.
   446       T right() const {
   445       T right() const {
   447         return _top_right.x;
   446         return _top_right.x;
   448       }
   447       }
   449 
   448 
   450       ///Set the right side of the box
   449       ///Set the right side of the box
   456       }
   455       }
   457 
   456 
   458       ///Give back the height of the box
   457       ///Give back the height of the box
   459 
   458 
   460       ///Give back the height of the box.
   459       ///Give back the height of the box.
   461       ///If the bounding box is empty, then the return value is not defined.
   460       ///If the box is empty, then the return value is not defined.
   462       T height() const {
   461       T height() const {
   463         return _top_right.y-_bottom_left.y;
   462         return _top_right.y-_bottom_left.y;
   464       }
   463       }
   465 
   464 
   466       ///Give back the width of the box
   465       ///Give back the width of the box
   467 
   466 
   468       ///Give back the width of the box.
   467       ///Give back the width of the box.
   469       ///If the bounding box is empty, then the return value is not defined.
   468       ///If the box is empty, then the return value is not defined.
   470       T width() const {
   469       T width() const {
   471         return _top_right.x-_bottom_left.x;
   470         return _top_right.x-_bottom_left.x;
   472       }
   471       }
   473 
   472 
   474       ///Checks whether a point is inside a bounding box
   473       ///Checks whether a point is inside the box
   475       bool inside(const Point<T>& u) const {
   474       bool inside(const Point<T>& u) const {
   476         if (_empty)
   475         if (_empty)
   477           return false;
   476           return false;
   478         else {
   477         else {
   479           return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
   478           return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
   480                    (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
   479                    (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
   481         }
   480         }
   482       }
   481       }
   483 
   482 
   484       ///Increments a bounding box with a point
   483       ///Increments the box with a point
   485 
   484 
   486       ///Increments a bounding box with a point.
   485       ///Increments the box with a point.
   487       ///
   486       ///
   488       BoundingBox& add(const Point<T>& u){
   487       Box& add(const Point<T>& u){
   489         if (_empty) {
   488         if (_empty) {
   490           _bottom_left = _top_right = u;
   489           _bottom_left = _top_right = u;
   491           _empty = false;
   490           _empty = false;
   492         }
   491         }
   493         else {
   492         else {
   497           if (_top_right.y < u.y) _top_right.y = u.y;
   496           if (_top_right.y < u.y) _top_right.y = u.y;
   498         }
   497         }
   499         return *this;
   498         return *this;
   500       }
   499       }
   501 
   500 
   502       ///Increments a bounding box to contain another bounding box
   501       ///Increments the box to contain another box
   503 
   502 
   504       ///Increments a bounding box to contain another bounding box.
   503       ///Increments the box to contain another box.
   505       ///
   504       ///
   506       BoundingBox& add(const BoundingBox &u){
   505       Box& add(const Box &u){
   507         if ( !u.empty() ){
   506         if ( !u.empty() ){
   508           add(u._bottom_left);
   507           add(u._bottom_left);
   509           add(u._top_right);
   508           add(u._top_right);
   510         }
   509         }
   511         return *this;
   510         return *this;
   512       }
   511       }
   513 
   512 
   514       ///Intersection of two bounding boxes
   513       ///Intersection of two boxes
   515 
   514 
   516       ///Intersection of two bounding boxes.
   515       ///Intersection of two boxes.
   517       ///
   516       ///
   518       BoundingBox operator&(const BoundingBox& u) const {
   517       Box operator&(const Box& u) const {
   519         BoundingBox b;
   518         Box b;
   520         if (_empty || u._empty) {
   519         if (_empty || u._empty) {
   521           b._empty = true;
   520           b._empty = true;
   522         } else {
   521         } else {
   523           b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
   522           b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
   524           b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
   523           b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
   528                      b._bottom_left.y > b._top_right.y;
   527                      b._bottom_left.y > b._top_right.y;
   529         }
   528         }
   530         return b;
   529         return b;
   531       }
   530       }
   532 
   531 
   533     };//class Boundingbox
   532   };//class Box
   534 
   533 
   535 
   534 
   536   ///Read a bounding box from a stream
   535   ///Read a box from a stream
   537 
   536 
   538   ///Read a bounding box from a stream.
   537   ///Read a box from a stream.
   539   ///\relates BoundingBox
   538   ///\relates Box
   540   template<typename T>
   539   template<typename T>
   541   inline std::istream& operator>>(std::istream &is, BoundingBox<T>& b) {
   540   inline std::istream& operator>>(std::istream &is, Box<T>& b) {
   542     char c;
   541     char c;
   543     Point<T> p;
   542     Point<T> p;
   544     if (is >> c) {
   543     if (is >> c) {
   545       if (c != '(') is.putback(c);
   544       if (c != '(') is.putback(c);
   546     } else {
   545     } else {
   561       is.clear();
   560       is.clear();
   562     }
   561     }
   563     return is;
   562     return is;
   564   }
   563   }
   565 
   564 
   566   ///Write a bounding box to a stream
   565   ///Write a box to a stream
   567 
   566 
   568   ///Write a bounding box to a stream.
   567   ///Write a box to a stream.
   569   ///\relates BoundingBox
   568   ///\relates Box
   570   template<typename T>
   569   template<typename T>
   571   inline std::ostream& operator<<(std::ostream &os, const BoundingBox<T>& b)
   570   inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)
   572   {
   571   {
   573     os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
   572     os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
   574     return os;
   573     return os;
   575   }
   574   }
   576 
   575