Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2025 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 290 : class BoundingBox : public std::pair<Point, Point>
41 : {
42 : public:
43 :
44 3845788 : BoundingBox (const Point & new_min,
45 3845788 : const Point & new_max) :
46 3845788 : std::pair<Point, Point>(new_min, new_max)
47 3845788 : {}
48 :
49 60083 : BoundingBox (const std::pair<Point, Point> & bbox) :
50 60083 : std::pair<Point, Point> (bbox)
51 5562 : {}
52 :
53 : /**
54 : * Default constructor sets invalid bounds.
55 : */
56 2344553 : BoundingBox ()
57 38224 : {
58 38224 : this->invalidate();
59 2344553 : }
60 :
61 : /**
62 : * Sets the bounding box to be "inverted". This is a useful
63 : * starting point for future \p union_with operations.
64 : */
65 38224 : void invalidate ()
66 : {
67 9531008 : for (unsigned int i=0; i<LIBMESH_DIM; i++)
68 : {
69 7148256 : this->first(i) = std::numeric_limits<Real>::max();
70 7148256 : this->second(i) = -std::numeric_limits<Real>::max();
71 : }
72 38224 : }
73 :
74 : /**
75 : * \returns A point at the minimum x,y,z coordinates of the box.
76 : */
77 9 : const Point & min() const
78 9 : { return this->first; }
79 :
80 2760958 : Point & min()
81 2764546 : { return this->first; }
82 :
83 : /**
84 : * \returns A point at the maximum x,y,z coordinates of the box.
85 : */
86 9 : const Point & max() const
87 9 : { return this->second; }
88 :
89 2760958 : Point & max()
90 2764546 : { return this->second; }
91 :
92 : /**
93 : * \returns \p true if the other bounding box is contained in this
94 : * bounding box. Exact floating point <= comparisons are performed.
95 : */
96 : bool contains (const BoundingBox &) const;
97 :
98 : /**
99 : * \returns \p true if the other bounding box has a non-empty
100 : * intersection with this bounding box. Exact floating point <=
101 : * comparisons are performed.
102 : */
103 : bool intersects (const BoundingBox &) const;
104 :
105 : /**
106 : * \returns \p true if the other bounding box has a non-empty
107 : * intersection with this bounding box. abstol is an absolute
108 : * tolerance used to make "fuzzy" comparisons. abstol must be
109 : * strictly > 0.0, and both BBoxes being compared are "inflated" by
110 : * abstol in each direction, i.e.
111 : * (xmin, ymin, zmin) -> (xmin - abstol, ymin - abstol, zmin - abstol)
112 : * (xmax, ymax, zmax) -> (xmax + abstol, ymax + abstol, zmax + abstol)
113 : * before the intersection comparisons are made. This approach can
114 : * be helpful for detecting intersections between two degenerate
115 : * (planar) bounding boxes that lie in nearly (to within abstol) the
116 : * same plane and in certain situations should be considered
117 : * intersecting.
118 : */
119 : bool intersects (const BoundingBox &, Real abstol) const;
120 :
121 : /**
122 : * \returns \p true if the bounding box contains the given point.
123 : */
124 : bool contains_point (const Point &) const;
125 :
126 : /**
127 : * \returns \p true if the bounding box contains the given point,
128 : * to within at least one of the given tolerance(s). At least one
129 : * tolerance should be set to greater than zero; otherwise use the
130 : * other \p contains_point overload for efficiency.
131 : *
132 : * Relative tolerances are computed relative to the maximum finite
133 : * extent of the bounding box, \p max_size()
134 : */
135 : bool contains_point (const Point & p, Real abs_tol, Real rel_tol) const;
136 :
137 : /**
138 : * Sets this bounding box to be the intersection with the other
139 : * bounding box.
140 : */
141 : void intersect_with (const BoundingBox &);
142 :
143 : /**
144 : * Enlarges this bounding box to include the given point
145 : */
146 : void union_with (const Point & p);
147 :
148 : /**
149 : * Sets this bounding box to be the union with the other
150 : * bounding box.
151 : */
152 : void union_with (const BoundingBox &);
153 :
154 : /**
155 : * Computes the signed distance, d, from a given Point p to this
156 : * BoundingBox. The sign convention is:
157 : * d > 0 if the point is outside the BoundingBox
158 : * d <= 0 if the point is inside the Bounding Box
159 : */
160 : Real signed_distance(const Point & p) const;
161 :
162 : /**
163 : * Scales each dimension of the bounding box by \p factor.
164 : *
165 : * Has no effect for dimensions in which either
166 : * min(dim) == std::numeric_limits<Real>::max() or
167 : * max(dim) == -std::numeric_limits<Real>::max(),
168 : * which is the "invalid" state set by the default
169 : * constructor and by invalidate().
170 : */
171 : void scale(const Real factor);
172 :
173 : /**
174 : * Returns the maximum size of a finite box extent.
175 : *
176 : * If the bounding box is infinite (or effectively so, e.g. using
177 : * numeric_limits<Real>::max()) in some dimension, then that
178 : * dimension is ignored.
179 : */
180 : Real max_size() const;
181 :
182 : /**
183 : * Formatted print, by default to \p libMesh::out.
184 : */
185 : void print(std::ostream & os = libMesh::out) const;
186 :
187 : /**
188 : * Formatted print as above but supports the syntax:
189 : *
190 : * \code
191 : * BoundingBox b;
192 : * std::cout << b << std::endl;
193 : * \endcode
194 : */
195 1 : friend std::ostream & operator << (std::ostream & os, const BoundingBox & b)
196 : {
197 12 : b.print(os);
198 1 : return os;
199 : }
200 : };
201 :
202 :
203 :
204 : // ------------------------------------------------------------
205 : // BoundingBox class member functions
206 :
207 : inline
208 : bool
209 138 : BoundingBox::contains(const BoundingBox & other_box) const
210 : {
211 4 : const libMesh::Point & my_lower = this->first;
212 4 : const libMesh::Point & my_upper = this->second;
213 :
214 4 : const libMesh::Point & other_lower = other_box.first;
215 4 : const libMesh::Point & other_upper = other_box.second;
216 :
217 568 : for (unsigned int dir=0; dir<LIBMESH_DIM; ++dir)
218 438 : if (my_lower(dir) > other_lower(dir) ||
219 426 : other_upper(dir) > my_upper(dir))
220 0 : return false;
221 :
222 4 : return true;
223 : }
224 :
225 :
226 :
227 : // BoundingBox::intersects() is about 30% faster when inlined, so its definition
228 : // is here instead of in the source file.
229 : inline
230 : bool
231 7677519 : BoundingBox::intersects(const BoundingBox & other_box) const
232 : {
233 224540 : const libMesh::Point & my_lower = this->first;
234 224540 : const libMesh::Point & my_upper = this->second;
235 :
236 224540 : const libMesh::Point & other_lower = other_box.first;
237 224540 : const libMesh::Point & other_upper = other_box.second;
238 :
239 : // Since boxes are tensor products of line intervals it suffices to check
240 : // that the line segments for each coordinate axis overlap.
241 18127945 : for (unsigned int dir=0; dir<LIBMESH_DIM; ++dir)
242 : {
243 : // Line segments can intersect in two ways:
244 : // 1. They can overlap.
245 : // 2. One can be inside the other.
246 : //
247 : // In the first case we want to see if either end point of the second
248 : // line segment lies within the first. In the second case we can simply
249 : // check that one end point of the first line segment lies in the second
250 : // line segment. Note that we don't need, in the second case, to do two
251 : // checks since that case is already covered by the first.
252 34348262 : if (!((my_lower(dir) <= other_lower(dir) &&
253 11907024 : other_lower(dir) <= my_upper(dir)) ||
254 6992545 : (my_lower(dir) <= other_upper(dir) &&
255 23308510 : other_upper(dir) <= my_upper(dir))) &&
256 2931351 : !((other_lower(dir) <= my_lower(dir) &&
257 81682 : my_lower(dir) <= other_upper(dir))))
258 : {
259 167244 : return false;
260 : }
261 : }
262 :
263 57296 : return true;
264 : }
265 :
266 : inline
267 : bool
268 : BoundingBox::intersects(const BoundingBox & other_box,
269 : Real abstol) const
270 : {
271 : // If you want to use abstol==0, you need to call the "exact"
272 : // comparison version of the intersects() function.
273 : libmesh_assert(abstol > 0.);
274 :
275 : BoundingBox expanded_my_box = *this;
276 : for (unsigned int dir=0; dir<LIBMESH_DIM; ++dir)
277 : {
278 : expanded_my_box.first(dir) -= abstol;
279 : expanded_my_box.second(dir) += abstol;
280 : }
281 : return expanded_my_box.intersects(other_box);
282 : }
283 :
284 : inline
285 : void
286 4708319 : BoundingBox::union_with(const Point & p)
287 : {
288 20689200 : for (unsigned int i=0; i<LIBMESH_DIM; i++)
289 : {
290 15516900 : min()(i) = std::min(min()(i), p(i));
291 15516900 : max()(i) = std::max(max()(i), p(i));
292 : }
293 4708319 : }
294 :
295 : } // namespace libMesh
296 :
297 :
298 : #endif // LIBMESH_BOUNDING_BOX_H
|
