COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dim2.h

Last change on this file was 2562:27c54b7f4f1d, checked in by Peter Kovacs, 12 years ago

Improvements and fixes in dim2.h.

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