Flow123d  master-ad1076ca0
bounding_box.hh
Go to the documentation of this file.
1 /*!
2  *
3  * Copyright (C) 2015 Technical University of Liberec. All rights reserved.
4  *
5  * This program is free software; you can redistribute it and/or modify it under
6  * the terms of the GNU General Public License version 3 as published by the
7  * Free Software Foundation. (http://www.gnu.org/licenses/gpl-3.0.en.html)
8  *
9  * This program is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12  *
13  *
14  * @file bounding_box.hh
15  * @brief
16  */
17 
18 #ifndef BOX_ELEMENT_HH_
19 #define BOX_ELEMENT_HH_
20 
21 #include <string.h> // for memcpy
22 #include <algorithm> // for max, min
23 
24 
25 #include <new> // for operator new[]
26 #include <ostream> // for operator<<
27 #include <string> // for basic_string
28 #include <vector> // for vector
29 #include <armadillo>
30 #include "mesh/point.hh" // for Space, Space<>...
31 #include "system/exc_common.hh" // for ExcAssertMsg
32 #include "system/exceptions.hh" // for ExcStream, ope...
33 #include "system/global_defs.h" // for msg, rank, ss
34 
35 using namespace std;
36 
37 /**
38  * @brief Bounding box in 3d ambient space.
39  *
40  * Primary intention is usage in BIHTree and various speedups of non-compatible
41  * intersections.
42  *
43  * Copy constructor and assignment are default provided by compiler.
44  * These can be used to set bounds latter on without particular method
45  * to this end:
46  *
47  * @code
48  * BoundingBox box; // non-initialized box
49  * box=BoundingBox( arma::vec3("0 1 2"), arma::vec3("4 5 6") );
50  * @endcode
51  *
52  * Don;t worry about performance, all is inlined.
53  */
54 class BoundingBox {
55 public:
56  TYPEDEF_ERR_INFO( EI_split_point, double);
57  TYPEDEF_ERR_INFO( EI_interval_left, double);
58  TYPEDEF_ERR_INFO( EI_interval_right, double);
59  DECLARE_EXCEPTION(ExcSplitting, << "Split point " << EI_split_point::val
60  << "out of bounds: <" << EI_interval_left::val
61  << ", " << EI_interval_right::val << ">\n");
62 
63  /// Currently we set dimension to 3.
64  static const unsigned int dimension = 3;
65  /// stabilization parameter
66  static const double epsilon;
67  /// Currently we assume
69 
70 
71  /**
72  * Default constructor.
73  * No initialization of vertices. Be very careful using this.
74  * One necessary usage is vector of BoundigBox.
75  */
77  {
78  // set undefined vertices
79  min_vertex_.fill( std::numeric_limits<double>::signaling_NaN() );
80  max_vertex_.fill( std::numeric_limits<double>::signaling_NaN() );
81  }
82 
83  /**
84  * Constructor for point box.
85  */
86  BoundingBox(const Point &min)
87  : min_vertex_(min), max_vertex_(min)
88  {};
89 
90  /**
91  * Constructor.
92  *
93  * From given minimal and maximal vertex.
94  */
95  BoundingBox(const Point &min, const Point &max)
96  : min_vertex_(min), max_vertex_(max)
97  {
98  ASSERT( arma::min( min <= max ) ).error("Wrong coordinates in constructor.");
99  };
100 
101  /**
102  * Constructor.
103  *
104  * Make bounding box for set of points.
105  */
106  BoundingBox(const vector<Point> &points);
107 
108  /**
109  * Set maximum in given axis.
110  */
111  void set_max(unsigned int axis, double max) {
112  ASSERT_LT( axis , dimension);
113  ASSERT_LE( min(axis) , max);
114  max_vertex_[axis] = max;
115  }
116 
117  /**
118  * Set minimum on given axis.
119  */
120  void set_min(unsigned int axis, double min) {
121  ASSERT_LT(axis, dimension);
122  ASSERT_LE(min , max(axis));
123  min_vertex_[axis] = min;
124  }
125 
126  /**
127  * Return minimal vertex of the bounding box.
128  */
129  const Point &min() const {
130  return min_vertex_;
131  }
132 
133  /**
134  * Return maximal vertex of the bounding box.
135  */
136  const Point &max() const {
137  return max_vertex_;
138  }
139 
140  /**
141  * Return minimal value on given axis.
142  */
143  double min(unsigned int axis) const {
144  return min()[axis];
145  }
146 
147  /**
148  * Return maximal value on given axis.
149  */
150  double max(unsigned int axis) const {
151  return max()[axis];
152  }
153 
154 
155  /**
156  * Return size of the box in given axis.
157  */
158  double size(unsigned int axis) const {
159  return max()[axis] - min()[axis];
160  }
161 
162 
163  /**
164  * Return center of the bounding box.
165  */
166  Point center() const {
167  return (max_vertex_ + min_vertex_) / 2.0;
168  }
169 
170  /**
171  * Return center of projection of the bounding box to given @p axis.
172  * Axis coding is: 0 - axis x, 1 - axis y, 2 - axis z.
173  */
174  double projection_center(unsigned int axis) const {
175  ASSERT_LT(axis, dimension);
176  return (max_vertex_[axis] + min_vertex_[axis])/2;
177  }
178 
179  /**
180  * Returns true is the box element contains @p point
181  *
182  * @param point Testing point
183  * @return True if box element contains point
184  */
185  bool contains_point(const Point &point) const
186  {
187  for (unsigned int i=0; i<dimension; i++) {
188  if ((point(i) + epsilon < min_vertex_(i)) ||
189  (point(i) > epsilon + max_vertex_(i))) return false;
190  }
191  return true;
192  }
193 
194  /**
195  * Returns true if two bounding boxes have intersection.
196  *
197  * This serves as an estimate of intersection of elements.
198  * To make it safe (do not exclude possible intersection) for
199  * 1d and 2d elements aligned with axes, we use some tolerance.
200  * Since this tolerance is fixed, there could be problem with
201  * highly refined meshes (get false positive result).
202  */
203  bool intersect(const BoundingBox &b2) const
204  {
205  for (unsigned int i=0; i<dimension; i++) {
206  if ( (min_vertex_(i) > b2.max_vertex_(i) + epsilon) ||
207  (b2.min_vertex_(i) > max_vertex_(i) + epsilon ) ) return false;
208  }
209  return true;
210  }
211 
212  /**
213  * Returns true if projection of the box to @p axis is an interval
214  * less then (with tolerance) to given @p value.
215  */
216  bool projection_lt(unsigned int axis, double value) const
217  {
218  return max_vertex_(axis) + epsilon < value;
219  }
220 
221  /**
222  * Returns true if projection of the box to @p axis is an interval
223  * greater then (with tolerance) to given @p value.
224  */
225  bool projection_gt(unsigned int axis, double value) const
226  {
227  return min_vertex_(axis) - epsilon > value;
228  }
229 
230  /**
231  * Split box into two boxes along @p axis by the
232  * plane going through @p splitting_point on the axis.
233  */
234  void split(unsigned int axis, double splitting_point,
235  BoundingBox &left, BoundingBox &right ) const
236  {
237  ASSERT_LT(axis , dimension);
238  if (min_vertex_[axis] <= splitting_point && splitting_point <= max_vertex_[axis] ) {
239  left = *this;
240  right = *this;
241  left.max_vertex_[axis] = splitting_point;
242  right.min_vertex_[axis] = splitting_point;
243  } else {
244  THROW( ExcSplitting() << EI_interval_left(min_vertex_[axis])
245  << EI_interval_right(max_vertex_[axis])
246  << EI_split_point(splitting_point) );
247  }
248  }
249 
250  /**
251  * Expand bounding box to contain also given @p point.
252  */
253  void expand(const Point &point) {
254  for(unsigned int j=0; j<dimension; j++) {
255  // parameters of min and max functions must be in correct order, vertices can be set to NaN (see default constructor)
256  min_vertex_(j) = std::min( point[j], min_vertex_[j] );
257  max_vertex_(j) = std::max( point[j], max_vertex_[j] );
258  }
259  }
260 
261  /**
262  * Expand bounding box to contain also given @p box.
263  */
264  void expand(const BoundingBox &box) {
265  for(unsigned int j=0; j<dimension; j++) {
266  // parameters of min and max functions must be in correct order, vertices can be set to NaN (see default constructor)
267  min_vertex_[j] = std::min( box.min_vertex_[j], min_vertex_[j] );
268  max_vertex_[j] = std::max( box.max_vertex_[j], max_vertex_[j] );
269  }
270  }
271 
272  /**
273  * Return index of the axis in which the box has longest projection.
274  */
275  unsigned char longest_axis() const {
276  auto diff=max_vertex_ - min_vertex_;
277  return (diff[1] > diff[0])
278  ? ( diff[2] > diff[1] ? 2 : 1 )
279  : ( diff[2] > diff[0] ? 2 : 0 );
280  }
281 
282  /**
283  * Project point to bounding box.
284  *
285  * If point is in bounding box, returns its.
286  */
287  Point project_point(const Point &point) const {
288  Point projected_point;
289  for (unsigned int i=0; i<dimension; ++i) {
290  if ( projection_gt(i, point[i]) ) projected_point[i] = min_vertex_(i);
291  else if ( projection_lt(i, point[i]) ) projected_point[i] = max_vertex_(i);
292  else projected_point[i] = point[i];
293  }
294 
295  return projected_point;
296  }
297 
298  /**
299  * Return size of the axis in which the box has longest projection.
300  */
301  inline double longest_size() const {
302  return size( longest_axis() );
303  }
304 
305 
306 private:
307  /// minimal coordinates of bounding box
309  /// maximal coordinates of bounding box
311 };
312 
313 /// Overloads output operator for box.
314 inline ostream &operator<<(ostream &stream, const BoundingBox &box) {
315  stream << "Box("
316  << box.min(0) << " "
317  << box.min(1) << " "
318  << box.min(2) << "; "
319  << box.max(0) << " "
320  << box.max(1) << " "
321  << box.max(2) << ")";
322  return stream;
323 }
324 
325 #endif /* BOX_ELEMENT_HH_ */
LimitSide::right
@ right
BoundingBox::set_max
void set_max(unsigned int axis, double max)
Definition: bounding_box.hh:111
BoundingBox::projection_gt
bool projection_gt(unsigned int axis, double value) const
Definition: bounding_box.hh:225
BoundingBox::expand
void expand(const Point &point)
Definition: bounding_box.hh:253
ASSERT
#define ASSERT(expr)
Definition: asserts.hh:350
string.h
BoundingBox::longest_axis
unsigned char longest_axis() const
Definition: bounding_box.hh:275
point.hh
BoundingBox::Point
Space< dimension >::Point Point
Currently we assume.
Definition: bounding_box.hh:68
BoundingBox::projection_center
double projection_center(unsigned int axis) const
Definition: bounding_box.hh:174
value
static constexpr bool value
Definition: json.hpp:87
BoundingBox::max_vertex_
Point max_vertex_
maximal coordinates of bounding box
Definition: bounding_box.hh:310
THROW
#define THROW(whole_exception_expr)
Wrapper for throw. Saves the throwing point.
Definition: exceptions.hh:53
BoundingBox::size
double size(unsigned int axis) const
Definition: bounding_box.hh:158
std::vector
Definition: doxy_dummy_defs.hh:7
operator<<
ostream & operator<<(ostream &stream, const BoundingBox &box)
Overloads output operator for box.
Definition: bounding_box.hh:314
exceptions.hh
ASSERT_LT
#define ASSERT_LT(a, b)
Definition of comparative assert macro (Less Than) only for debug mode.
Definition: asserts.hh:300
BoundingBox
Bounding box in 3d ambient space.
Definition: bounding_box.hh:54
BoundingBox::epsilon
static const double epsilon
stabilization parameter
Definition: bounding_box.hh:66
Space
Definition: point.hh:40
BoundingBox::contains_point
bool contains_point(const Point &point) const
Definition: bounding_box.hh:185
LimitSide::left
@ left
BoundingBox::min_vertex_
Point min_vertex_
minimal coordinates of bounding box
Definition: bounding_box.hh:308
BoundingBox::intersect
bool intersect(const BoundingBox &b2) const
Definition: bounding_box.hh:203
BoundingBox::expand
void expand(const BoundingBox &box)
Definition: bounding_box.hh:264
BoundingBox::BoundingBox
BoundingBox()
Definition: bounding_box.hh:76
BoundingBox::split
void split(unsigned int axis, double splitting_point, BoundingBox &left, BoundingBox &right) const
Definition: bounding_box.hh:234
BoundingBox::BoundingBox
BoundingBox(const Point &min, const Point &max)
Definition: bounding_box.hh:95
BoundingBox::center
Point center() const
Definition: bounding_box.hh:166
BoundingBox::set_min
void set_min(unsigned int axis, double min)
Definition: bounding_box.hh:120
exc_common.hh
TYPEDEF_ERR_INFO
#define TYPEDEF_ERR_INFO(EI_Type, Type)
Macro to simplify declaration of error_info types.
Definition: exceptions.hh:194
BoundingBox::longest_size
double longest_size() const
Definition: bounding_box.hh:301
global_defs.h
Global macros to enhance readability and debugging, general constants.
BoundingBox::projection_lt
bool projection_lt(unsigned int axis, double value) const
Definition: bounding_box.hh:216
std
Definition: doxy_dummy_defs.hh:5
ASSERT_LE
#define ASSERT_LE(a, b)
Definition of comparative assert macro (Less or Equal) only for debug mode.
Definition: asserts.hh:308
BoundingBox::max
const Point & max() const
Definition: bounding_box.hh:136
BoundingBox::BoundingBox
BoundingBox(const Point &min)
Definition: bounding_box.hh:86
BoundingBox::max
double max(unsigned int axis) const
Definition: bounding_box.hh:150
DECLARE_EXCEPTION
#define DECLARE_EXCEPTION(ExcName, Format)
Macro for simple definition of exceptions.
Definition: exceptions.hh:158
BoundingBox::project_point
Point project_point(const Point &point) const
Definition: bounding_box.hh:287
BoundingBox::min
const Point & min() const
Definition: bounding_box.hh:129
BoundingBox::min
double min(unsigned int axis) const
Definition: bounding_box.hh:143