alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2391: * Copyright (C) 2003-2007 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@2207: #ifndef LEMON_DIM2_H alpar@2207: #define LEMON_DIM2_H athos@201: athos@201: #include deba@1993: #include athos@201: klao@491: ///\ingroup misc alpar@249: ///\file alpar@249: ///\brief A simple two dimensional vector and a bounding box implementation alpar@249: /// alpar@2207: /// The class \ref lemon::dim2::Point "dim2::Point" implements alpar@249: ///a two dimensional vector with the usual alpar@249: /// operations. alpar@249: /// alpar@2207: /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" alpar@2207: /// can be used to determine alpar@2207: /// the rectangular bounding box of a set of alpar@2207: /// \ref lemon::dim2::Point "dim2::Point"'s. alpar@458: /// alpar@458: ///\author Attila Bernath alpar@249: alpar@249: alpar@921: namespace lemon { alpar@431: alpar@2207: ///Tools for handling two dimensional coordinates alpar@2207: alpar@2207: ///This namespace is a storage of several alpar@2207: ///tools for handling two dimensional coordinates alpar@2207: namespace dim2 { alpar@2207: alpar@431: /// \addtogroup misc alpar@431: /// @{ alpar@431: alpar@1257: /// A simple two dimensional vector (plainvector) implementation alpar@242: alpar@1257: /// A simple two dimensional vector (plainvector) implementation alpar@458: ///with the usual vector alpar@458: /// operators. alpar@458: /// athos@207: template alpar@2207: class Point { athos@201: athos@207: public: athos@240: alpar@987: typedef T Value; alpar@964: alpar@1974: ///First co-ordinate alpar@1974: T x; alpar@1974: ///Second co-ordinate alpar@1974: T y; athos@207: alpar@1257: ///Default constructor alpar@2207: Point() {} athos@201: alpar@2157: ///Construct an instance from coordinates alpar@2207: Point(T a, T b) : x(a), y(b) { } athos@201: deba@2217: ///The dimension of the vector. deba@2217: deba@2217: ///This class give back always 2. deba@2217: /// deba@2212: int size() const { return 2; } deba@2212: deba@2212: ///Subscripting operator deba@2217: deba@2217: ///\c p[0] is \c p.x and \c p[1] is \c p.y deba@2217: /// deba@2212: T& operator[](int idx) { return idx == 0 ? x : y; } deba@2212: deba@2212: ///Const subscripting operator deba@2217: deba@2217: ///\c p[0] is \c p.x and \c p[1] is \c p.y deba@2217: /// deba@2212: const T& operator[](int idx) const { return idx == 0 ? x : y; } athos@201: alpar@1049: ///Conversion constructor alpar@2207: template Point(const Point &p) : x(p.x), y(p.y) {} alpar@1049: alpar@2157: ///Give back the square of the norm of the vector alpar@1257: T normSquare() const { ladanyi@1426: return x*x+y*y; alpar@1391: } athos@201: alpar@2157: ///Increment the left hand side by u alpar@2207: Point& operator +=(const Point& u) { ladanyi@1426: x += u.x; ladanyi@1426: y += u.y; ladanyi@1426: return *this; alpar@1391: } athos@201: alpar@2157: ///Decrement the left hand side by u alpar@2207: Point& operator -=(const Point& u) { ladanyi@1426: x -= u.x; ladanyi@1426: y -= u.y; ladanyi@1426: return *this; alpar@1391: } athos@201: alpar@2157: ///Multiply the left hand side with a scalar alpar@2207: Point& operator *=(const T &u) { ladanyi@1426: x *= u; ladanyi@1426: y *= u; ladanyi@1426: return *this; alpar@1391: } athos@207: alpar@2157: ///Divide the left hand side by a scalar alpar@2207: Point& operator /=(const T &u) { ladanyi@1426: x /= u; ladanyi@1426: y /= u; ladanyi@1426: return *this; alpar@1391: } athos@201: alpar@2157: ///Return the scalar product of two vectors alpar@2207: T operator *(const Point& u) const { ladanyi@1426: return x*u.x+y*u.y; alpar@1391: } athos@201: alpar@2157: ///Return the sum of two vectors alpar@2207: Point operator+(const Point &u) const { alpar@2207: Point b=*this; ladanyi@1426: return b+=u; alpar@1391: } athos@201: alpar@2157: ///Return the neg of the vectors alpar@2207: Point operator-() const { alpar@2207: Point b=*this; ladanyi@1426: b.x=-b.x; b.y=-b.y; ladanyi@1426: return b; alpar@1391: } alpar@1049: alpar@2157: ///Return the difference of two vectors alpar@2207: Point operator-(const Point &u) const { alpar@2207: Point b=*this; ladanyi@1426: return b-=u; alpar@1391: } athos@201: alpar@2157: ///Return a vector multiplied by a scalar alpar@2207: Point operator*(const T &u) const { alpar@2207: Point b=*this; ladanyi@1426: return b*=u; alpar@1391: } athos@201: alpar@2157: ///Return a vector divided by a scalar alpar@2207: Point operator/(const T &u) const { alpar@2207: Point b=*this; ladanyi@1426: return b/=u; alpar@1391: } athos@201: alpar@2157: ///Test equality alpar@2207: bool operator==(const Point &u) const { ladanyi@1426: return (x==u.x) && (y==u.y); alpar@1391: } athos@201: alpar@2157: ///Test inequality alpar@2207: bool operator!=(Point u) const { ladanyi@1426: return (x!=u.x) || (y!=u.y); alpar@1391: } athos@201: athos@207: }; athos@201: alpar@2207: ///Return an Point deba@1999: alpar@2207: ///Return an Point alpar@2207: ///\relates Point deba@1999: template deba@2212: inline Point makePoint(const T& x, const T& y) { alpar@2207: return Point(x, y); deba@1999: } deba@1999: alpar@2157: ///Return a vector multiplied by a scalar alpar@1083: alpar@2157: ///Return a vector multiplied by a scalar alpar@2207: ///\relates Point alpar@2207: template Point operator*(const T &u,const Point &x) { alpar@1071: return x*u; alpar@1391: } alpar@1071: alpar@814: ///Read a plainvector from a stream alpar@814: alpar@967: ///Read a plainvector from a stream alpar@2207: ///\relates Point alpar@814: /// athos@207: template alpar@2207: inline std::istream& operator>>(std::istream &is, Point &z) { deba@1392: char c; deba@1392: if (is >> c) { deba@1392: if (c != '(') is.putback(c); deba@1392: } else { deba@1392: is.clear(); deba@1392: } deba@1392: if (!(is >> z.x)) return is; deba@1392: if (is >> c) { deba@1392: if (c != ',') is.putback(c); deba@1392: } else { deba@1392: is.clear(); deba@1392: } deba@1392: if (!(is >> z.y)) return is; deba@1392: if (is >> c) { deba@1392: if (c != ')') is.putback(c); deba@1392: } else { deba@1392: is.clear(); deba@1392: } athos@207: return is; athos@207: } athos@201: alpar@814: ///Write a plainvector to a stream alpar@814: alpar@967: ///Write a plainvector to a stream alpar@2207: ///\relates Point alpar@814: /// athos@207: template alpar@2207: inline std::ostream& operator<<(std::ostream &os, const Point& z) athos@207: { athos@240: os << "(" << z.x << ", " << z.y << ")"; athos@207: return os; athos@207: } athos@207: alpar@1202: ///Rotate by 90 degrees alpar@1202: alpar@1202: ///Returns its parameter rotated by 90 degrees in positive direction. alpar@2207: ///\relates Point alpar@1202: /// alpar@1202: template alpar@2207: inline Point rot90(const Point &z) alpar@1202: { alpar@2207: return Point(-z.y,z.x); alpar@1202: } alpar@1202: alpar@2157: ///Rotate by 180 degrees alpar@2157: alpar@2157: ///Returns its parameter rotated by 180 degrees. alpar@2207: ///\relates Point alpar@2157: /// alpar@2157: template alpar@2207: inline Point rot180(const Point &z) alpar@2157: { alpar@2207: return Point(-z.x,-z.y); alpar@2157: } alpar@2157: alpar@1202: ///Rotate by 270 degrees alpar@1202: alpar@1202: ///Returns its parameter rotated by 90 degrees in negative direction. alpar@2207: ///\relates Point alpar@1202: /// alpar@1202: template alpar@2207: inline Point rot270(const Point &z) alpar@1202: { alpar@2207: return Point(z.y,-z.x); alpar@1202: } alpar@1202: alpar@1202: athos@244: alpar@458: /// A class to calculate or store the bounding box of plainvectors. alpar@458: alpar@458: /// A class to calculate or store the bounding box of plainvectors. alpar@458: /// alpar@458: ///\author Attila Bernath athos@244: template athos@244: class BoundingBox { alpar@2207: Point bottom_left, top_right; athos@244: bool _empty; athos@244: public: athos@244: ladanyi@1426: ///Default constructor: creates an empty bounding box athos@244: BoundingBox() { _empty = true; } athos@244: alpar@2157: ///Construct an instance from one point alpar@2207: BoundingBox(Point a) { bottom_left=top_right=a; _empty = false; } athos@244: ladanyi@1426: ///Were any points added? athos@244: bool empty() const { ladanyi@1426: return _empty; athos@244: } athos@244: alpar@2157: ///Make the BoundingBox empty alpar@1391: void clear() { ladanyi@1426: _empty=1; alpar@1391: } alpar@1391: alpar@2157: ///Give back the bottom left corner alpar@2157: alpar@2157: ///Give back the bottom left corner. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@2207: Point bottomLeft() const { ladanyi@1426: return bottom_left; alpar@1391: } athos@244: alpar@2157: ///Set the bottom left corner alpar@2157: alpar@2157: ///Set the bottom left corner. alpar@2157: ///It should only bee used for non-empty box. alpar@2207: void bottomLeft(Point p) { alpar@1927: bottom_left = p; alpar@1927: } alpar@1927: alpar@2157: ///Give back the top right corner alpar@2157: alpar@2157: ///Give back the top right corner. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@2207: Point topRight() const { ladanyi@1426: return top_right; alpar@1391: } athos@244: alpar@2157: ///Set the top right corner alpar@2157: alpar@2157: ///Set the top right corner. alpar@2157: ///It should only bee used for non-empty box. alpar@2207: void topRight(Point p) { alpar@1927: top_right = p; alpar@1927: } alpar@1927: alpar@2157: ///Give back the bottom right corner alpar@2157: alpar@2157: ///Give back the bottom right corner. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@2207: Point bottomRight() const { alpar@2207: return Point(top_right.x,bottom_left.y); alpar@1391: } alpar@1045: alpar@2157: ///Set the bottom right corner alpar@2157: alpar@2157: ///Set the bottom right corner. alpar@2157: ///It should only bee used for non-empty box. alpar@2207: void bottomRight(Point p) { alpar@1927: top_right.x = p.x; alpar@1927: bottom_left.y = p.y; alpar@1927: } alpar@2157: alpar@2157: ///Give back the top left corner alpar@1927: alpar@2157: ///Give back the top left corner. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@2207: Point topLeft() const { alpar@2207: return Point(bottom_left.x,top_right.y); alpar@1391: } alpar@1045: alpar@2157: ///Set the top left corner alpar@2157: alpar@2157: ///Set the top left corner. alpar@2157: ///It should only bee used for non-empty box. alpar@2207: void topLeft(Point p) { alpar@1927: top_right.y = p.y; alpar@1927: bottom_left.x = p.x; alpar@1927: } alpar@1927: alpar@2157: ///Give back the bottom of the box alpar@2157: alpar@2157: ///Give back the bottom of the box. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@1045: T bottom() const { ladanyi@1426: return bottom_left.y; alpar@1391: } alpar@1045: alpar@2157: ///Set the bottom of the box alpar@2157: alpar@2157: ///Set the bottom of the box. alpar@2157: ///It should only bee used for non-empty box. alpar@1927: void bottom(T t) { alpar@1927: bottom_left.y = t; alpar@1927: } alpar@1927: alpar@2157: ///Give back the top of the box alpar@2157: alpar@2157: ///Give back the top of the box. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@1045: T top() const { ladanyi@1426: return top_right.y; alpar@1391: } alpar@1045: alpar@2157: ///Set the top of the box alpar@2157: alpar@2157: ///Set the top of the box. alpar@2157: ///It should only bee used for non-empty box. alpar@1927: void top(T t) { alpar@1927: top_right.y = t; alpar@1927: } alpar@1927: alpar@2157: ///Give back the left side of the box alpar@2157: alpar@2157: ///Give back the left side of the box. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@1045: T left() const { ladanyi@1426: return bottom_left.x; alpar@1391: } alpar@2157: alpar@2157: ///Set the left side of the box alpar@1045: alpar@2157: ///Set the left side of the box. alpar@2157: ///It should only bee used for non-empty box alpar@1927: void left(T t) { alpar@1927: bottom_left.x = t; alpar@1927: } alpar@1927: alpar@2157: /// Give back the right side of the box alpar@2157: alpar@2157: /// Give back the right side of the box. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@1045: T right() const { ladanyi@1426: return top_right.x; alpar@1391: } alpar@1045: alpar@2157: ///Set the right side of the box alpar@2157: alpar@2157: ///Set the right side of the box. alpar@2157: ///It should only bee used for non-empty box alpar@1927: void right(T t) { alpar@1927: top_right.x = t; alpar@1927: } alpar@1927: alpar@2157: ///Give back the height of the box alpar@2157: alpar@2157: ///Give back the height of the box. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@1102: T height() const { ladanyi@1426: return top_right.y-bottom_left.y; alpar@1391: } alpar@1102: alpar@2157: ///Give back the width of the box alpar@2157: alpar@2157: ///Give back the width of the box. alpar@2157: ///If the bounding box is empty, then the return value is not defined. alpar@1102: T width() const { ladanyi@1426: return top_right.x-bottom_left.x; alpar@1391: } alpar@1102: athos@244: ///Checks whether a point is inside a bounding box alpar@2207: bool inside(const Point& u){ ladanyi@1426: if (_empty) ladanyi@1426: return false; ladanyi@1426: else{ ladanyi@1426: return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && ladanyi@1426: (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); ladanyi@1426: } athos@244: } athos@244: athos@244: ///Increments a bounding box with a point alpar@2207: BoundingBox& add(const Point& u){ ladanyi@1426: if (_empty){ ladanyi@1426: bottom_left=top_right=u; ladanyi@1426: _empty = false; ladanyi@1426: } ladanyi@1426: else{ ladanyi@1426: if (bottom_left.x > u.x) bottom_left.x = u.x; ladanyi@1426: if (bottom_left.y > u.y) bottom_left.y = u.y; ladanyi@1426: if (top_right.x < u.x) top_right.x = u.x; ladanyi@1426: if (top_right.y < u.y) top_right.y = u.y; ladanyi@1426: } ladanyi@1426: return *this; alpar@1391: } alpar@2214: alpar@2214: ///Increments a bounding to contain another bounding box alpar@1588: BoundingBox& add(const BoundingBox &u){ ladanyi@1426: if ( !u.empty() ){ alpar@1588: this->add(u.bottomLeft()); alpar@1588: this->add(u.topRight()); ladanyi@1426: } ladanyi@1426: return *this; alpar@1391: } athos@244: alpar@1588: ///Intersection of two bounding boxes alpar@1588: BoundingBox operator &(const BoundingBox& u){ alpar@1588: BoundingBox b; alpar@1588: b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x); alpar@1588: b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y); alpar@1588: b.top_right.x=std::min(this->top_right.x,u.top_right.x); alpar@1588: b.top_right.y=std::min(this->top_right.y,u.top_right.y); alpar@1588: b._empty = this->_empty || u._empty || alpar@1588: b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y; alpar@1588: return b; alpar@1391: } athos@244: athos@244: };//class Boundingbox athos@244: athos@244: alpar@2207: ///Map of x-coordinates of a dim2::Point<>-map alpar@1317: alpar@1317: ///\ingroup maps alpar@2214: ///Map of x-coordinates of a dim2::Point<>-map alpar@1317: /// alpar@1317: template alpar@1317: class XMap alpar@1317: { deba@1706: M& _map; alpar@1317: public: deba@1420: alpar@1317: typedef typename M::Value::Value Value; alpar@1317: typedef typename M::Key Key; alpar@1317: ///\e deba@1706: XMap(M& map) : _map(map) {} alpar@1317: Value operator[](Key k) const {return _map[k].x;} alpar@1352: void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));} alpar@1317: }; alpar@1317: alpar@1317: ///Returns an \ref XMap class alpar@1317: alpar@1317: ///This function just returns an \ref XMap class. alpar@1317: /// alpar@1317: ///\ingroup maps alpar@1317: ///\relates XMap alpar@1317: template alpar@1317: inline XMap xMap(M &m) alpar@1317: { alpar@1317: return XMap(m); alpar@1317: } alpar@1317: deba@1420: template deba@1420: inline XMap xMap(const M &m) deba@1420: { deba@1420: return XMap(m); deba@1420: } deba@1420: alpar@1317: ///Constant (read only) version of \ref XMap alpar@1317: alpar@1317: ///\ingroup maps alpar@2214: ///Constant (read only) version of \ref XMap alpar@1317: /// alpar@1317: template alpar@1317: class ConstXMap alpar@1317: { deba@1706: const M& _map; alpar@1317: public: deba@1420: alpar@1317: typedef typename M::Value::Value Value; alpar@1317: typedef typename M::Key Key; alpar@1317: ///\e alpar@1317: ConstXMap(const M &map) : _map(map) {} alpar@1317: Value operator[](Key k) const {return _map[k].x;} alpar@1317: }; alpar@1317: alpar@1317: ///Returns a \ref ConstXMap class alpar@1317: alpar@1317: ///This function just returns an \ref ConstXMap class. alpar@1317: /// alpar@1317: ///\ingroup maps alpar@1317: ///\relates ConstXMap alpar@1317: template alpar@1317: inline ConstXMap xMap(const M &m) alpar@1317: { alpar@1317: return ConstXMap(m); alpar@1317: } alpar@1317: alpar@2207: ///Map of y-coordinates of a dim2::Point<>-map alpar@1317: alpar@1317: ///\ingroup maps alpar@2214: ///Map of y-coordinates of a dim2::Point<>-map alpar@1317: /// alpar@1317: template alpar@1317: class YMap alpar@1317: { deba@1706: M& _map; alpar@1317: public: deba@1420: alpar@1317: typedef typename M::Value::Value Value; alpar@1317: typedef typename M::Key Key; alpar@1317: ///\e deba@1706: YMap(M& map) : _map(map) {} alpar@1317: Value operator[](Key k) const {return _map[k].y;} alpar@1352: void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));} alpar@1317: }; alpar@1317: alpar@1317: ///Returns an \ref YMap class alpar@1317: alpar@1317: ///This function just returns an \ref YMap class. alpar@1317: /// alpar@1317: ///\ingroup maps alpar@1317: ///\relates YMap alpar@1317: template alpar@1317: inline YMap yMap(M &m) alpar@1317: { alpar@1317: return YMap(m); alpar@1317: } alpar@1317: deba@1420: template deba@1420: inline YMap yMap(const M &m) deba@1420: { deba@1420: return YMap(m); deba@1420: } deba@1420: alpar@1317: ///Constant (read only) version of \ref YMap alpar@1317: alpar@1317: ///\ingroup maps alpar@2214: ///Constant (read only) version of \ref YMap alpar@1317: /// alpar@1317: template alpar@1317: class ConstYMap alpar@1317: { deba@1706: const M& _map; alpar@1317: public: deba@1420: alpar@1317: typedef typename M::Value::Value Value; alpar@1317: typedef typename M::Key Key; alpar@1317: ///\e alpar@1317: ConstYMap(const M &map) : _map(map) {} alpar@1317: Value operator[](Key k) const {return _map[k].y;} alpar@1317: }; alpar@1317: alpar@1317: ///Returns a \ref ConstYMap class alpar@1317: alpar@1317: ///This function just returns an \ref ConstYMap class. alpar@1317: /// alpar@1317: ///\ingroup maps alpar@1317: ///\relates ConstYMap alpar@1317: template alpar@1317: inline ConstYMap yMap(const M &m) alpar@1317: { alpar@1317: return ConstYMap(m); alpar@1317: } alpar@1317: alpar@1317: alpar@2214: ///\brief Map of the \ref Point::normSquare() "normSquare()" alpar@2214: ///of an \ref Point "Point"-map alpar@2214: /// alpar@2214: ///Map of the \ref Point::normSquare() "normSquare()" alpar@2214: ///of an \ref Point "Point"-map alpar@2214: ///\ingroup maps alpar@2214: /// alpar@1352: template alpar@1352: class NormSquareMap alpar@1352: { deba@1706: const M& _map; alpar@1352: public: deba@1420: alpar@1352: typedef typename M::Value::Value Value; alpar@1352: typedef typename M::Key Key; alpar@1352: ///\e alpar@1352: NormSquareMap(const M &map) : _map(map) {} alpar@1352: Value operator[](Key k) const {return _map[k].normSquare();} alpar@1352: }; alpar@1352: alpar@1352: ///Returns a \ref NormSquareMap class alpar@1352: alpar@1352: ///This function just returns an \ref NormSquareMap class. alpar@1352: /// alpar@1352: ///\ingroup maps alpar@1352: ///\relates NormSquareMap alpar@1352: template alpar@1352: inline NormSquareMap normSquareMap(const M &m) alpar@1352: { alpar@1352: return NormSquareMap(m); alpar@1352: } alpar@1352: alpar@431: /// @} athos@244: alpar@2207: } //namespce dim2 alpar@2207: alpar@921: } //namespace lemon athos@201: alpar@2207: #endif //LEMON_DIM2_H