COIN-OR::LEMON - Graph Library

source: lemon/lemon/dim2.h @ 8:a1b1d672f37a

Last change on this file since 8:a1b1d672f37a was 8:a1b1d672f37a, checked in by Alpar Juttner <alpar@…>, 11 years ago

Port dim2.h from svn -r3422

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