source/geometry/boundingbox.h

   1 #ifndef MSP_GEOMETRY_BOUNDINGBOX_H_
   2 #define MSP_GEOMETRY_BOUNDINGBOX_H_
   3
   4 #include <algorithm>
   5 #include <stdexcept>
   6 #include <msp/linal/vector.h>
   7
   8 namespace Msp {
   9 namespace Geometry {
  10
  11 template<typename T, unsigned D>
  12 class BoundingBox
  13 {
  14 private:
  15         LinAl::Vector<T, D> min_pt;
  16         LinAl::Vector<T, D> max_pt;
  17         bool empty;
  18         bool negated;
  19
  20 public:
  21         BoundingBox();
  22         BoundingBox(const LinAl::Vector<T, D> &, const LinAl::Vector<T, D> &);
  23
  24         static BoundingBox negate(const BoundingBox &);
  25
  26         const LinAl::Vector<T, D> &get_minimum_point() const { return min_pt; }
  27         T get_minimum_coordinate(unsigned i) const { return min_pt[i]; }
  28         const LinAl::Vector<T, D> &get_maximum_point() const { return max_pt; }
  29         T get_maximum_coordinate(unsigned i) const { return max_pt[i]; }
  30         LinAl::Vector<T, D> get_dimensions() const { return max_pt-min_pt; }
  31         T get_dimension(unsigned i) const { return max_pt[i]-min_pt[i]; }
  32
  33         bool is_empty() const { return empty && !negated; }
  34         bool is_space() const { return empty && negated; }
  35         bool is_negated() const { return negated; }
  36 };
  37
  38 template<typename T, unsigned D>
  39 inline BoundingBox<T, D>::BoundingBox():
  40         empty(true),
  41         negated(false)
  42 { }
  43
  44 template<typename T, unsigned D>
  45 inline BoundingBox<T, D>::BoundingBox(const LinAl::Vector<T, D> &n, const LinAl::Vector<T, D> &x):
  46         min_pt(n),
  47         max_pt(x),
  48         empty(false),
  49         negated(false)
  50 {
  51         for(unsigned i=0; i<D; ++i)
  52                 if(min_pt[i]>max_pt[i])
  53                         throw std::invalid_argument("BoundingBox::BoundingBox");
  54 }
  55
  56 template<typename T, unsigned D>
  57 inline BoundingBox<T, D> BoundingBox<T, D>::negate(const BoundingBox<T, D> &bb)
  58 {
  59         BoundingBox<T, D> result = bb;
  60         result.negated = !bb.negated;
  61         return result;
  62 }
  63
  64 template<typename T, unsigned D>
  65 inline BoundingBox<T, D> operator&(const BoundingBox<T, D> &bb1, const BoundingBox<T, D> &bb2)
  66 {
  67         if(bb1.is_empty() || bb2.is_empty())
  68                 return BoundingBox<T, D>();
  69
  70         if(bb1.is_negated())
  71         {
  72                 if(bb2.is_negated())
  73                         return ~((~bb1)|(~bb2));
  74                 else
  75                         return bb2&bb1;
  76         }
  77
  78         LinAl::Vector<T, D> result_min;
  79         LinAl::Vector<T, D> result_max;
  80
  81         if(bb2.is_negated())
  82         {
  83                 // This is effectively subtraction of (non-negated) bb2 from bb1
  84                 int uncovered_axis = -1;
  85                 for(unsigned i=0; i<D; ++i)
  86                         if(bb1.get_minimum_coordinate(i)<bb2.get_minimum_coordinate(i) || bb1.get_maximum_coordinate(i)>bb2.get_maximum_coordinate(i))
  87                         {
  88                                 if(uncovered_axis!=-1)
  89                                         return bb1;
  90                                 uncovered_axis = i;
  91                         }
  92
  93                 if(uncovered_axis==-1)
  94                         return BoundingBox<T, D>();
  95
  96                 result_min = bb1.get_minimum_point();
  97                 result_max = bb1.get_maximum_point();
  98                 if(bb2.get_minimum_coordinate(uncovered_axis)<bb1.get_minimum_coordinate(uncovered_axis))
  99                         result_min[uncovered_axis] = bb2.get_maximum_coordinate(uncovered_axis);
 100                 else
 101                         result_max[uncovered_axis] = bb2.get_minimum_coordinate(uncovered_axis);
 102         }
 103         else
 104         {
 105                 for(unsigned i=0; i<D; ++i)
 106                 {
 107                         result_min[i] = std::max(bb1.get_minimum_coordinate(i), bb2.get_minimum_coordinate(i));
 108                         result_max[i] = std::min(bb1.get_maximum_coordinate(i), bb2.get_maximum_coordinate(i));
 109                         if(result_min[i]>result_max[i])
 110                                 return BoundingBox<T, D>();
 111                 }
 112         }
 113
 114         return BoundingBox<T, D>(result_min, result_max);
 115 }
 116
 117 template<typename T, unsigned D>
 118 inline BoundingBox<T, D> operator|(const BoundingBox<T, D> &bb1, const BoundingBox<T, D> &bb2)
 119 {
 120         if(bb1.is_empty())
 121                 return bb2;
 122         if(bb2.is_empty())
 123                 return bb1;
 124
 125         if(bb1.is_negated())
 126                 return ~((~bb1)&(~bb2));
 127         else if(bb2.is_negated())
 128                 return ~((~bb2)&(~bb1));
 129
 130         LinAl::Vector<T, D> result_min;
 131         LinAl::Vector<T, D> result_max;
 132         for(unsigned i=0; i<D; ++i)
 133         {
 134                 result_min[i] = std::min(bb1.get_minimum_coordinate(i), bb2.get_minimum_coordinate(i));
 135                 result_max[i] = std::max(bb1.get_maximum_coordinate(i), bb2.get_maximum_coordinate(i));
 136         }
 137
 138         return BoundingBox<T, D>(result_min, result_max);
 139 }
 140
 141 template<typename T, unsigned D>
 142 inline BoundingBox<T, D> operator~(const BoundingBox<T, D> &bb)
 143 {
 144         return BoundingBox<T, D>::negate(bb);
 145 }
 146
 147 } // namespace Geometry
 148 } // namespace Msp
 149
 150 #endif