COIN-OR::LEMON - Graph Library

source: lemon/lemon/dim2.h @ 257:8d76a7bf9961

Last change on this file since 257:8d76a7bf9961 was 241:92f046dd7f6c, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Improvements in dim2::BoundingBox? (ticket #126)

  • Rename the private varibles to start with underscore.
  • Doc improvements.
File size: 17.2 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
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
24///\ingroup misc
25///\file
26///\brief A simple two dimensional vector and a bounding box implementation
27///
28/// The class \ref lemon::dim2::Point "dim2::Point" implements
29/// a two dimensional vector with the usual operations.
30///
31/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
32/// can be used to determine
33/// the rectangular bounding box of a set of
34/// \ref lemon::dim2::Point "dim2::Point"'s.
35
36namespace lemon {
37
38  ///Tools for handling two dimensional coordinates
39
40  ///This namespace is a storage of several
41  ///tools for handling two dimensional coordinates
42  namespace dim2 {
43
44  /// \addtogroup misc
45  /// @{
46
47  /// A simple two dimensional vector (plain vector) implementation
48
49  /// A simple two dimensional vector (plain vector) implementation
50  /// with the usual vector operations.
51  template<typename T>
52    class Point {
53
54    public:
55
56      typedef T Value;
57
58      ///First coordinate
59      T x;
60      ///Second coordinate
61      T y;
62
63      ///Default constructor
64      Point() {}
65
66      ///Construct an instance from coordinates
67      Point(T a, T b) : x(a), y(b) { }
68
69      ///Returns the dimension of the vector (i.e. returns 2).
70
71      ///The dimension of the vector.
72      ///This function always returns 2.
73      int size() const { return 2; }
74
75      ///Subscripting operator
76
77      ///\c p[0] is \c p.x and \c p[1] is \c p.y
78      ///
79      T& operator[](int idx) { return idx == 0 ? x : y; }
80
81      ///Const subscripting operator
82
83      ///\c p[0] is \c p.x and \c p[1] is \c p.y
84      ///
85      const T& operator[](int idx) const { return idx == 0 ? x : y; }
86
87      ///Conversion constructor
88      template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
89
90      ///Give back the square of the norm of the vector
91      T normSquare() const {
92        return x*x+y*y;
93      }
94
95      ///Increment the left hand side by \c u
96      Point<T>& operator +=(const Point<T>& u) {
97        x += u.x;
98        y += u.y;
99        return *this;
100      }
101
102      ///Decrement the left hand side by \c u
103      Point<T>& operator -=(const Point<T>& u) {
104        x -= u.x;
105        y -= u.y;
106        return *this;
107      }
108
109      ///Multiply the left hand side with a scalar
110      Point<T>& operator *=(const T &u) {
111        x *= u;
112        y *= u;
113        return *this;
114      }
115
116      ///Divide the left hand side by a scalar
117      Point<T>& operator /=(const T &u) {
118        x /= u;
119        y /= u;
120        return *this;
121      }
122
123      ///Return the scalar product of two vectors
124      T operator *(const Point<T>& u) const {
125        return x*u.x+y*u.y;
126      }
127
128      ///Return the sum of two vectors
129      Point<T> operator+(const Point<T> &u) const {
130        Point<T> b=*this;
131        return b+=u;
132      }
133
134      ///Return the negative of the vector
135      Point<T> operator-() const {
136        Point<T> b=*this;
137        b.x=-b.x; b.y=-b.y;
138        return b;
139      }
140
141      ///Return the difference of two vectors
142      Point<T> operator-(const Point<T> &u) const {
143        Point<T> b=*this;
144        return b-=u;
145      }
146
147      ///Return a vector multiplied by a scalar
148      Point<T> operator*(const T &u) const {
149        Point<T> b=*this;
150        return b*=u;
151      }
152
153      ///Return a vector divided by a scalar
154      Point<T> operator/(const T &u) const {
155        Point<T> b=*this;
156        return b/=u;
157      }
158
159      ///Test equality
160      bool operator==(const Point<T> &u) const {
161        return (x==u.x) && (y==u.y);
162      }
163
164      ///Test inequality
165      bool operator!=(Point u) const {
166        return  (x!=u.x) || (y!=u.y);
167      }
168
169    };
170
171  ///Return a Point
172
173  ///Return a Point.
174  ///\relates Point
175  template <typename T>
176  inline Point<T> makePoint(const T& x, const T& y) {
177    return Point<T>(x, y);
178  }
179
180  ///Return a vector multiplied by a scalar
181
182  ///Return a vector multiplied by a scalar.
183  ///\relates Point
184  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
185    return x*u;
186  }
187
188  ///Read a plain vector from a stream
189
190  ///Read a plain vector from a stream.
191  ///\relates Point
192  ///
193  template<typename T>
194  inline std::istream& operator>>(std::istream &is, Point<T> &z) {
195    char c;
196    if (is >> c) {
197      if (c != '(') is.putback(c);
198    } else {
199      is.clear();
200    }
201    if (!(is >> z.x)) return is;
202    if (is >> c) {
203      if (c != ',') is.putback(c);
204    } else {
205      is.clear();
206    }
207    if (!(is >> z.y)) return is;
208    if (is >> c) {
209      if (c != ')') is.putback(c);
210    } else {
211      is.clear();
212    }
213    return is;
214  }
215
216  ///Write a plain vector to a stream
217
218  ///Write a plain vector to a stream.
219  ///\relates Point
220  ///
221  template<typename T>
222  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
223  {
224    os << "(" << z.x << ", " << z.y << ")";
225    return os;
226  }
227
228  ///Rotate by 90 degrees
229
230  ///Returns the parameter rotated by 90 degrees in positive direction.
231  ///\relates Point
232  ///
233  template<typename T>
234  inline Point<T> rot90(const Point<T> &z)
235  {
236    return Point<T>(-z.y,z.x);
237  }
238
239  ///Rotate by 180 degrees
240
241  ///Returns the parameter rotated by 180 degrees.
242  ///\relates Point
243  ///
244  template<typename T>
245  inline Point<T> rot180(const Point<T> &z)
246  {
247    return Point<T>(-z.x,-z.y);
248  }
249
250  ///Rotate by 270 degrees
251
252  ///Returns the parameter rotated by 90 degrees in negative direction.
253  ///\relates Point
254  ///
255  template<typename T>
256  inline Point<T> rot270(const Point<T> &z)
257  {
258    return Point<T>(z.y,-z.x);
259  }
260
261
262
263    /// A class to calculate or store the bounding box of plain vectors.
264
265    /// A class to calculate or store the bounding box of plain vectors.
266    ///
267    template<typename T>
268    class BoundingBox {
269      Point<T> _bottom_left, _top_right;
270      bool _empty;
271    public:
272
273      ///Default constructor: creates an empty bounding box
274      BoundingBox() { _empty = true; }
275
276      ///Construct an instance from one point
277      BoundingBox(Point<T> a) {
278        _bottom_left = _top_right = a;
279        _empty = false;
280      }
281
282      ///Construct an instance from two points
283
284      ///Construct an instance from two points.
285      ///\param a The bottom left corner.
286      ///\param b The top right corner.
287      ///\warning The coordinates of the bottom left corner must be no more
288      ///than those of the top right one.
289      BoundingBox(Point<T> a,Point<T> b)
290      {
291        _bottom_left = a;
292        _top_right = b;
293        _empty = false;
294      }
295
296      ///Construct an instance from four numbers
297
298      ///Construct an instance from four numbers.
299      ///\param l The left side of the box.
300      ///\param b The bottom of the box.
301      ///\param r The right side of the box.
302      ///\param t The top of the box.
303      ///\warning The left side must be no more than the right side and
304      ///bottom must be no more than the top.
305      BoundingBox(T l,T b,T r,T t)
306      {
307        _bottom_left=Point<T>(l,b);
308        _top_right=Point<T>(r,t);
309        _empty = false;
310      }
311
312      ///Return \c true if the bounding box is empty.
313
314      ///Return \c true if the bounding box is empty (i.e. return \c false
315      ///if at least one point was added to the box or the coordinates of
316      ///the box were set).
317      ///
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 = true;
326      }
327
328      ///Give back the bottom left corner of the box
329
330      ///Give back the bottom left corner of the box.
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 of the box
337
338      ///Set the bottom left corner of the box.
339      ///\pre The box must not be empty.
340      void bottomLeft(Point<T> p) {
341        _bottom_left = p;
342      }
343
344      ///Give back the top right corner of the box
345
346      ///Give back the top right corner of the box.
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 of the box
353
354      ///Set the top right corner of the box.
355      ///\pre The box must not be empty.
356      void topRight(Point<T> p) {
357        _top_right = p;
358      }
359
360      ///Give back the bottom right corner of the box
361
362      ///Give back the bottom right corner of the box.
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 of the box
369
370      ///Set the bottom right corner of the box.
371      ///\pre The box must not be empty.
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 of the box
378
379      ///Give back the top left corner of the box.
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 of the box
386
387      ///Set the top left corner of the box.
388      ///\pre The box must not be empty.
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      ///\pre The box must not be empty.
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      ///\pre The box must not be empty.
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      ///\pre The box must not be empty.
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      ///\pre The box must not be empty.
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          add(u._bottom_left);
509          add(u._top_right);
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 (_empty || u._empty) {
521          b._empty = true;
522        } else {
523          b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
524          b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
525          b._top_right.x = std::min(_top_right.x, u._top_right.x);
526          b._top_right.y = std::min(_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  template<class M>
678  class NormSquareMap
679  {
680    const M& _map;
681  public:
682
683    typedef typename M::Value::Value Value;
684    typedef typename M::Key Key;
685    ///\e
686    NormSquareMap(const M &map) : _map(map) {}
687    Value operator[](Key k) const {return _map[k].normSquare();}
688  };
689
690  ///Returns a \ref NormSquareMap class
691
692  ///This function just returns a \ref NormSquareMap class.
693  ///
694  ///\ingroup maps
695  ///\relates NormSquareMap
696  template<class M>
697  inline NormSquareMap<M> normSquareMap(const M &m)
698  {
699    return NormSquareMap<M>(m);
700  }
701
702  /// @}
703
704  } //namespce dim2
705
706} //namespace lemon
707
708#endif //LEMON_DIM2_H
Note: See TracBrowser for help on using the repository browser.