lemon/dim2.h
changeset 65 bfbc57a51fbb
parent 8 a1b1d672f37a
child 39 0a01d811071f
equal deleted inserted replaced
0:825b3e2afbd8 1:5908d2eaa672
    32 ///
    32 ///
    33 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    33 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    34 /// can be used to determine
    34 /// can be used to determine
    35 /// the rectangular bounding box of a set of
    35 /// the rectangular bounding box of a set of
    36 /// \ref lemon::dim2::Point "dim2::Point"'s.
    36 /// \ref lemon::dim2::Point "dim2::Point"'s.
    37 ///
       
    38 ///\author Attila Bernath
       
    39 
       
    40 
    37 
    41 namespace lemon {
    38 namespace lemon {
    42 
    39 
    43   ///Tools for handling two dimensional coordinates
    40   ///Tools for handling two dimensional coordinates
    44 
    41 
    60 
    57 
    61     public:
    58     public:
    62 
    59 
    63       typedef T Value;
    60       typedef T Value;
    64 
    61 
    65       ///First co-ordinate
    62       ///First coordinate
    66       T x;
    63       T x;
    67       ///Second co-ordinate
    64       ///Second coordinate
    68       T y;     
    65       T y;     
    69       
    66       
    70       ///Default constructor
    67       ///Default constructor
    71       Point() {}
    68       Point() {}
    72 
    69 
    73       ///Construct an instance from coordinates
    70       ///Construct an instance from coordinates
    74       Point(T a, T b) : x(a), y(b) { }
    71       Point(T a, T b) : x(a), y(b) { }
    75 
    72 
    76       ///The dimension of the vector.
    73       ///The dimension of the vector.
    77 
    74 
    78       ///This class give back always 2.
    75       ///The dimension of the vector.
    79       ///
    76       ///This function always returns 2. 
    80       int size() const { return 2; }
    77       int size() const { return 2; }
    81 
    78 
    82       ///Subscripting operator
    79       ///Subscripting operator
    83 
    80 
    84       ///\c p[0] is \c p.x and \c p[1] is \c p.y
    81       ///\c p[0] is \c p.x and \c p[1] is \c p.y
   136       Point<T> operator+(const Point<T> &u) const {
   133       Point<T> operator+(const Point<T> &u) const {
   137         Point<T> b=*this;
   134         Point<T> b=*this;
   138         return b+=u;
   135         return b+=u;
   139       }
   136       }
   140 
   137 
   141       ///Return the neg of the vectors
   138       ///Return the negative of the vector
   142       Point<T> operator-() const {
   139       Point<T> operator-() const {
   143         Point<T> b=*this;
   140         Point<T> b=*this;
   144         b.x=-b.x; b.y=-b.y;
   141         b.x=-b.x; b.y=-b.y;
   145         return b;
   142         return b;
   146       }
   143       }
   173         return  (x!=u.x) || (y!=u.y);
   170         return  (x!=u.x) || (y!=u.y);
   174       }
   171       }
   175 
   172 
   176     };
   173     };
   177 
   174 
   178   ///Return an Point 
   175   ///Return a Point 
   179 
   176 
   180   ///Return an Point
   177   ///Return a Point.
   181   ///\relates Point
   178   ///\relates Point
   182   template <typename T>
   179   template <typename T>
   183   inline Point<T> makePoint(const T& x, const T& y) {
   180   inline Point<T> makePoint(const T& x, const T& y) {
   184     return Point<T>(x, y);
   181     return Point<T>(x, y);
   185   }
   182   }
   186 
   183 
   187   ///Return a vector multiplied by a scalar
   184   ///Return a vector multiplied by a scalar
   188 
   185 
   189   ///Return a vector multiplied by a scalar
   186   ///Return a vector multiplied by a scalar.
   190   ///\relates Point
   187   ///\relates Point
   191   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
   188   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
   192     return x*u;
   189     return x*u;
   193   }
   190   }
   194 
   191 
   195   ///Read a plainvector from a stream
   192   ///Read a plainvector from a stream
   196 
   193 
   197   ///Read a plainvector from a stream
   194   ///Read a plainvector from a stream.
   198   ///\relates Point
   195   ///\relates Point
   199   ///
   196   ///
   200   template<typename T>
   197   template<typename T>
   201   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
   198   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
   202     char c;
   199     char c;
   220     return is;
   217     return is;
   221   }
   218   }
   222 
   219 
   223   ///Write a plainvector to a stream
   220   ///Write a plainvector to a stream
   224 
   221 
   225   ///Write a plainvector to a stream
   222   ///Write a plainvector to a stream.
   226   ///\relates Point
   223   ///\relates Point
   227   ///
   224   ///
   228   template<typename T>
   225   template<typename T>
   229   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
   226   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
   230   {
   227   {
   232     return os;
   229     return os;
   233   }
   230   }
   234 
   231 
   235   ///Rotate by 90 degrees
   232   ///Rotate by 90 degrees
   236 
   233 
   237   ///Returns its parameter rotated by 90 degrees in positive direction.
   234   ///Returns the parameter rotated by 90 degrees in positive direction.
   238   ///\relates Point
   235   ///\relates Point
   239   ///
   236   ///
   240   template<typename T>
   237   template<typename T>
   241   inline Point<T> rot90(const Point<T> &z)
   238   inline Point<T> rot90(const Point<T> &z)
   242   {
   239   {
   243     return Point<T>(-z.y,z.x);
   240     return Point<T>(-z.y,z.x);
   244   }
   241   }
   245 
   242 
   246   ///Rotate by 180 degrees
   243   ///Rotate by 180 degrees
   247 
   244 
   248   ///Returns its parameter rotated by 180 degrees.
   245   ///Returns the parameter rotated by 180 degrees.
   249   ///\relates Point
   246   ///\relates Point
   250   ///
   247   ///
   251   template<typename T>
   248   template<typename T>
   252   inline Point<T> rot180(const Point<T> &z)
   249   inline Point<T> rot180(const Point<T> &z)
   253   {
   250   {
   254     return Point<T>(-z.x,-z.y);
   251     return Point<T>(-z.x,-z.y);
   255   }
   252   }
   256 
   253 
   257   ///Rotate by 270 degrees
   254   ///Rotate by 270 degrees
   258 
   255 
   259   ///Returns its parameter rotated by 90 degrees in negative direction.
   256   ///Returns the parameter rotated by 90 degrees in negative direction.
   260   ///\relates Point
   257   ///\relates Point
   261   ///
   258   ///
   262   template<typename T>
   259   template<typename T>
   263   inline Point<T> rot270(const Point<T> &z)
   260   inline Point<T> rot270(const Point<T> &z)
   264   {
   261   {
   269 
   266 
   270   /// A class to calculate or store the bounding box of plainvectors.
   267   /// A class to calculate or store the bounding box of plainvectors.
   271 
   268 
   272   /// A class to calculate or store the bounding box of plainvectors.
   269   /// A class to calculate or store the bounding box of plainvectors.
   273   ///
   270   ///
   274   ///\author Attila Bernath
       
   275     template<typename T>
   271     template<typename T>
   276     class BoundingBox {
   272     class BoundingBox {
   277       Point<T> bottom_left, top_right;
   273       Point<T> bottom_left, top_right;
   278       bool _empty;
   274       bool _empty;
   279     public:
   275     public:
   284       ///Construct an instance from one point
   280       ///Construct an instance from one point
   285       BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
   281       BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
   286       
   282       
   287       ///Construct an instance from two points
   283       ///Construct an instance from two points
   288       
   284       
   289       ///Construct an instance from two points
   285       ///Construct an instance from two points.
   290       ///\warning The coordinates of the bottom-left corner must be no more
   286       ///\param a The bottom left corner.
   291       ///than those of the top-right one
   287       ///\param b The top right corner.
       
   288       ///\warning The coordinates of the bottom left corner must be no more
       
   289       ///than those of the top right one.
   292       BoundingBox(Point<T> a,Point<T> b)
   290       BoundingBox(Point<T> a,Point<T> b)
   293       {
   291       {
   294 	bottom_left=a;
   292 	bottom_left=a;
   295 	top_right=b;
   293 	top_right=b;
   296 	_empty = false;
   294 	_empty = false;
   297       }
   295       }
   298       
   296       
   299       ///Construct an instance from four numbers
   297       ///Construct an instance from four numbers
   300 
   298 
   301       ///Construct an instance from four numbers
   299       ///Construct an instance from four numbers.
   302       ///\warning The coordinates of the bottom-left corner must be no more
   300       ///\param l The left side of the box.
   303       ///than those of the top-right one
   301       ///\param b The bottom of the box.
       
   302       ///\param r The right side of the box.
       
   303       ///\param t The top of the box.
       
   304       ///\warning The left side must be no more than the right side and
       
   305       ///bottom must be no more than the top. 
   304       BoundingBox(T l,T b,T r,T t)
   306       BoundingBox(T l,T b,T r,T t)
   305       {
   307       {
   306 	bottom_left=Point<T>(l,b);
   308 	bottom_left=Point<T>(l,b);
   307 	top_right=Point<T>(r,t);
   309 	top_right=Point<T>(r,t);
   308 	_empty = false;
   310 	_empty = false;
   309       }
   311       }
   310       
   312       
   311       ///Were any points added?
   313       ///Return \c true if the bounding box is empty.
       
   314       
       
   315       ///Return \c true if the bounding box is empty (i.e. return \c false
       
   316       ///if at least one point was added to the box or the coordinates of
       
   317       ///the box were set).
       
   318       ///The coordinates of an empty bounding box are not defined. 
   312       bool empty() const {
   319       bool empty() const {
   313         return _empty;
   320         return _empty;
   314       }
   321       }
   315       
   322       
   316       ///Make the BoundingBox empty
   323       ///Make the BoundingBox empty
   327       }
   334       }
   328 
   335 
   329       ///Set the bottom left corner
   336       ///Set the bottom left corner
   330 
   337 
   331       ///Set the bottom left corner.
   338       ///Set the bottom left corner.
   332       ///It should only bee used for non-empty box.
   339       ///It should only be used for non-empty box.
   333       void bottomLeft(Point<T> p) {
   340       void bottomLeft(Point<T> p) {
   334 	bottom_left = p;
   341 	bottom_left = p;
   335       }
   342       }
   336 
   343 
   337       ///Give back the top right corner
   344       ///Give back the top right corner
   343       }
   350       }
   344 
   351 
   345       ///Set the top right corner
   352       ///Set the top right corner
   346 
   353 
   347       ///Set the top right corner.
   354       ///Set the top right corner.
   348       ///It should only bee used for non-empty box.
   355       ///It should only be used for non-empty box.
   349       void topRight(Point<T> p) {
   356       void topRight(Point<T> p) {
   350 	top_right = p;
   357 	top_right = p;
   351       }
   358       }
   352 
   359 
   353       ///Give back the bottom right corner
   360       ///Give back the bottom right corner
   359       }
   366       }
   360 
   367 
   361       ///Set the bottom right corner
   368       ///Set the bottom right corner
   362 
   369 
   363       ///Set the bottom right corner.
   370       ///Set the bottom right corner.
   364       ///It should only bee used for non-empty box.
   371       ///It should only be used for non-empty box.
   365       void bottomRight(Point<T> p) {
   372       void bottomRight(Point<T> p) {
   366 	top_right.x = p.x;
   373 	top_right.x = p.x;
   367 	bottom_left.y = p.y;
   374 	bottom_left.y = p.y;
   368       }
   375       }
   369  
   376  
   376       }
   383       }
   377 
   384 
   378       ///Set the top left corner
   385       ///Set the top left corner
   379 
   386 
   380       ///Set the top left corner.
   387       ///Set the top left corner.
   381       ///It should only bee used for non-empty box.
   388       ///It should only be used for non-empty box.
   382       void topLeft(Point<T> p) {
   389       void topLeft(Point<T> p) {
   383 	top_right.y = p.y;
   390 	top_right.y = p.y;
   384 	bottom_left.x = p.x;
   391 	bottom_left.x = p.x;
   385       }
   392       }
   386 
   393 
   393       }
   400       }
   394 
   401 
   395       ///Set the bottom of the box
   402       ///Set the bottom of the box
   396 
   403 
   397       ///Set the bottom of the box.
   404       ///Set the bottom of the box.
   398       ///It should only bee used for non-empty box.
   405       ///It should only be used for non-empty box.
   399       void bottom(T t) {
   406       void bottom(T t) {
   400 	bottom_left.y = t;
   407 	bottom_left.y = t;
   401       }
   408       }
   402 
   409 
   403       ///Give back the top of the box
   410       ///Give back the top of the box
   409       }
   416       }
   410 
   417 
   411       ///Set the top of the box
   418       ///Set the top of the box
   412 
   419 
   413       ///Set the top of the box.
   420       ///Set the top of the box.
   414       ///It should only bee used for non-empty box.
   421       ///It should only be used for non-empty box.
   415       void top(T t) {
   422       void top(T t) {
   416 	top_right.y = t;
   423 	top_right.y = t;
   417       }
   424       }
   418 
   425 
   419       ///Give back the left side of the box
   426       ///Give back the left side of the box
   425       }
   432       }
   426  
   433  
   427       ///Set the left side of the box
   434       ///Set the left side of the box
   428 
   435 
   429       ///Set the left side of the box.
   436       ///Set the left side of the box.
   430       ///It should only bee used for non-empty box
   437       ///It should only be used for non-empty box.
   431       void left(T t) {
   438       void left(T t) {
   432 	bottom_left.x = t;
   439 	bottom_left.x = t;
   433       }
   440       }
   434 
   441 
   435       /// Give back the right side of the box
   442       /// Give back the right side of the box
   441       }
   448       }
   442 
   449 
   443       ///Set the right side of the box
   450       ///Set the right side of the box
   444 
   451 
   445       ///Set the right side of the box.
   452       ///Set the right side of the box.
   446       ///It should only bee used for non-empty box
   453       ///It should only be used for non-empty box.
   447       void right(T t) {
   454       void right(T t) {
   448 	top_right.x = t;
   455 	top_right.x = t;
   449       }
   456       }
   450 
   457 
   451       ///Give back the height of the box
   458       ///Give back the height of the box
   463       T width() const {
   470       T width() const {
   464         return top_right.x-bottom_left.x;
   471         return top_right.x-bottom_left.x;
   465       }
   472       }
   466 
   473 
   467       ///Checks whether a point is inside a bounding box
   474       ///Checks whether a point is inside a bounding box
   468       bool inside(const Point<T>& u){
   475       bool inside(const Point<T>& u) const {
   469         if (_empty)
   476         if (_empty)
   470           return false;
   477           return false;
   471         else{
   478         else{
   472           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 &&
   473               (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
   480               (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
   474         }
   481         }
   475       }
   482       }
   476   
   483   
   477       ///Increments a bounding box with a point
   484       ///Increments a bounding box with a point
       
   485 
       
   486       ///Increments a bounding box with a point.
       
   487       ///
   478       BoundingBox& add(const Point<T>& u){
   488       BoundingBox& add(const Point<T>& u){
   479         if (_empty){
   489         if (_empty){
   480           bottom_left=top_right=u;
   490           bottom_left=top_right=u;
   481           _empty = false;
   491           _empty = false;
   482         }
   492         }
   487           if (top_right.y < u.y) top_right.y = u.y;
   497           if (top_right.y < u.y) top_right.y = u.y;
   488         }
   498         }
   489         return *this;
   499         return *this;
   490       }
   500       }
   491     
   501     
   492       ///Increments a bounding to contain another bounding box
   502       ///Increments a bounding box to contain another bounding box
       
   503       
       
   504       ///Increments a bounding box to contain another bounding box.
       
   505       ///
   493       BoundingBox& add(const BoundingBox &u){
   506       BoundingBox& add(const BoundingBox &u){
   494         if ( !u.empty() ){
   507         if ( !u.empty() ){
   495           this->add(u.bottomLeft());
   508           this->add(u.bottomLeft());
   496 	  this->add(u.topRight());
   509 	  this->add(u.topRight());
   497         }
   510         }
   498         return *this;
   511         return *this;
   499       }
   512       }
   500   
   513   
   501       ///Intersection of two bounding boxes
   514       ///Intersection of two bounding boxes
   502       BoundingBox operator &(const BoundingBox& u){
   515 
       
   516       ///Intersection of two bounding boxes.
       
   517       ///
       
   518       BoundingBox operator&(const BoundingBox& u) const {
   503         BoundingBox b;
   519         BoundingBox b;
   504 	b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
   520         if (this->_empty || u._empty) {
   505 	b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
   521 	  b._empty = true;
   506 	b.top_right.x=std::min(this->top_right.x,u.top_right.x);
   522 	} else {
   507 	b.top_right.y=std::min(this->top_right.y,u.top_right.y);
   523 	  b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
   508 	b._empty = this->_empty || u._empty ||
   524 	  b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
   509 	  b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
   525 	  b.top_right.x = std::min(this->top_right.x,u.top_right.x);
       
   526 	  b.top_right.y = std::min(this->top_right.y,u.top_right.y);
       
   527 	  b._empty = b.bottom_left.x > b.top_right.x ||
       
   528 	             b.bottom_left.y > b.top_right.y;
       
   529 	} 
   510         return b;
   530         return b;
   511       }
   531       }
   512 
   532 
   513     };//class Boundingbox
   533     };//class Boundingbox
   514 
   534 
   515 
   535 
   516   ///Map of x-coordinates of a dim2::Point<>-map
   536   ///Map of x-coordinates of a \ref Point "Point"-map
   517 
   537 
   518   ///\ingroup maps
   538   ///\ingroup maps
   519   ///Map of x-coordinates of a dim2::Point<>-map
   539   ///Map of x-coordinates of a \ref Point "Point"-map.
   520   ///
   540   ///
   521   template<class M>
   541   template<class M>
   522   class XMap 
   542   class XMap 
   523   {
   543   {
   524     M& _map;
   544     M& _map;
   568     Value operator[](Key k) const {return _map[k].x;}
   588     Value operator[](Key k) const {return _map[k].x;}
   569   };
   589   };
   570     
   590     
   571   ///Returns a \ref ConstXMap class
   591   ///Returns a \ref ConstXMap class
   572 
   592 
   573   ///This function just returns an \ref ConstXMap class.
   593   ///This function just returns a \ref ConstXMap class.
   574   ///
   594   ///
   575   ///\ingroup maps
   595   ///\ingroup maps
   576   ///\relates ConstXMap
   596   ///\relates ConstXMap
   577   template<class M> 
   597   template<class M> 
   578   inline ConstXMap<M> xMap(const M &m) 
   598   inline ConstXMap<M> xMap(const M &m) 
   579   {
   599   {
   580     return ConstXMap<M>(m);
   600     return ConstXMap<M>(m);
   581   }
   601   }
   582 
   602 
   583   ///Map of y-coordinates of a dim2::Point<>-map
   603   ///Map of y-coordinates of a \ref Point "Point"-map
   584     
   604     
   585   ///\ingroup maps
   605   ///\ingroup maps
   586   ///Map of y-coordinates of a dim2::Point<>-map
   606   ///Map of y-coordinates of a \ref Point "Point"-map.
   587   ///
   607   ///
   588   template<class M>
   608   template<class M>
   589   class YMap 
   609   class YMap 
   590   {
   610   {
   591     M& _map;
   611     M& _map;
   597     YMap(M& map) : _map(map) {}
   617     YMap(M& map) : _map(map) {}
   598     Value operator[](Key k) const {return _map[k].y;}
   618     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));}
   619     void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
   600   };
   620   };
   601 
   621 
   602   ///Returns an \ref YMap class
   622   ///Returns a \ref YMap class
   603 
   623 
   604   ///This function just returns an \ref YMap class.
   624   ///This function just returns a \ref YMap class.
   605   ///
   625   ///
   606   ///\ingroup maps
   626   ///\ingroup maps
   607   ///\relates YMap
   627   ///\relates YMap
   608   template<class M> 
   628   template<class M> 
   609   inline YMap<M> yMap(M &m) 
   629   inline YMap<M> yMap(M &m) 
   635     Value operator[](Key k) const {return _map[k].y;}
   655     Value operator[](Key k) const {return _map[k].y;}
   636   };
   656   };
   637     
   657     
   638   ///Returns a \ref ConstYMap class
   658   ///Returns a \ref ConstYMap class
   639 
   659 
   640   ///This function just returns an \ref ConstYMap class.
   660   ///This function just returns a \ref ConstYMap class.
   641   ///
   661   ///
   642   ///\ingroup maps
   662   ///\ingroup maps
   643   ///\relates ConstYMap
   663   ///\relates ConstYMap
   644   template<class M> 
   664   template<class M> 
   645   inline ConstYMap<M> yMap(const M &m) 
   665   inline ConstYMap<M> yMap(const M &m) 
   647     return ConstYMap<M>(m);
   667     return ConstYMap<M>(m);
   648   }
   668   }
   649 
   669 
   650 
   670 
   651     ///\brief Map of the \ref Point::normSquare() "normSquare()"
   671     ///\brief Map of the \ref Point::normSquare() "normSquare()"
   652     ///of an \ref Point "Point"-map
   672     ///of a \ref Point "Point"-map
   653     ///
   673     ///
   654     ///Map of the \ref Point::normSquare() "normSquare()"
   674     ///Map of the \ref Point::normSquare() "normSquare()"
   655     ///of an \ref Point "Point"-map
   675     ///of a \ref Point "Point"-map.
   656     ///\ingroup maps
   676     ///\ingroup maps
   657     ///
   677     ///
   658   template<class M>
   678   template<class M>
   659   class NormSquareMap 
   679   class NormSquareMap 
   660   {
   680   {
   668     Value operator[](Key k) const {return _map[k].normSquare();}
   688     Value operator[](Key k) const {return _map[k].normSquare();}
   669   };
   689   };
   670     
   690     
   671   ///Returns a \ref NormSquareMap class
   691   ///Returns a \ref NormSquareMap class
   672 
   692 
   673   ///This function just returns an \ref NormSquareMap class.
   693   ///This function just returns a \ref NormSquareMap class.
   674   ///
   694   ///
   675   ///\ingroup maps
   695   ///\ingroup maps
   676   ///\relates NormSquareMap
   696   ///\relates NormSquareMap
   677   template<class M> 
   697   template<class M> 
   678   inline NormSquareMap<M> normSquareMap(const M &m) 
   698   inline NormSquareMap<M> normSquareMap(const M &m)