lemon/dim2.h
changeset 21 40d6f625e549
child 15 062f361aa520
equal deleted inserted replaced
-1:000000000000 0:825b3e2afbd8
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2007
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 #ifndef LEMON_DIM2_H
       
    20 #define LEMON_DIM2_H
       
    21 
       
    22 #include <iostream>
       
    23 #include <lemon/bits/utility.h>
       
    24 
       
    25 ///\ingroup misc
       
    26 ///\file
       
    27 ///\brief A simple two dimensional vector and a bounding box implementation 
       
    28 ///
       
    29 /// The class \ref lemon::dim2::Point "dim2::Point" implements
       
    30 ///a two dimensional vector with the usual
       
    31 /// operations.
       
    32 ///
       
    33 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
       
    34 /// can be used to determine
       
    35 /// the rectangular bounding box of a set of
       
    36 /// \ref lemon::dim2::Point "dim2::Point"'s.
       
    37 ///
       
    38 ///\author Attila Bernath
       
    39 
       
    40 
       
    41 namespace lemon {
       
    42 
       
    43   ///Tools for handling two dimensional coordinates
       
    44 
       
    45   ///This namespace is a storage of several
       
    46   ///tools for handling two dimensional coordinates
       
    47   namespace dim2 {
       
    48 
       
    49   /// \addtogroup misc
       
    50   /// @{
       
    51 
       
    52   /// A simple two dimensional vector (plainvector) implementation
       
    53 
       
    54   /// A simple two dimensional vector (plainvector) implementation
       
    55   ///with the usual vector
       
    56   /// operators.
       
    57   ///
       
    58   template<typename T>
       
    59     class Point {
       
    60 
       
    61     public:
       
    62 
       
    63       typedef T Value;
       
    64 
       
    65       ///First co-ordinate
       
    66       T x;
       
    67       ///Second co-ordinate
       
    68       T y;     
       
    69       
       
    70       ///Default constructor
       
    71       Point() {}
       
    72 
       
    73       ///Construct an instance from coordinates
       
    74       Point(T a, T b) : x(a), y(b) { }
       
    75 
       
    76       ///The dimension of the vector.
       
    77 
       
    78       ///This class give back always 2.
       
    79       ///
       
    80       int size() const { return 2; }
       
    81 
       
    82       ///Subscripting operator
       
    83 
       
    84       ///\c p[0] is \c p.x and \c p[1] is \c p.y
       
    85       ///
       
    86       T& operator[](int idx) { return idx == 0 ? x : y; }
       
    87 
       
    88       ///Const subscripting operator
       
    89 
       
    90       ///\c p[0] is \c p.x and \c p[1] is \c p.y
       
    91       ///
       
    92       const T& operator[](int idx) const { return idx == 0 ? x : y; }
       
    93 
       
    94       ///Conversion constructor
       
    95       template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
       
    96 
       
    97       ///Give back the square of the norm of the vector
       
    98       T normSquare() const {
       
    99         return x*x+y*y;
       
   100       }
       
   101   
       
   102       ///Increment the left hand side by u
       
   103       Point<T>& operator +=(const Point<T>& u) {
       
   104         x += u.x;
       
   105         y += u.y;
       
   106         return *this;
       
   107       }
       
   108   
       
   109       ///Decrement the left hand side by u
       
   110       Point<T>& operator -=(const Point<T>& u) {
       
   111         x -= u.x;
       
   112         y -= u.y;
       
   113         return *this;
       
   114       }
       
   115 
       
   116       ///Multiply the left hand side with a scalar
       
   117       Point<T>& operator *=(const T &u) {
       
   118         x *= u;
       
   119         y *= u;
       
   120         return *this;
       
   121       }
       
   122 
       
   123       ///Divide the left hand side by a scalar
       
   124       Point<T>& operator /=(const T &u) {
       
   125         x /= u;
       
   126         y /= u;
       
   127         return *this;
       
   128       }
       
   129   
       
   130       ///Return the scalar product of two vectors
       
   131       T operator *(const Point<T>& u) const {
       
   132         return x*u.x+y*u.y;
       
   133       }
       
   134   
       
   135       ///Return the sum of two vectors
       
   136       Point<T> operator+(const Point<T> &u) const {
       
   137         Point<T> b=*this;
       
   138         return b+=u;
       
   139       }
       
   140 
       
   141       ///Return the neg of the vectors
       
   142       Point<T> operator-() const {
       
   143         Point<T> b=*this;
       
   144         b.x=-b.x; b.y=-b.y;
       
   145         return b;
       
   146       }
       
   147 
       
   148       ///Return the difference of two vectors
       
   149       Point<T> operator-(const Point<T> &u) const {
       
   150         Point<T> b=*this;
       
   151         return b-=u;
       
   152       }
       
   153 
       
   154       ///Return a vector multiplied by a scalar
       
   155       Point<T> operator*(const T &u) const {
       
   156         Point<T> b=*this;
       
   157         return b*=u;
       
   158       }
       
   159 
       
   160       ///Return a vector divided by a scalar
       
   161       Point<T> operator/(const T &u) const {
       
   162         Point<T> b=*this;
       
   163         return b/=u;
       
   164       }
       
   165 
       
   166       ///Test equality
       
   167       bool operator==(const Point<T> &u) const {
       
   168         return (x==u.x) && (y==u.y);
       
   169       }
       
   170 
       
   171       ///Test inequality
       
   172       bool operator!=(Point u) const {
       
   173         return  (x!=u.x) || (y!=u.y);
       
   174       }
       
   175 
       
   176     };
       
   177 
       
   178   ///Return an Point 
       
   179 
       
   180   ///Return an Point
       
   181   ///\relates Point
       
   182   template <typename T>
       
   183   inline Point<T> makePoint(const T& x, const T& y) {
       
   184     return Point<T>(x, y);
       
   185   }
       
   186 
       
   187   ///Return a vector multiplied by a scalar
       
   188 
       
   189   ///Return a vector multiplied by a scalar
       
   190   ///\relates Point
       
   191   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
       
   192     return x*u;
       
   193   }
       
   194 
       
   195   ///Read a plainvector from a stream
       
   196 
       
   197   ///Read a plainvector from a stream
       
   198   ///\relates Point
       
   199   ///
       
   200   template<typename T>
       
   201   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
       
   202     char c;
       
   203     if (is >> c) {
       
   204       if (c != '(') is.putback(c);
       
   205     } else {
       
   206       is.clear();
       
   207     }
       
   208     if (!(is >> z.x)) return is;
       
   209     if (is >> c) {
       
   210       if (c != ',') is.putback(c);
       
   211     } else {
       
   212       is.clear();
       
   213     }
       
   214     if (!(is >> z.y)) return is;
       
   215     if (is >> c) {
       
   216       if (c != ')') is.putback(c);
       
   217     } else {
       
   218       is.clear();
       
   219     }
       
   220     return is;
       
   221   }
       
   222 
       
   223   ///Write a plainvector to a stream
       
   224 
       
   225   ///Write a plainvector to a stream
       
   226   ///\relates Point
       
   227   ///
       
   228   template<typename T>
       
   229   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
       
   230   {
       
   231     os << "(" << z.x << ", " << z.y << ")";
       
   232     return os;
       
   233   }
       
   234 
       
   235   ///Rotate by 90 degrees
       
   236 
       
   237   ///Returns its parameter rotated by 90 degrees in positive direction.
       
   238   ///\relates Point
       
   239   ///
       
   240   template<typename T>
       
   241   inline Point<T> rot90(const Point<T> &z)
       
   242   {
       
   243     return Point<T>(-z.y,z.x);
       
   244   }
       
   245 
       
   246   ///Rotate by 180 degrees
       
   247 
       
   248   ///Returns its parameter rotated by 180 degrees.
       
   249   ///\relates Point
       
   250   ///
       
   251   template<typename T>
       
   252   inline Point<T> rot180(const Point<T> &z)
       
   253   {
       
   254     return Point<T>(-z.x,-z.y);
       
   255   }
       
   256 
       
   257   ///Rotate by 270 degrees
       
   258 
       
   259   ///Returns its parameter rotated by 90 degrees in negative direction.
       
   260   ///\relates Point
       
   261   ///
       
   262   template<typename T>
       
   263   inline Point<T> rot270(const Point<T> &z)
       
   264   {
       
   265     return Point<T>(z.y,-z.x);
       
   266   }
       
   267 
       
   268   
       
   269 
       
   270   /// A class to calculate or store the bounding box of plainvectors.
       
   271 
       
   272   /// A class to calculate or store the bounding box of plainvectors.
       
   273   ///
       
   274   ///\author Attila Bernath
       
   275     template<typename T>
       
   276     class BoundingBox {
       
   277       Point<T> bottom_left, top_right;
       
   278       bool _empty;
       
   279     public:
       
   280       
       
   281       ///Default constructor: creates an empty bounding box
       
   282       BoundingBox() { _empty = true; }
       
   283 
       
   284       ///Construct an instance from one point
       
   285       BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
       
   286       
       
   287       ///Construct an instance from two points
       
   288       
       
   289       ///Construct an instance from two points
       
   290       ///\warning The coordinates of the bottom-left corner must be no more
       
   291       ///than those of the top-right one
       
   292       BoundingBox(Point<T> a,Point<T> b)
       
   293       {
       
   294 	bottom_left=a;
       
   295 	top_right=b;
       
   296 	_empty = false;
       
   297       }
       
   298       
       
   299       ///Construct an instance from four numbers
       
   300 
       
   301       ///Construct an instance from four numbers
       
   302       ///\warning The coordinates of the bottom-left corner must be no more
       
   303       ///than those of the top-right one
       
   304       BoundingBox(T l,T b,T r,T t)
       
   305       {
       
   306 	bottom_left=Point<T>(l,b);
       
   307 	top_right=Point<T>(r,t);
       
   308 	_empty = false;
       
   309       }
       
   310       
       
   311       ///Were any points added?
       
   312       bool empty() const {
       
   313         return _empty;
       
   314       }
       
   315       
       
   316       ///Make the BoundingBox empty
       
   317       void clear() {
       
   318         _empty=1;
       
   319       }
       
   320 
       
   321       ///Give back the bottom left corner
       
   322 
       
   323       ///Give back the bottom left corner.
       
   324       ///If the bounding box is empty, then the return value is not defined.
       
   325       Point<T> bottomLeft() const {
       
   326         return bottom_left;
       
   327       }
       
   328 
       
   329       ///Set the bottom left corner
       
   330 
       
   331       ///Set the bottom left corner.
       
   332       ///It should only bee used for non-empty box.
       
   333       void bottomLeft(Point<T> p) {
       
   334 	bottom_left = p;
       
   335       }
       
   336 
       
   337       ///Give back the top right corner
       
   338 
       
   339       ///Give back the top right corner.
       
   340       ///If the bounding box is empty, then the return value is not defined.
       
   341       Point<T> topRight() const {
       
   342         return top_right;
       
   343       }
       
   344 
       
   345       ///Set the top right corner
       
   346 
       
   347       ///Set the top right corner.
       
   348       ///It should only bee used for non-empty box.
       
   349       void topRight(Point<T> p) {
       
   350 	top_right = p;
       
   351       }
       
   352 
       
   353       ///Give back the bottom right corner
       
   354 
       
   355       ///Give back the bottom right corner.
       
   356       ///If the bounding box is empty, then the return value is not defined.
       
   357       Point<T> bottomRight() const {
       
   358         return Point<T>(top_right.x,bottom_left.y);
       
   359       }
       
   360 
       
   361       ///Set the bottom right corner
       
   362 
       
   363       ///Set the bottom right corner.
       
   364       ///It should only bee used for non-empty box.
       
   365       void bottomRight(Point<T> p) {
       
   366 	top_right.x = p.x;
       
   367 	bottom_left.y = p.y;
       
   368       }
       
   369  
       
   370       ///Give back the top left corner
       
   371 
       
   372       ///Give back the top left corner.
       
   373       ///If the bounding box is empty, then the return value is not defined.
       
   374       Point<T> topLeft() const {
       
   375         return Point<T>(bottom_left.x,top_right.y);
       
   376       }
       
   377 
       
   378       ///Set the top left corner
       
   379 
       
   380       ///Set the top left corner.
       
   381       ///It should only bee used for non-empty box.
       
   382       void topLeft(Point<T> p) {
       
   383 	top_right.y = p.y;
       
   384 	bottom_left.x = p.x;
       
   385       }
       
   386 
       
   387       ///Give back the bottom of the box
       
   388 
       
   389       ///Give back the bottom of the box.
       
   390       ///If the bounding box is empty, then the return value is not defined.
       
   391       T bottom() const {
       
   392         return bottom_left.y;
       
   393       }
       
   394 
       
   395       ///Set the bottom of the box
       
   396 
       
   397       ///Set the bottom of the box.
       
   398       ///It should only bee used for non-empty box.
       
   399       void bottom(T t) {
       
   400 	bottom_left.y = t;
       
   401       }
       
   402 
       
   403       ///Give back the top of the box
       
   404 
       
   405       ///Give back the top of the box.
       
   406       ///If the bounding box is empty, then the return value is not defined.
       
   407       T top() const {
       
   408         return top_right.y;
       
   409       }
       
   410 
       
   411       ///Set the top of the box
       
   412 
       
   413       ///Set the top of the box.
       
   414       ///It should only bee used for non-empty box.
       
   415       void top(T t) {
       
   416 	top_right.y = t;
       
   417       }
       
   418 
       
   419       ///Give back the left side of the box
       
   420 
       
   421       ///Give back the left side of the box.
       
   422       ///If the bounding box is empty, then the return value is not defined.
       
   423       T left() const {
       
   424         return bottom_left.x;
       
   425       }
       
   426  
       
   427       ///Set the left side of the box
       
   428 
       
   429       ///Set the left side of the box.
       
   430       ///It should only bee used for non-empty box
       
   431       void left(T t) {
       
   432 	bottom_left.x = t;
       
   433       }
       
   434 
       
   435       /// Give back the right side of the box
       
   436 
       
   437       /// Give back the right side of the box.
       
   438       ///If the bounding box is empty, then the return value is not defined.
       
   439       T right() const {
       
   440         return top_right.x;
       
   441       }
       
   442 
       
   443       ///Set the right side of the box
       
   444 
       
   445       ///Set the right side of the box.
       
   446       ///It should only bee used for non-empty box
       
   447       void right(T t) {
       
   448 	top_right.x = t;
       
   449       }
       
   450 
       
   451       ///Give back the height of the box
       
   452 
       
   453       ///Give back the height of the box.
       
   454       ///If the bounding box is empty, then the return value is not defined.
       
   455       T height() const {
       
   456         return top_right.y-bottom_left.y;
       
   457       }
       
   458 
       
   459       ///Give back the width of the box
       
   460 
       
   461       ///Give back the width of the box.
       
   462       ///If the bounding box is empty, then the return value is not defined.
       
   463       T width() const {
       
   464         return top_right.x-bottom_left.x;
       
   465       }
       
   466 
       
   467       ///Checks whether a point is inside a bounding box
       
   468       bool inside(const Point<T>& u){
       
   469         if (_empty)
       
   470           return false;
       
   471         else{
       
   472           return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
       
   473               (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
       
   474         }
       
   475       }
       
   476   
       
   477       ///Increments a bounding box with a point
       
   478       BoundingBox& add(const Point<T>& u){
       
   479         if (_empty){
       
   480           bottom_left=top_right=u;
       
   481           _empty = false;
       
   482         }
       
   483         else{
       
   484           if (bottom_left.x > u.x) bottom_left.x = u.x;
       
   485           if (bottom_left.y > u.y) bottom_left.y = u.y;
       
   486           if (top_right.x < u.x) top_right.x = u.x;
       
   487           if (top_right.y < u.y) top_right.y = u.y;
       
   488         }
       
   489         return *this;
       
   490       }
       
   491     
       
   492       ///Increments a bounding to contain another bounding box
       
   493       BoundingBox& add(const BoundingBox &u){
       
   494         if ( !u.empty() ){
       
   495           this->add(u.bottomLeft());
       
   496 	  this->add(u.topRight());
       
   497         }
       
   498         return *this;
       
   499       }
       
   500   
       
   501       ///Intersection of two bounding boxes
       
   502       BoundingBox operator &(const BoundingBox& u){
       
   503         BoundingBox b;
       
   504 	b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
       
   505 	b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
       
   506 	b.top_right.x=std::min(this->top_right.x,u.top_right.x);
       
   507 	b.top_right.y=std::min(this->top_right.y,u.top_right.y);
       
   508 	b._empty = this->_empty || u._empty ||
       
   509 	  b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
       
   510         return b;
       
   511       }
       
   512 
       
   513     };//class Boundingbox
       
   514 
       
   515 
       
   516   ///Map of x-coordinates of a dim2::Point<>-map
       
   517 
       
   518   ///\ingroup maps
       
   519   ///Map of x-coordinates of a dim2::Point<>-map
       
   520   ///
       
   521   template<class M>
       
   522   class XMap 
       
   523   {
       
   524     M& _map;
       
   525   public:
       
   526 
       
   527     typedef typename M::Value::Value Value;
       
   528     typedef typename M::Key Key;
       
   529     ///\e
       
   530     XMap(M& map) : _map(map) {}
       
   531     Value operator[](Key k) const {return _map[k].x;}
       
   532     void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
       
   533   };
       
   534     
       
   535   ///Returns an \ref XMap class
       
   536 
       
   537   ///This function just returns an \ref XMap class.
       
   538   ///
       
   539   ///\ingroup maps
       
   540   ///\relates XMap
       
   541   template<class M> 
       
   542   inline XMap<M> xMap(M &m) 
       
   543   {
       
   544     return XMap<M>(m);
       
   545   }
       
   546 
       
   547   template<class M> 
       
   548   inline XMap<M> xMap(const M &m) 
       
   549   {
       
   550     return XMap<M>(m);
       
   551   }
       
   552 
       
   553   ///Constant (read only) version of \ref XMap
       
   554 
       
   555   ///\ingroup maps
       
   556   ///Constant (read only) version of \ref XMap
       
   557   ///
       
   558   template<class M>
       
   559   class ConstXMap 
       
   560   {
       
   561     const M& _map;
       
   562   public:
       
   563 
       
   564     typedef typename M::Value::Value Value;
       
   565     typedef typename M::Key Key;
       
   566     ///\e
       
   567     ConstXMap(const M &map) : _map(map) {}
       
   568     Value operator[](Key k) const {return _map[k].x;}
       
   569   };
       
   570     
       
   571   ///Returns a \ref ConstXMap class
       
   572 
       
   573   ///This function just returns an \ref ConstXMap class.
       
   574   ///
       
   575   ///\ingroup maps
       
   576   ///\relates ConstXMap
       
   577   template<class M> 
       
   578   inline ConstXMap<M> xMap(const M &m) 
       
   579   {
       
   580     return ConstXMap<M>(m);
       
   581   }
       
   582 
       
   583   ///Map of y-coordinates of a dim2::Point<>-map
       
   584     
       
   585   ///\ingroup maps
       
   586   ///Map of y-coordinates of a dim2::Point<>-map
       
   587   ///
       
   588   template<class M>
       
   589   class YMap 
       
   590   {
       
   591     M& _map;
       
   592   public:
       
   593 
       
   594     typedef typename M::Value::Value Value;
       
   595     typedef typename M::Key Key;
       
   596     ///\e
       
   597     YMap(M& map) : _map(map) {}
       
   598     Value operator[](Key k) const {return _map[k].y;}
       
   599     void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
       
   600   };
       
   601 
       
   602   ///Returns an \ref YMap class
       
   603 
       
   604   ///This function just returns an \ref YMap class.
       
   605   ///
       
   606   ///\ingroup maps
       
   607   ///\relates YMap
       
   608   template<class M> 
       
   609   inline YMap<M> yMap(M &m) 
       
   610   {
       
   611     return YMap<M>(m);
       
   612   }
       
   613 
       
   614   template<class M> 
       
   615   inline YMap<M> yMap(const M &m) 
       
   616   {
       
   617     return YMap<M>(m);
       
   618   }
       
   619 
       
   620   ///Constant (read only) version of \ref YMap
       
   621 
       
   622   ///\ingroup maps
       
   623   ///Constant (read only) version of \ref YMap
       
   624   ///
       
   625   template<class M>
       
   626   class ConstYMap 
       
   627   {
       
   628     const M& _map;
       
   629   public:
       
   630 
       
   631     typedef typename M::Value::Value Value;
       
   632     typedef typename M::Key Key;
       
   633     ///\e
       
   634     ConstYMap(const M &map) : _map(map) {}
       
   635     Value operator[](Key k) const {return _map[k].y;}
       
   636   };
       
   637     
       
   638   ///Returns a \ref ConstYMap class
       
   639 
       
   640   ///This function just returns an \ref ConstYMap class.
       
   641   ///
       
   642   ///\ingroup maps
       
   643   ///\relates ConstYMap
       
   644   template<class M> 
       
   645   inline ConstYMap<M> yMap(const M &m) 
       
   646   {
       
   647     return ConstYMap<M>(m);
       
   648   }
       
   649 
       
   650 
       
   651     ///\brief Map of the \ref Point::normSquare() "normSquare()"
       
   652     ///of an \ref Point "Point"-map
       
   653     ///
       
   654     ///Map of the \ref Point::normSquare() "normSquare()"
       
   655     ///of an \ref Point "Point"-map
       
   656     ///\ingroup maps
       
   657     ///
       
   658   template<class M>
       
   659   class NormSquareMap 
       
   660   {
       
   661     const M& _map;
       
   662   public:
       
   663 
       
   664     typedef typename M::Value::Value Value;
       
   665     typedef typename M::Key Key;
       
   666     ///\e
       
   667     NormSquareMap(const M &map) : _map(map) {}
       
   668     Value operator[](Key k) const {return _map[k].normSquare();}
       
   669   };
       
   670     
       
   671   ///Returns a \ref NormSquareMap class
       
   672 
       
   673   ///This function just returns an \ref NormSquareMap class.
       
   674   ///
       
   675   ///\ingroup maps
       
   676   ///\relates NormSquareMap
       
   677   template<class M> 
       
   678   inline NormSquareMap<M> normSquareMap(const M &m) 
       
   679   {
       
   680     return NormSquareMap<M>(m);
       
   681   }
       
   682 
       
   683   /// @}
       
   684 
       
   685   } //namespce dim2
       
   686   
       
   687 } //namespace lemon
       
   688 
       
   689 #endif //LEMON_DIM2_H