changeset 310 | 2bf7c645d5a6 |
parent 250 | d0aae16df1bb |
child 317 | 64f8f7cc6168 |
8:dd9c19843b40 | 9:6f3cb84bd930 |
---|---|
26 ///\brief A simple two dimensional vector and a bounding box implementation |
26 ///\brief A simple two dimensional vector and a bounding box implementation |
27 /// |
27 /// |
28 /// The class \ref lemon::dim2::Point "dim2::Point" implements |
28 /// The class \ref lemon::dim2::Point "dim2::Point" implements |
29 /// a two dimensional vector with the usual operations. |
29 /// a two dimensional vector with the usual operations. |
30 /// |
30 /// |
31 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" |
31 /// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine |
32 /// can be used to determine |
|
33 /// the rectangular bounding box of a set of |
32 /// the rectangular bounding box of a set of |
34 /// \ref lemon::dim2::Point "dim2::Point"'s. |
33 /// \ref lemon::dim2::Point "dim2::Point"'s. |
35 |
34 |
36 namespace lemon { |
35 namespace lemon { |
37 |
36 |
42 namespace dim2 { |
41 namespace dim2 { |
43 |
42 |
44 /// \addtogroup misc |
43 /// \addtogroup misc |
45 /// @{ |
44 /// @{ |
46 |
45 |
47 /// A simple two dimensional vector (plain vector) implementation |
46 /// Two dimensional vector (plain vector) |
48 |
47 |
49 /// A simple two dimensional vector (plain vector) implementation |
48 /// A simple two dimensional vector (plain vector) implementation |
50 /// with the usual vector operations. |
49 /// with the usual vector operations. |
51 template<typename T> |
50 template<typename T> |
52 class Point { |
51 class Point { |
258 return Point<T>(z.y,-z.x); |
257 return Point<T>(z.y,-z.x); |
259 } |
258 } |
260 |
259 |
261 |
260 |
262 |
261 |
263 /// A class to calculate or store the bounding box of plain vectors. |
262 /// Bounding box of plain vectors (\ref Point points). |
264 |
263 |
265 /// A class to calculate or store the bounding box of plain vectors. |
264 /// A class to calculate or store the bounding box of plain vectors |
266 /// |
265 /// (\ref Point points). |
267 template<typename T> |
266 template<typename T> |
268 class BoundingBox { |
267 class Box { |
269 Point<T> _bottom_left, _top_right; |
268 Point<T> _bottom_left, _top_right; |
270 bool _empty; |
269 bool _empty; |
271 public: |
270 public: |
272 |
271 |
273 ///Default constructor: creates an empty bounding box |
272 ///Default constructor: creates an empty box |
274 BoundingBox() { _empty = true; } |
273 Box() { _empty = true; } |
275 |
274 |
276 ///Construct an instance from one point |
275 ///Construct a box from one point |
277 BoundingBox(Point<T> a) { |
276 Box(Point<T> a) { |
278 _bottom_left = _top_right = a; |
277 _bottom_left = _top_right = a; |
279 _empty = false; |
278 _empty = false; |
280 } |
279 } |
281 |
280 |
282 ///Construct an instance from two points |
281 ///Construct a box from two points |
283 |
282 |
284 ///Construct an instance from two points. |
283 ///Construct a box from two points. |
285 ///\param a The bottom left corner. |
284 ///\param a The bottom left corner. |
286 ///\param b The top right corner. |
285 ///\param b The top right corner. |
287 ///\warning The coordinates of the bottom left corner must be no more |
286 ///\warning The coordinates of the bottom left corner must be no more |
288 ///than those of the top right one. |
287 ///than those of the top right one. |
289 BoundingBox(Point<T> a,Point<T> b) |
288 Box(Point<T> a,Point<T> b) |
290 { |
289 { |
291 _bottom_left = a; |
290 _bottom_left = a; |
292 _top_right = b; |
291 _top_right = b; |
293 _empty = false; |
292 _empty = false; |
294 } |
293 } |
295 |
294 |
296 ///Construct an instance from four numbers |
295 ///Construct a box from four numbers |
297 |
296 |
298 ///Construct an instance from four numbers. |
297 ///Construct a box from four numbers. |
299 ///\param l The left side of the box. |
298 ///\param l The left side of the box. |
300 ///\param b The bottom of the box. |
299 ///\param b The bottom of the box. |
301 ///\param r The right side of the box. |
300 ///\param r The right side of the box. |
302 ///\param t The top of the box. |
301 ///\param t The top of the box. |
303 ///\warning The left side must be no more than the right side and |
302 ///\warning The left side must be no more than the right side and |
304 ///bottom must be no more than the top. |
303 ///bottom must be no more than the top. |
305 BoundingBox(T l,T b,T r,T t) |
304 Box(T l,T b,T r,T t) |
306 { |
305 { |
307 _bottom_left=Point<T>(l,b); |
306 _bottom_left=Point<T>(l,b); |
308 _top_right=Point<T>(r,t); |
307 _top_right=Point<T>(r,t); |
309 _empty = false; |
308 _empty = false; |
310 } |
309 } |
311 |
310 |
312 ///Return \c true if the bounding box is empty. |
311 ///Return \c true if the box is empty. |
313 |
312 |
314 ///Return \c true if the bounding box is empty (i.e. return \c false |
313 ///Return \c true if the box is empty (i.e. return \c false |
315 ///if at least one point was added to the box or the coordinates of |
314 ///if at least one point was added to the box or the coordinates of |
316 ///the box were set). |
315 ///the box were set). |
317 /// |
316 /// |
318 ///The coordinates of an empty bounding box are not defined. |
317 ///The coordinates of an empty box are not defined. |
319 bool empty() const { |
318 bool empty() const { |
320 return _empty; |
319 return _empty; |
321 } |
320 } |
322 |
321 |
323 ///Make the BoundingBox empty |
322 ///Make the box empty |
324 void clear() { |
323 void clear() { |
325 _empty = true; |
324 _empty = true; |
326 } |
325 } |
327 |
326 |
328 ///Give back the bottom left corner of the box |
327 ///Give back the bottom left corner of the box |
329 |
328 |
330 ///Give back the bottom left corner of the box. |
329 ///Give back the bottom left corner of the box. |
331 ///If the bounding box is empty, then the return value is not defined. |
330 ///If the box is empty, then the return value is not defined. |
332 Point<T> bottomLeft() const { |
331 Point<T> bottomLeft() const { |
333 return _bottom_left; |
332 return _bottom_left; |
334 } |
333 } |
335 |
334 |
336 ///Set the bottom left corner of the box |
335 ///Set the bottom left corner of the box |
342 } |
341 } |
343 |
342 |
344 ///Give back the top right corner of the box |
343 ///Give back the top right corner of the box |
345 |
344 |
346 ///Give back the top right corner of the box. |
345 ///Give back the top right corner of the box. |
347 ///If the bounding box is empty, then the return value is not defined. |
346 ///If the box is empty, then the return value is not defined. |
348 Point<T> topRight() const { |
347 Point<T> topRight() const { |
349 return _top_right; |
348 return _top_right; |
350 } |
349 } |
351 |
350 |
352 ///Set the top right corner of the box |
351 ///Set the top right corner of the box |
358 } |
357 } |
359 |
358 |
360 ///Give back the bottom right corner of the box |
359 ///Give back the bottom right corner of the box |
361 |
360 |
362 ///Give back the bottom right corner of the box. |
361 ///Give back the bottom right corner of the box. |
363 ///If the bounding box is empty, then the return value is not defined. |
362 ///If the box is empty, then the return value is not defined. |
364 Point<T> bottomRight() const { |
363 Point<T> bottomRight() const { |
365 return Point<T>(_top_right.x,_bottom_left.y); |
364 return Point<T>(_top_right.x,_bottom_left.y); |
366 } |
365 } |
367 |
366 |
368 ///Set the bottom right corner of the box |
367 ///Set the bottom right corner of the box |
375 } |
374 } |
376 |
375 |
377 ///Give back the top left corner of the box |
376 ///Give back the top left corner of the box |
378 |
377 |
379 ///Give back the top left corner of the box. |
378 ///Give back the top left corner of the box. |
380 ///If the bounding box is empty, then the return value is not defined. |
379 ///If the box is empty, then the return value is not defined. |
381 Point<T> topLeft() const { |
380 Point<T> topLeft() const { |
382 return Point<T>(_bottom_left.x,_top_right.y); |
381 return Point<T>(_bottom_left.x,_top_right.y); |
383 } |
382 } |
384 |
383 |
385 ///Set the top left corner of the box |
384 ///Set the top left corner of the box |
392 } |
391 } |
393 |
392 |
394 ///Give back the bottom of the box |
393 ///Give back the bottom of the box |
395 |
394 |
396 ///Give back the bottom of the box. |
395 ///Give back the bottom of the box. |
397 ///If the bounding box is empty, then the return value is not defined. |
396 ///If the box is empty, then the return value is not defined. |
398 T bottom() const { |
397 T bottom() const { |
399 return _bottom_left.y; |
398 return _bottom_left.y; |
400 } |
399 } |
401 |
400 |
402 ///Set the bottom of the box |
401 ///Set the bottom of the box |
408 } |
407 } |
409 |
408 |
410 ///Give back the top of the box |
409 ///Give back the top of the box |
411 |
410 |
412 ///Give back the top of the box. |
411 ///Give back the top of the box. |
413 ///If the bounding box is empty, then the return value is not defined. |
412 ///If the box is empty, then the return value is not defined. |
414 T top() const { |
413 T top() const { |
415 return _top_right.y; |
414 return _top_right.y; |
416 } |
415 } |
417 |
416 |
418 ///Set the top of the box |
417 ///Set the top of the box |
424 } |
423 } |
425 |
424 |
426 ///Give back the left side of the box |
425 ///Give back the left side of the box |
427 |
426 |
428 ///Give back the left side of the box. |
427 ///Give back the left side of the box. |
429 ///If the bounding box is empty, then the return value is not defined. |
428 ///If the box is empty, then the return value is not defined. |
430 T left() const { |
429 T left() const { |
431 return _bottom_left.x; |
430 return _bottom_left.x; |
432 } |
431 } |
433 |
432 |
434 ///Set the left side of the box |
433 ///Set the left side of the box |
440 } |
439 } |
441 |
440 |
442 /// Give back the right side of the box |
441 /// Give back the right side of the box |
443 |
442 |
444 /// Give back the right side of the box. |
443 /// Give back the right side of the box. |
445 ///If the bounding box is empty, then the return value is not defined. |
444 ///If the box is empty, then the return value is not defined. |
446 T right() const { |
445 T right() const { |
447 return _top_right.x; |
446 return _top_right.x; |
448 } |
447 } |
449 |
448 |
450 ///Set the right side of the box |
449 ///Set the right side of the box |
456 } |
455 } |
457 |
456 |
458 ///Give back the height of the box |
457 ///Give back the height of the box |
459 |
458 |
460 ///Give back the height of the box. |
459 ///Give back the height of the box. |
461 ///If the bounding box is empty, then the return value is not defined. |
460 ///If the box is empty, then the return value is not defined. |
462 T height() const { |
461 T height() const { |
463 return _top_right.y-_bottom_left.y; |
462 return _top_right.y-_bottom_left.y; |
464 } |
463 } |
465 |
464 |
466 ///Give back the width of the box |
465 ///Give back the width of the box |
467 |
466 |
468 ///Give back the width of the box. |
467 ///Give back the width of the box. |
469 ///If the bounding box is empty, then the return value is not defined. |
468 ///If the box is empty, then the return value is not defined. |
470 T width() const { |
469 T width() const { |
471 return _top_right.x-_bottom_left.x; |
470 return _top_right.x-_bottom_left.x; |
472 } |
471 } |
473 |
472 |
474 ///Checks whether a point is inside a bounding box |
473 ///Checks whether a point is inside the box |
475 bool inside(const Point<T>& u) const { |
474 bool inside(const Point<T>& u) const { |
476 if (_empty) |
475 if (_empty) |
477 return false; |
476 return false; |
478 else { |
477 else { |
479 return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 && |
478 return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 && |
480 (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 ); |
479 (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 ); |
481 } |
480 } |
482 } |
481 } |
483 |
482 |
484 ///Increments a bounding box with a point |
483 ///Increments the box with a point |
485 |
484 |
486 ///Increments a bounding box with a point. |
485 ///Increments the box with a point. |
487 /// |
486 /// |
488 BoundingBox& add(const Point<T>& u){ |
487 Box& add(const Point<T>& u){ |
489 if (_empty) { |
488 if (_empty) { |
490 _bottom_left = _top_right = u; |
489 _bottom_left = _top_right = u; |
491 _empty = false; |
490 _empty = false; |
492 } |
491 } |
493 else { |
492 else { |
497 if (_top_right.y < u.y) _top_right.y = u.y; |
496 if (_top_right.y < u.y) _top_right.y = u.y; |
498 } |
497 } |
499 return *this; |
498 return *this; |
500 } |
499 } |
501 |
500 |
502 ///Increments a bounding box to contain another bounding box |
501 ///Increments the box to contain another box |
503 |
502 |
504 ///Increments a bounding box to contain another bounding box. |
503 ///Increments the box to contain another box. |
505 /// |
504 /// |
506 BoundingBox& add(const BoundingBox &u){ |
505 Box& add(const Box &u){ |
507 if ( !u.empty() ){ |
506 if ( !u.empty() ){ |
508 add(u._bottom_left); |
507 add(u._bottom_left); |
509 add(u._top_right); |
508 add(u._top_right); |
510 } |
509 } |
511 return *this; |
510 return *this; |
512 } |
511 } |
513 |
512 |
514 ///Intersection of two bounding boxes |
513 ///Intersection of two boxes |
515 |
514 |
516 ///Intersection of two bounding boxes. |
515 ///Intersection of two boxes. |
517 /// |
516 /// |
518 BoundingBox operator&(const BoundingBox& u) const { |
517 Box operator&(const Box& u) const { |
519 BoundingBox b; |
518 Box b; |
520 if (_empty || u._empty) { |
519 if (_empty || u._empty) { |
521 b._empty = true; |
520 b._empty = true; |
522 } else { |
521 } else { |
523 b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x); |
522 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); |
523 b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y); |
528 b._bottom_left.y > b._top_right.y; |
527 b._bottom_left.y > b._top_right.y; |
529 } |
528 } |
530 return b; |
529 return b; |
531 } |
530 } |
532 |
531 |
533 };//class Boundingbox |
532 };//class Box |
534 |
533 |
535 |
534 |
536 ///Read a bounding box from a stream |
535 ///Read a box from a stream |
537 |
536 |
538 ///Read a bounding box from a stream. |
537 ///Read a box from a stream. |
539 ///\relates BoundingBox |
538 ///\relates Box |
540 template<typename T> |
539 template<typename T> |
541 inline std::istream& operator>>(std::istream &is, BoundingBox<T>& b) { |
540 inline std::istream& operator>>(std::istream &is, Box<T>& b) { |
542 char c; |
541 char c; |
543 Point<T> p; |
542 Point<T> p; |
544 if (is >> c) { |
543 if (is >> c) { |
545 if (c != '(') is.putback(c); |
544 if (c != '(') is.putback(c); |
546 } else { |
545 } else { |
561 is.clear(); |
560 is.clear(); |
562 } |
561 } |
563 return is; |
562 return is; |
564 } |
563 } |
565 |
564 |
566 ///Write a bounding box to a stream |
565 ///Write a box to a stream |
567 |
566 |
568 ///Write a bounding box to a stream. |
567 ///Write a box to a stream. |
569 ///\relates BoundingBox |
568 ///\relates Box |
570 template<typename T> |
569 template<typename T> |
571 inline std::ostream& operator<<(std::ostream &os, const BoundingBox<T>& b) |
570 inline std::ostream& operator<<(std::ostream &os, const Box<T>& b) |
572 { |
571 { |
573 os << "(" << b.bottomLeft() << "," << b.topRight() << ")"; |
572 os << "(" << b.bottomLeft() << "," << b.topRight() << ")"; |
574 return os; |
573 return os; |
575 } |
574 } |
576 |
575 |