32 /// |
32 /// |
33 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" |
33 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" |
34 /// can be used to determine |
34 /// can be used to determine |
35 /// the rectangular bounding box of a set of |
35 /// the rectangular bounding box of a set of |
36 /// \ref lemon::dim2::Point "dim2::Point"'s. |
36 /// \ref lemon::dim2::Point "dim2::Point"'s. |
37 /// |
|
38 ///\author Attila Bernath |
|
39 |
|
40 |
37 |
41 namespace lemon { |
38 namespace lemon { |
42 |
39 |
43 ///Tools for handling two dimensional coordinates |
40 ///Tools for handling two dimensional coordinates |
44 |
41 |
60 |
57 |
61 public: |
58 public: |
62 |
59 |
63 typedef T Value; |
60 typedef T Value; |
64 |
61 |
65 ///First co-ordinate |
62 ///First coordinate |
66 T x; |
63 T x; |
67 ///Second co-ordinate |
64 ///Second coordinate |
68 T y; |
65 T y; |
69 |
66 |
70 ///Default constructor |
67 ///Default constructor |
71 Point() {} |
68 Point() {} |
72 |
69 |
73 ///Construct an instance from coordinates |
70 ///Construct an instance from coordinates |
74 Point(T a, T b) : x(a), y(b) { } |
71 Point(T a, T b) : x(a), y(b) { } |
75 |
72 |
76 ///The dimension of the vector. |
73 ///The dimension of the vector. |
77 |
74 |
78 ///This class give back always 2. |
75 ///The dimension of the vector. |
79 /// |
76 ///This function always returns 2. |
80 int size() const { return 2; } |
77 int size() const { return 2; } |
81 |
78 |
82 ///Subscripting operator |
79 ///Subscripting operator |
83 |
80 |
84 ///\c p[0] is \c p.x and \c p[1] is \c p.y |
81 ///\c p[0] is \c p.x and \c p[1] is \c p.y |
173 return (x!=u.x) || (y!=u.y); |
170 return (x!=u.x) || (y!=u.y); |
174 } |
171 } |
175 |
172 |
176 }; |
173 }; |
177 |
174 |
178 ///Return an Point |
175 ///Return a Point |
179 |
176 |
180 ///Return an Point |
177 ///Return a Point. |
181 ///\relates Point |
178 ///\relates Point |
182 template <typename T> |
179 template <typename T> |
183 inline Point<T> makePoint(const T& x, const T& y) { |
180 inline Point<T> makePoint(const T& x, const T& y) { |
184 return Point<T>(x, y); |
181 return Point<T>(x, y); |
185 } |
182 } |
186 |
183 |
187 ///Return a vector multiplied by a scalar |
184 ///Return a vector multiplied by a scalar |
188 |
185 |
189 ///Return a vector multiplied by a scalar |
186 ///Return a vector multiplied by a scalar. |
190 ///\relates Point |
187 ///\relates Point |
191 template<typename T> Point<T> operator*(const T &u,const Point<T> &x) { |
188 template<typename T> Point<T> operator*(const T &u,const Point<T> &x) { |
192 return x*u; |
189 return x*u; |
193 } |
190 } |
194 |
191 |
195 ///Read a plainvector from a stream |
192 ///Read a plainvector from a stream |
196 |
193 |
197 ///Read a plainvector from a stream |
194 ///Read a plainvector from a stream. |
198 ///\relates Point |
195 ///\relates Point |
199 /// |
196 /// |
200 template<typename T> |
197 template<typename T> |
201 inline std::istream& operator>>(std::istream &is, Point<T> &z) { |
198 inline std::istream& operator>>(std::istream &is, Point<T> &z) { |
202 char c; |
199 char c; |
232 return os; |
229 return os; |
233 } |
230 } |
234 |
231 |
235 ///Rotate by 90 degrees |
232 ///Rotate by 90 degrees |
236 |
233 |
237 ///Returns its parameter rotated by 90 degrees in positive direction. |
234 ///Returns the parameter rotated by 90 degrees in positive direction. |
238 ///\relates Point |
235 ///\relates Point |
239 /// |
236 /// |
240 template<typename T> |
237 template<typename T> |
241 inline Point<T> rot90(const Point<T> &z) |
238 inline Point<T> rot90(const Point<T> &z) |
242 { |
239 { |
243 return Point<T>(-z.y,z.x); |
240 return Point<T>(-z.y,z.x); |
244 } |
241 } |
245 |
242 |
246 ///Rotate by 180 degrees |
243 ///Rotate by 180 degrees |
247 |
244 |
248 ///Returns its parameter rotated by 180 degrees. |
245 ///Returns the parameter rotated by 180 degrees. |
249 ///\relates Point |
246 ///\relates Point |
250 /// |
247 /// |
251 template<typename T> |
248 template<typename T> |
252 inline Point<T> rot180(const Point<T> &z) |
249 inline Point<T> rot180(const Point<T> &z) |
253 { |
250 { |
254 return Point<T>(-z.x,-z.y); |
251 return Point<T>(-z.x,-z.y); |
255 } |
252 } |
256 |
253 |
257 ///Rotate by 270 degrees |
254 ///Rotate by 270 degrees |
258 |
255 |
259 ///Returns its parameter rotated by 90 degrees in negative direction. |
256 ///Returns the parameter rotated by 90 degrees in negative direction. |
260 ///\relates Point |
257 ///\relates Point |
261 /// |
258 /// |
262 template<typename T> |
259 template<typename T> |
263 inline Point<T> rot270(const Point<T> &z) |
260 inline Point<T> rot270(const Point<T> &z) |
264 { |
261 { |
284 ///Construct an instance from one point |
280 ///Construct an instance from one point |
285 BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; } |
281 BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; } |
286 |
282 |
287 ///Construct an instance from two points |
283 ///Construct an instance from two points |
288 |
284 |
289 ///Construct an instance from two points |
285 ///Construct an instance from two points. |
290 ///\warning The coordinates of the bottom-left corner must be no more |
286 ///\param a The bottom left corner. |
291 ///than those of the top-right one |
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. |
292 BoundingBox(Point<T> a,Point<T> b) |
290 BoundingBox(Point<T> a,Point<T> b) |
293 { |
291 { |
294 bottom_left=a; |
292 bottom_left=a; |
295 top_right=b; |
293 top_right=b; |
296 _empty = false; |
294 _empty = false; |
297 } |
295 } |
298 |
296 |
299 ///Construct an instance from four numbers |
297 ///Construct an instance from four numbers |
300 |
298 |
301 ///Construct an instance from four numbers |
299 ///Construct an instance from four numbers. |
302 ///\warning The coordinates of the bottom-left corner must be no more |
300 ///\param l The left side of the box. |
303 ///than those of the top-right one |
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. |
304 BoundingBox(T l,T b,T r,T t) |
306 BoundingBox(T l,T b,T r,T t) |
305 { |
307 { |
306 bottom_left=Point<T>(l,b); |
308 bottom_left=Point<T>(l,b); |
307 top_right=Point<T>(r,t); |
309 top_right=Point<T>(r,t); |
308 _empty = false; |
310 _empty = false; |
309 } |
311 } |
310 |
312 |
311 ///Were any points added? |
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. |
312 bool empty() const { |
319 bool empty() const { |
313 return _empty; |
320 return _empty; |
314 } |
321 } |
315 |
322 |
316 ///Make the BoundingBox empty |
323 ///Make the BoundingBox empty |
463 T width() const { |
470 T width() const { |
464 return top_right.x-bottom_left.x; |
471 return top_right.x-bottom_left.x; |
465 } |
472 } |
466 |
473 |
467 ///Checks whether a point is inside a bounding box |
474 ///Checks whether a point is inside a bounding box |
468 bool inside(const Point<T>& u){ |
475 bool inside(const Point<T>& u) const { |
469 if (_empty) |
476 if (_empty) |
470 return false; |
477 return false; |
471 else{ |
478 else{ |
472 return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && |
479 return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && |
473 (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); |
480 (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); |
474 } |
481 } |
475 } |
482 } |
476 |
483 |
477 ///Increments a bounding box with a point |
484 ///Increments a bounding box with a point |
|
485 |
|
486 ///Increments a bounding box with a point. |
|
487 /// |
478 BoundingBox& add(const Point<T>& u){ |
488 BoundingBox& add(const Point<T>& u){ |
479 if (_empty){ |
489 if (_empty){ |
480 bottom_left=top_right=u; |
490 bottom_left=top_right=u; |
481 _empty = false; |
491 _empty = false; |
482 } |
492 } |
487 if (top_right.y < u.y) top_right.y = u.y; |
497 if (top_right.y < u.y) top_right.y = u.y; |
488 } |
498 } |
489 return *this; |
499 return *this; |
490 } |
500 } |
491 |
501 |
492 ///Increments a bounding to contain another bounding box |
502 ///Increments a bounding box to contain another bounding box |
|
503 |
|
504 ///Increments a bounding box to contain another bounding box. |
|
505 /// |
493 BoundingBox& add(const BoundingBox &u){ |
506 BoundingBox& add(const BoundingBox &u){ |
494 if ( !u.empty() ){ |
507 if ( !u.empty() ){ |
495 this->add(u.bottomLeft()); |
508 this->add(u.bottomLeft()); |
496 this->add(u.topRight()); |
509 this->add(u.topRight()); |
497 } |
510 } |
498 return *this; |
511 return *this; |
499 } |
512 } |
500 |
513 |
501 ///Intersection of two bounding boxes |
514 ///Intersection of two bounding boxes |
502 BoundingBox operator &(const BoundingBox& u){ |
515 |
|
516 ///Intersection of two bounding boxes. |
|
517 /// |
|
518 BoundingBox operator&(const BoundingBox& u) const { |
503 BoundingBox b; |
519 BoundingBox b; |
504 b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x); |
520 if (this->_empty || u._empty) { |
505 b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y); |
521 b._empty = true; |
506 b.top_right.x=std::min(this->top_right.x,u.top_right.x); |
522 } else { |
507 b.top_right.y=std::min(this->top_right.y,u.top_right.y); |
523 b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x); |
508 b._empty = this->_empty || u._empty || |
524 b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y); |
509 b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.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 } |
510 return b; |
530 return b; |
511 } |
531 } |
512 |
532 |
513 };//class Boundingbox |
533 };//class Boundingbox |
514 |
534 |
515 |
535 |
516 ///Map of x-coordinates of a dim2::Point<>-map |
536 ///Map of x-coordinates of a \ref Point "Point"-map |
517 |
537 |
518 ///\ingroup maps |
538 ///\ingroup maps |
519 ///Map of x-coordinates of a dim2::Point<>-map |
539 ///Map of x-coordinates of a \ref Point "Point"-map. |
520 /// |
540 /// |
521 template<class M> |
541 template<class M> |
522 class XMap |
542 class XMap |
523 { |
543 { |
524 M& _map; |
544 M& _map; |
568 Value operator[](Key k) const {return _map[k].x;} |
588 Value operator[](Key k) const {return _map[k].x;} |
569 }; |
589 }; |
570 |
590 |
571 ///Returns a \ref ConstXMap class |
591 ///Returns a \ref ConstXMap class |
572 |
592 |
573 ///This function just returns an \ref ConstXMap class. |
593 ///This function just returns a \ref ConstXMap class. |
574 /// |
594 /// |
575 ///\ingroup maps |
595 ///\ingroup maps |
576 ///\relates ConstXMap |
596 ///\relates ConstXMap |
577 template<class M> |
597 template<class M> |
578 inline ConstXMap<M> xMap(const M &m) |
598 inline ConstXMap<M> xMap(const M &m) |
579 { |
599 { |
580 return ConstXMap<M>(m); |
600 return ConstXMap<M>(m); |
581 } |
601 } |
582 |
602 |
583 ///Map of y-coordinates of a dim2::Point<>-map |
603 ///Map of y-coordinates of a \ref Point "Point"-map |
584 |
604 |
585 ///\ingroup maps |
605 ///\ingroup maps |
586 ///Map of y-coordinates of a dim2::Point<>-map |
606 ///Map of y-coordinates of a \ref Point "Point"-map. |
587 /// |
607 /// |
588 template<class M> |
608 template<class M> |
589 class YMap |
609 class YMap |
590 { |
610 { |
591 M& _map; |
611 M& _map; |
597 YMap(M& map) : _map(map) {} |
617 YMap(M& map) : _map(map) {} |
598 Value operator[](Key k) const {return _map[k].y;} |
618 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));} |
619 void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));} |
600 }; |
620 }; |
601 |
621 |
602 ///Returns an \ref YMap class |
622 ///Returns a \ref YMap class |
603 |
623 |
604 ///This function just returns an \ref YMap class. |
624 ///This function just returns a \ref YMap class. |
605 /// |
625 /// |
606 ///\ingroup maps |
626 ///\ingroup maps |
607 ///\relates YMap |
627 ///\relates YMap |
608 template<class M> |
628 template<class M> |
609 inline YMap<M> yMap(M &m) |
629 inline YMap<M> yMap(M &m) |
635 Value operator[](Key k) const {return _map[k].y;} |
655 Value operator[](Key k) const {return _map[k].y;} |
636 }; |
656 }; |
637 |
657 |
638 ///Returns a \ref ConstYMap class |
658 ///Returns a \ref ConstYMap class |
639 |
659 |
640 ///This function just returns an \ref ConstYMap class. |
660 ///This function just returns a \ref ConstYMap class. |
641 /// |
661 /// |
642 ///\ingroup maps |
662 ///\ingroup maps |
643 ///\relates ConstYMap |
663 ///\relates ConstYMap |
644 template<class M> |
664 template<class M> |
645 inline ConstYMap<M> yMap(const M &m) |
665 inline ConstYMap<M> yMap(const M &m) |
647 return ConstYMap<M>(m); |
667 return ConstYMap<M>(m); |
648 } |
668 } |
649 |
669 |
650 |
670 |
651 ///\brief Map of the \ref Point::normSquare() "normSquare()" |
671 ///\brief Map of the \ref Point::normSquare() "normSquare()" |
652 ///of an \ref Point "Point"-map |
672 ///of a \ref Point "Point"-map |
653 /// |
673 /// |
654 ///Map of the \ref Point::normSquare() "normSquare()" |
674 ///Map of the \ref Point::normSquare() "normSquare()" |
655 ///of an \ref Point "Point"-map |
675 ///of a \ref Point "Point"-map. |
656 ///\ingroup maps |
676 ///\ingroup maps |
657 /// |
677 /// |
658 template<class M> |
678 template<class M> |
659 class NormSquareMap |
679 class NormSquareMap |
660 { |
680 { |
668 Value operator[](Key k) const {return _map[k].normSquare();} |
688 Value operator[](Key k) const {return _map[k].normSquare();} |
669 }; |
689 }; |
670 |
690 |
671 ///Returns a \ref NormSquareMap class |
691 ///Returns a \ref NormSquareMap class |
672 |
692 |
673 ///This function just returns an \ref NormSquareMap class. |
693 ///This function just returns a \ref NormSquareMap class. |
674 /// |
694 /// |
675 ///\ingroup maps |
695 ///\ingroup maps |
676 ///\relates NormSquareMap |
696 ///\relates NormSquareMap |
677 template<class M> |
697 template<class M> |
678 inline NormSquareMap<M> normSquareMap(const M &m) |
698 inline NormSquareMap<M> normSquareMap(const M &m) |