COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dim2.h @ 2214:a886e48e0d91

Last change on this file since 2214:a886e48e0d91 was 2214:a886e48e0d91, checked in by Alpar Juttner, 13 years ago

Doc improvements

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