COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/dim2.h @ 39:0a01d811071f

Last change on this file since 39:0a01d811071f was 39:0a01d811071f, checked in by Alpar Juttner <alpar@…>, 17 years ago

Happy New Year (update the copyright headers)

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