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