BoundingBox.h

Go to the documentation of this file.

#ifndef BoundingBox_HEADER
#define BoundingBox_HEADER

#include <algorithm>
#include <utilities/identity.h>

#include "Point.h"
#include "ProjectionPlane.h"

namespace Geometry {

/***************************************************************************
 * Compute an orthogonal bounding box around a set of points.
 ***************************************************************************/
template <unsigned d>
struct BoundingBox {
  typedef Geometry::Point<d> Point;
  static const unsigned dimension = d;

  Point mincorner;
  double extent;

  BoundingBox(): mincorner(0.0), extent(0.0) { }

  BoundingBox(Point p, double e)
    : mincorner(p), extent(e) { }

  /* Compute the bounding box of the points indicated by the range. */
  template <class iterator>
  BoundingBox(iterator begin, iterator end) {
    init(begin, end, hudson::form_identity(*begin));
  }

  /* Compute the bounding box of the points indicated by the range,
     projected to the given plane. */
  template <class iterator, unsigned ambient>
  BoundingBox(iterator begin, iterator end,
              const ProjectionPlane<ambient, d>& plane) {
    typedef ProjectionPlane<ambient, d> ProjectionPlane;
    init(begin, end, std::bind1st(std::mem_fun(&ProjectionPlane::project1), &plane));
  }

  /* Compute the bounding box of the points indicated by the range,
     transformed by the given operator. */
  template <class iterator, class xform>
  BoundingBox(iterator begin, iterator end, const xform& x) {
    init(begin, end, x);
  }

  /* Scale the box to have the same center but have
   * a buffer around its sides.  For example, a buffer
   * of 1.0 yields a box three times bigger. */
  BoundingBox scale(double buffer) const {
    BoundingBox bigbox;
    bigbox.mincorner = mincorner -
      (Point(1.0) * buffer * extent);
    bigbox.extent = extent * (1.0 + 2.0 * buffer);
    return bigbox;
  }

  bool bitwiseEqual(const BoundingBox& other) const {
    return extent == other.extent
      && mincorner.bitwiseEqual(other.mincorner);
  }

  /* Open box */
  bool inBox(const Point& p) const {
    for(size_t i = 0; i < d; ++i) {
      if (p[i] < mincorner[i] || p[i] > mincorner[i] + extent) {
        return false;
      }
    }
    return true;
  }

  bool inClosedBox(const Point& p) const {
    for(size_t i = 0; i < d; ++i) {
      if (p[i] <= mincorner[i] || p[i] >= mincorner[i] + extent) {
        return false;
      }
    }
    return true;
  }

  std::string toString() const {
    char buffer[4096];
    sprintf(buffer, ", sidelength = %g", extent);
    return mincorner.toString() + buffer;
  }

  private:
  template <class iterator, class xform>
  void init(iterator begin, iterator end, const xform& x) {
    assert(begin != end);
    Point mincoords, maxcoords; // uninitialized
    iterator it = begin;
    mincoords = maxcoords = x(*it); // don't init to zero!
    Point sum(x(*begin));
    size_t n = 1;
    for(++it ; it != end; ++it) {
      Point p = x(*it);
      n++;
      for(unsigned i = 0; i < d; i++) {
        mincoords[i] = std::min(mincoords[i], p[i]);
        maxcoords[i] = std::max(maxcoords[i], p[i]);
      }
    }
    extent = 0.0;
    for (unsigned i = 0; i < d; i++) {
      extent = std::max(maxcoords[i] - mincoords[i], extent);
    }
    Point center = (maxcoords + mincoords) * 0.5;
    mincorner = center - Point(1) * (extent / 2.0);
    /* in case of numerical error in the previous */
    if ( (mincoords - mincorner).norm1() < 0.0 ) {
      mincorner = mincoords;
    }
  }
};

}

#endif

---