1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2020 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License, or (at your option) any later version.
8
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // Lesser General Public License for more details.
13
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this library; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
18
19
20 #ifndef LIBMESH_BOUNDING_BOX_H
21 #define LIBMESH_BOUNDING_BOX_H
22
23 // Local Includes
24 #include "libmesh/libmesh.h"
25 #include "libmesh/point.h" // some compilers want the full definition - I think so they can do
26 // return-value-optimization for BoundingBox'es - BSK
27
28 // C++ Includes
29 #include <vector>
30 #include <set>
31 #include <limits>
32
33 namespace libMesh
34 {
35
36 /**
37 * Defines a Cartesian bounding box by the two
38 * corner extremum.
39 */
40 class BoundingBox : public std::pair<Point, Point>
41 {
42 public:
43
BoundingBox(const Point & new_min,const Point & new_max)44 BoundingBox (const Point & new_min,
45 const Point & new_max) :
46 std::pair<Point, Point>(new_min, new_max)
47 {}
48
BoundingBox(const std::pair<Point,Point> & bbox)49 BoundingBox (const std::pair<Point, Point> & bbox) :
50 std::pair<Point, Point> (bbox)
51 {}
52
53 /**
54 * Default constructor sets invalid bounds.
55 */
BoundingBox()56 BoundingBox ()
57 {
58 this->invalidate();
59 }
60
61 /**
62 * Sets the bounding box to encompass the universe.
63 */
invalidate()64 void invalidate ()
65 {
66 for (unsigned int i=0; i<LIBMESH_DIM; i++)
67 {
68 this->first(i) = std::numeric_limits<Real>::max();
69 this->second(i) = -std::numeric_limits<Real>::max();
70 }
71 }
72
73 /**
74 * \returns A point at the minimum x,y,z coordinates of the box.
75 */
min()76 const Point & min() const
77 { return this->first; }
78
min()79 Point & min()
80 { return this->first; }
81
82 /**
83 * \returns A point at the maximum x,y,z coordinates of the box.
84 */
max()85 const Point & max() const
86 { return this->second; }
87
max()88 Point & max()
89 { return this->second; }
90
91 /**
92 * \returns \p true if the other bounding box has a non-empty
93 * intersection with this bounding box. Exact floating point <=
94 * comparisons are performed.
95 */
96 bool intersects (const BoundingBox &) const;
97
98 /**
99 * \returns \p true if the other bounding box has a non-empty
100 * intersection with this bounding box. abstol is an absolute
101 * tolerance used to make "fuzzy" comparisons. abstol must be
102 * strictly > 0.0, and both BBoxes being compared are "inflated" by
103 * abstol in each direction, i.e.
104 * (xmin, ymin, zmin) -> (xmin - abstol, ymin - abstol, zmin - abstol)
105 * (xmax, ymax, zmax) -> (xmax + abstol, ymax + abstol, zmax + abstol)
106 * before the intersection comparisons are made. This approach can
107 * be helpful for detecting intersections between two degenerate
108 * (planar) bounding boxes that lie in nearly (to within abstol) the
109 * same plane and in certain situations should be considered
110 * intersecting.
111 */
112 bool intersects (const BoundingBox &, Real abstol) const;
113
114 /**
115 * \returns \p true if the bounding box contains the given point.
116 */
117 bool contains_point (const Point &) const;
118
119 /**
120 * Sets this bounding box to be the intersection with the other
121 * bounding box.
122 */
123 void intersect_with (const BoundingBox &);
124
125 /**
126 * Enlarges this bounding box to include the given point
127 */
128 void union_with (const Point & p);
129
130 /**
131 * Sets this bounding box to be the union with the other
132 * bounding box.
133 */
134 void union_with (const BoundingBox &);
135
136 /**
137 * Computes the signed distance, d, from a given Point p to this
138 * BoundingBox. The sign convention is:
139 * d > 0 if the point is outside the BoundingBox
140 * d <= 0 if the point is inside the Bounding Box
141 */
142 Real signed_distance(const Point & p) const;
143 };
144
145
146
147 // ------------------------------------------------------------
148 // BoundingBox class member functions
149
150 // BoundingBox::intersects() is about 30% faster when inlined, so its definition
151 // is here instead of in the source file.
152 inline
153 bool
intersects(const BoundingBox & other_box)154 BoundingBox::intersects(const BoundingBox & other_box) const
155 {
156 const libMesh::Point & my_lower = this->first;
157 const libMesh::Point & my_upper = this->second;
158
159 const libMesh::Point & other_lower = other_box.first;
160 const libMesh::Point & other_upper = other_box.second;
161
162 // Since boxes are tensor products of line intervals it suffices to check
163 // that the line segments for each coordinate axis overlap.
164 for (unsigned int dir=0; dir<LIBMESH_DIM; ++dir)
165 {
166 // Line segments can intersect in two ways:
167 // 1. They can overlap.
168 // 2. One can be inside the other.
169 //
170 // In the first case we want to see if either end point of the second
171 // line segment lies within the first. In the second case we can simply
172 // check that one end point of the first line segment lies in the second
173 // line segment. Note that we don't need, in the second case, to do two
174 // checks since that case is already covered by the first.
175 if (!((my_lower(dir) <= other_lower(dir) &&
176 other_lower(dir) <= my_upper(dir)) ||
177 (my_lower(dir) <= other_upper(dir) &&
178 other_upper(dir) <= my_upper(dir))) &&
179 !((other_lower(dir) <= my_lower(dir) &&
180 my_lower(dir) <= other_upper(dir))))
181 {
182 return false;
183 }
184 }
185
186 return true;
187 }
188
189 inline
190 bool
intersects(const BoundingBox & other_box,Real abstol)191 BoundingBox::intersects(const BoundingBox & other_box,
192 Real abstol) const
193 {
194 // If you want to use abstol==0, you need to call the "exact"
195 // comparison version of the intersects() function.
196 libmesh_assert(abstol > 0.);
197
198 BoundingBox expanded_my_box = *this;
199 for (unsigned int dir=0; dir<LIBMESH_DIM; ++dir)
200 {
201 expanded_my_box.first(dir) -= abstol;
202 expanded_my_box.second(dir) += abstol;
203 }
204 return expanded_my_box.intersects(other_box);
205 }
206
207 inline
208 void
union_with(const Point & p)209 BoundingBox::union_with(const Point & p)
210 {
211 for (unsigned int i=0; i<LIBMESH_DIM; i++)
212 {
213 min()(i) = std::min(min()(i), p(i));
214 max()(i) = std::max(max()(i), p(i));
215 }
216 }
217
218 } // namespace libMesh
219
220
221 #endif // LIBMESH_BOUNDING_BOX_H
222