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