Debian Codegraph @

include/deal.II/base/bounding_box.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2017 - 2025 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_base_bounding_box_h
16 #define dealii_base_bounding_box_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/exceptions.h>
22 #include <deal.II/base/point.h>
23
24 #include <limits>
25
26 DEAL_II_NAMESPACE_OPEN
27
28 /**
29 * The enumerator NeighborType describes the neighboring relation between
30 * two bounding boxes.
31 */
32 enum class NeighborType
33 {
34 /**
35 * Not neighbors: the intersection is empty.
36 */
37 not_neighbors = 0,
38
39 /**
40 * Simple neighbors: the boxes intersect with an intersection of dimension at
41 * most `spacedim - 2`. For example, in 2d this means that the two rectangles
42 * touch at a single point, which must then be a vertex of each box. In 3d,
43 * this means that two boxes touch along an edge.
44 */
45 simple_neighbors = 1,
46
47 /**
48 * Attached neighbors: neighbors with an intersection of
49 * `dimension > spacedim - 2`. For example, in 2d this means that the two
50 * rectangles touch along (parts of) their edges. In 3d, it would mean that
51 * two boxes touch along (parts of) their faces.
52 */
53 attached_neighbors = 2,
54
55 /**
56 * Mergeable neighbors: neighbors which can be expressed with a single
57 * BoundingBox, e.g.
58 * @code
59 * .--V--W .-----V
60 * | | | = | |
61 * V--W--. V-----.
62 * @endcode
63 * or one is inside the other. This is a special case of `attached_neighbors`
64 * where the two bounding boxes touch along the entirety of their respective
65 * faces, or where they overlap in suitable ways.
66 */
67 mergeable_neighbors = 3
68 };
69
70 /**
71 * A class that represents a box of arbitrary dimension <tt>spacedim</tt> and
72 * with sides parallel to the coordinate axes, that is, a region
73 * @f[
74 * [x_0^L, x_0^U] \times ... \times [x_{spacedim-1}^L, x_{spacedim-1}^U],
75 * @f]
76 * where $(x_0^L , ..., x_{spacedim-1}^L)$ and $(x_0^U , ..., x_{spacedim-1}^U)$
77 * denote the two vertices (bottom left and top right) which are used to
78 * represent the box. The quantities $x_k^L$ and $x_k^U$ denote the "lower"
79 * and "upper" bounds of values that are within the box for each coordinate
80 * direction $k$.
81 *
82 * Geometrically, a bounding box is thus:
83 * - 1d: a segment (represented by its vertices in the proper order)
84 * - 2d: a rectangle (represented by the vertices V at bottom left, top right)
85 * @code
86 * .--------V
87 * | |
88 * V--------.
89 * @endcode
90 *
91 * - 3d: a cuboid (in which case the two vertices V follow the convention and
92 * are not owned by the same face)
93 * @code
94 * .------V
95 * / /|
96 * .------. |
97 * | | /
98 * | |/
99 * V------.
100 * @endcode
101 *
102 * Bounding boxes are, for example, useful in parallel distributed meshes to
103 * give a general description of the owners of each portion of the mesh. More
104 * generally, bounding boxes are often used to roughly describe a region of
105 * space in which an object is contained; if a candidate point is not within
106 * the bounding box (a test that is cheap to execute), then it is not necessary
107 * to perform an expensive test whether the candidate point is in fact inside
108 * the object itself. Bounding boxes are therefore often used as a first,
109 * cheap rejection test before more detailed checks. As such, bounding boxes
110 * serve many of the same purposes as the
111 * [convex hull](https://en.wikipedia.org/wiki/Convex_hull), for which it is
112 * also relatively straightforward to compute whether a point is inside or
113 * outside, though not quite as cheap as for the bounding box.
114 *
115 * Taking the cross section of a BoundingBox<spacedim> orthogonal to a given
116 * direction gives a box in one dimension lower: BoundingBox<spacedim - 1>.
117 * In 3d, the 2 coordinates of the cross section of BoundingBox<3> can be
118 * ordered in 2 different ways. That is, if we take the cross section orthogonal
119 * to the y direction we could either order a 3d-coordinate into a
120 * 2d-coordinate as $(x,z)$ or as $(z,x)$. This class uses the second
121 * convention, corresponding to the coordinates being ordered cyclicly
122 * $x \rightarrow y \rightarrow z \rightarrow x \rightarrow ... $
123 * To be precise, if we take a cross section:
124 *
125 * | Orthogonal to | Cross section coordinates ordered as |
126 * |:-------------:|:------------------------------------:|
127 * | x | (y, z) |
128 * | y | (z, x) |
129 * | z | (x, y) |
130 *
131 * This is according to the convention set by the function
132 * <code>coordinate_to_one_dim_higher</code>.
133 */
134 template <int spacedim, typename Number = double>
135 class BoundingBox
136 {
137 public:
138 /**
139 * Provide a way to get the dimension of an object without explicit
140 * knowledge of it's data type.
141 */
142 static constexpr unsigned int dimension = spacedim;
143
144 /**
145 * Standard constructor. Creates an object that corresponds to an empty box,
146 * i.e. a degenerate box with both points being the origin.
147 */
148 BoundingBox() = default;
149
150 /**
151 * Standard copy constructor operator.
152 */
153 BoundingBox(const BoundingBox<spacedim, Number> &box) = default;
154
155 /**
156 * Standard copy assignment operator.
157 */
158 BoundingBox<spacedim, Number> &
159 operator=(const BoundingBox<spacedim, Number> &t) = default;
160
161 /**
162 * Standard constructor for an empty box around a point @p point.
163 */
164 BoundingBox(const Point<spacedim, Number> &point);
165
166 /**
167 * Standard constructor for non-empty boxes: it uses a pair of points
168 * which describe the box: one for the bottom and one for the top
169 * corner.
170 */
171 BoundingBox(const std::pair<Point<spacedim, Number>, Point<spacedim, Number>>
172 &boundary_points);
173
174 /**
175 * Construct the bounding box that encloses all the points in the given
176 * container.
177 *
178 * The constructor supports any Container that provides begin() and end()
179 * iterators to Point<spacedim, Number> elements.
180 */
181 template <class Container>
182 BoundingBox(const Container &points);
183
184 /**
185 * Return a reference to the boundary_points
186 */
187 std::pair<Point<spacedim, Number>, Point<spacedim, Number>> &
188 get_boundary_points();
189
190 /**
191 * Return a const reference to the boundary_points
192 */
193 const std::pair<Point<spacedim, Number>, Point<spacedim, Number>> &
194 get_boundary_points() const;
195
196 /**
197 * Test for equality.
198 */
199 bool
200 operator==(const BoundingBox<spacedim, Number> &box) const;
201
202 /**
203 * Test for inequality.
204 */
205 bool
206 operator!=(const BoundingBox<spacedim, Number> &box) const;
207
208 /**
209 * Check if the current object and @p other_bbox are neighbors, i.e. if the boxes
210 * have dimension spacedim, check if their intersection is non empty.
211 */
212 bool
213 has_overlap_with(
214 const BoundingBox<spacedim, Number> &other_bbox,
215 const double tolerance = std::numeric_limits<Number>::epsilon()) const;
216
217 /**
218 * Check which NeighborType @p other_bbox is to the current object.
219 */
220 NeighborType
221 get_neighbor_type(
222 const BoundingBox<spacedim, Number> &other_bbox,
223 const double tolerance = std::numeric_limits<Number>::epsilon()) const;
224
225 /**
226 * Enlarge the current object so that it contains @p other_bbox .
227 * If the current object already contains @p other_bbox then it is not changed
228 * by this function.
229 */
230 void
231 merge_with(const BoundingBox<spacedim, Number> &other_bbox);
232
233 /**
234 * Return true if the point is inside the Bounding Box, false otherwise. The
235 * parameter @p tolerance is a factor by which the bounding box is enlarged
236 * relative to the dimensions of the bounding box in order to determine in a
237 * numerically robust way whether the point is inside.
238 */
239 bool
240 point_inside(
241 const Point<spacedim, Number> &p,
242 const double tolerance = std::numeric_limits<Number>::epsilon()) const;
243
244 /**
245 * Increase (or decrease) the size of the bounding box by the given amount.
246 * After calling this method, the lower left corner of the bounding box will
247 * have each coordinate decreased by @p amount, and the upper right corner
248 * of the bounding box will have each coordinate increased by @p amount.
249 *
250 * If you call this method with a negative number, and one of the axes of the
251 * original bounding box is smaller than amount/2, the method will trigger
252 * an assertion.
253 */
254 void
255 extend(const Number amount);
256
257 /**
258 * The same as above with the difference that a new BoundingBox instance is
259 * created without changing the current object.
260 */
261 BoundingBox<spacedim, Number>
262 create_extended(const Number amount) const;
263
264 /**
265 * Increase (or decrease) each side of the bounding box by the given
266 * @p relative_amount.
267 *
268 * After calling this method, the lower left corner of the bounding box will
269 * have each coordinate decreased by @p relative_amount * side_length(direction),
270 * and the upper right corner of the bounding box will have each coordinate
271 * increased by @p relative_amount * side_length(direction).
272 *
273 * If you call this method with a negative number, and one of the axes of the
274 * original bounding box is smaller than relative_amount *
275 * side_length(direction) / 2, the method will trigger an assertion.
276 */
277 BoundingBox<spacedim, Number>
278 create_extended_relative(const Number relative_amount) const;
279
280 /**
281 * Compute the volume (i.e. the dim-dimensional measure) of the BoundingBox.
282 */
283 double
284 volume() const;
285
286 /**
287 * Returns the point in the center of the box.
288 */
289 Point<spacedim, Number>
290 center() const;
291
292 /**
293 * Returns the side length of the box in @p direction.
294 */
295 Number
296 side_length(const unsigned int direction) const;
297
298 /**
299 * Return the lower bound of the box in @p direction.
300 */
301 Number
302 lower_bound(const unsigned int direction) const;
303
304 /**
305 * Return the upper bound of the box in @p direction.
306 */
307 Number
308 upper_bound(const unsigned int direction) const;
309
310 /**
311 * Return the bounds of the box in @p direction, as a one-dimensional box.
312 */
313 BoundingBox<1, Number>
314 bounds(const unsigned int direction) const;
315
316 /**
317 * Returns the indexth vertex of the box. Vertex is meant in the same way as
318 * for a cell, so that @p index $\in [0, 2^{\text{dim}} - 1]$.
319 */
320 Point<spacedim, Number>
321 vertex(const unsigned int index) const;
322
323 /**
324 * Returns the indexth child of the box. Child is meant in the same way as for
325 * a cell.
326 */
327 BoundingBox<spacedim, Number>
328 child(const unsigned int index) const;
329
330 /**
331 * Returns the cross section of the box orthogonal to @p direction.
332 * This is a box in one dimension lower.
333 *
334 * @note Calling this method in 1d will result in an exception since
335 * <code>BoundingBox&lt;0&gt;</code> is not implemented.
336 */
337 BoundingBox<spacedim - 1, Number>
338 cross_section(const unsigned int direction) const;
339
340 /**
341 * Apply the affine transformation that transforms this BoundingBox to a unit
342 * BoundingBox object.
343 *
344 * If $B$ is this bounding box, and $\hat{B}$ is the unit bounding box,
345 * compute the affine mapping that satisfies $G(B) = \hat{B}$ and apply it to
346 * @p point.
347 */
348 Point<spacedim, Number>
349 real_to_unit(const Point<spacedim, Number> &point) const;
350
351 /**
352 * Apply the affine transformation that transforms the unit BoundingBox object
353 * to this object.
354 *
355 * If $B$ is this bounding box, and $\hat{B}$ is the unit bounding box,
356 * compute the affine mapping that satisfies $F(\hat{B}) = B$ and apply it to
357 * @p point.
358 */
359 Point<spacedim, Number>
360 unit_to_real(const Point<spacedim, Number> &point) const;
361 /**
362 * Returns the signed distance from a @p point orthogonal to the bounds of the
363 * box in @p direction. The signed distance is negative for points inside the
364 * interval described by the bounds of the rectangle in the respective
365 * direction, zero for points on the interval boundary and positive for points
366 * outside.
367 */
368 Number
369 signed_distance(const Point<spacedim, Number> &point,
370 const unsigned int direction) const;
371
372 /**
373 * Returns the signed distance from a @p point to the bounds of the box. The
374 * signed distance is negative for points inside the rectangle, zero for
375 * points on the rectangle and positive for points outside the rectangle.
376 */
377 Number
378 signed_distance(const Point<spacedim, Number> &point) const;
379
380 /**
381 * Write or read the data of this object to or from a stream for the
382 * purpose of serialization using the [BOOST serialization
383 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
384 */
385 template <class Archive>
386 void
387 serialize(Archive &ar, const unsigned int version);
388
389 private:
390 std::pair<Point<spacedim, Number>, Point<spacedim, Number>> boundary_points;
391 };
392
393 /**
394 * Specialization of BoundingBox for spacedim 0. This class exists to enable
395 * dimension-independent programming but unconditionally throws an exception
396 * in its constructor.
397 */
398 template <typename Number>
399 class BoundingBox<0, Number>
400 {
401 public:
402 /**
403 * Default constructor. Throws an exception.
404 */
405 BoundingBox();
406
407 /**
408 * Equivalent two-point constructor. Throws an exception.
409 */
410 BoundingBox(const std::pair<Point<0, Number>, Point<0, Number>> &);
411
412 /**
413 * Equivalent container constructor. Throws an exception.
414 */
415 template <class Container>
416 BoundingBox(const Container &);
417 };
418
419
420 /**
421 * Returns the unit box $[0,1]^\text{dim}$.
422 *
423 * @relates BoundingBox
424 */
425 template <int dim, typename Number = double>
426 BoundingBox<dim, Number>
427 create_unit_bounding_box();
428
429
430 namespace internal
431 {
432 /**
433 * This function defines a convention for how coordinates in dim
434 * dimensions should translate to the coordinates in dim + 1 dimensions,
435 * when one of the coordinates in dim + 1 dimensions is locked to a given
436 * value.
437 *
438 * The convention is the following: Starting from the locked coordinate we
439 * store the lower dimensional coordinates consecutively and wrap around
440 * when going over the dimension. This relationship is, in 2d,
441 *
442 * | locked in 2D | 1d coordinate | 2d coordinate |
443 * |:------------:|:-------------:|:-------------:|
444 * | x0 | (a) | (x0, a) |
445 * | x1 | (a) | (a , x1) |
446 *
447 * and, in 3d,
448 *
449 * | locked in 3D | 2d coordinates | 3d coordinates |
450 * |:-------------|:--------------:|:--------------:|
451 * | x0 | (a, b) | (x0, a, b) |
452 * | x1 | (a, b) | ( b, x1, a) |
453 * | x2 | (a, b) | ( a, b, x2) |
454 *
455 * Given a locked coordinate, this function maps a coordinate index in dim
456 * dimension to a coordinate index in dim + 1 dimensions.
457 *
458 * @param locked_coordinate should be in the range [0, dim+1).
459 * @param coordinate_in_dim should be in the range [0, dim).
460 * @return A coordinate index in the range [0, dim+1)
461 *
462 * @relates BoundingBox
463 */
464 template <int dim>
465 inline int
466 coordinate_to_one_dim_higher(const int locked_coordinate,
467 const int coordinate_in_dim)
468 {
469 AssertIndexRange(locked_coordinate, dim + 1);
470 AssertIndexRange(coordinate_in_dim, dim);
471 return (locked_coordinate + coordinate_in_dim + 1) % (dim + 1);
472 }
473
474 } // namespace internal
475
476 /*------------------------ Inline functions: BoundingBox --------------------*/
477
478 #ifndef DOXYGEN
479
480
481 template <int spacedim, typename Number>
482 inline BoundingBox<spacedim, Number>::BoundingBox(
483 const Point<spacedim, Number> &p)
484 : BoundingBox({p, p})
485 {}
486
487
488
489 template <int spacedim, typename Number>
490 inline BoundingBox<spacedim, Number>::BoundingBox(
491 const std::pair<Point<spacedim, Number>, Point<spacedim, Number>>
492 &boundary_points)
493 {
494 // We check the Bounding Box is not degenerate
495 for (unsigned int i = 0; i < spacedim; ++i)
496 Assert(boundary_points.first[i] <= boundary_points.second[i],
497 ExcMessage("Bounding Box can't be created: the points' "
498 "order should be bottom left, top right!"));
499
500 this->boundary_points = boundary_points;
501 }
502
503
504
505 template <int spacedim, typename Number>
506 template <class Container>
507 inline BoundingBox<spacedim, Number>::BoundingBox(const Container &points)
508 {
509 // Use the default constructor in case points is empty instead of setting
510 // things to +oo and -oo
511 if (points.size() > 0)
512 {
513 auto &min = boundary_points.first;
514 auto &max = boundary_points.second;
515 for (unsigned int d = 0; d < spacedim; ++d)
516 {
517 min[d] = std::numeric_limits<Number>::infinity();
518 max[d] = -std::numeric_limits<Number>::infinity();
519 }
520
521 for (const Point<spacedim, Number> &point : points)
522 for (unsigned int d = 0; d < spacedim; ++d)
523 {
524 min[d] = std::min(min[d], point[d]);
525 max[d] = std::max(max[d], point[d]);
526 }
527 }
528 }
529
530
531
532 template <int spacedim, typename Number>
533 inline std::pair<Point<spacedim, Number>, Point<spacedim, Number>> &
534 BoundingBox<spacedim, Number>::get_boundary_points()
535 {
536 return this->boundary_points;
537 }
538
539
540
541 template <int spacedim, typename Number>
542 inline const std::pair<Point<spacedim, Number>, Point<spacedim, Number>> &
543 BoundingBox<spacedim, Number>::get_boundary_points() const
544 {
545 return this->boundary_points;
546 }
547
548
549
550 template <int spacedim, typename Number>
551 inline bool
552 BoundingBox<spacedim, Number>::operator==(
553 const BoundingBox<spacedim, Number> &box) const
554 {
555 return boundary_points == box.boundary_points;
556 }
557
558
559
560 template <int spacedim, typename Number>
561 inline bool
562 BoundingBox<spacedim, Number>::operator!=(
563 const BoundingBox<spacedim, Number> &box) const
564 {
565 return boundary_points != box.boundary_points;
566 }
567
568
569
570 template <int spacedim, typename Number>
571 inline void
572 BoundingBox<spacedim, Number>::extend(const Number amount)
573 {
574 for (unsigned int d = 0; d < spacedim; ++d)
575 {
576 boundary_points.first[d] -= amount;
577 boundary_points.second[d] += amount;
578 Assert(boundary_points.first[d] <= boundary_points.second[d],
579 ExcMessage("Bounding Box can't be shrunk this much: the points' "
580 "order should remain bottom left, top right."));
581 }
582 }
583
584
585
586 template <int spacedim, typename Number>
587 inline BoundingBox<spacedim, Number>
588 BoundingBox<spacedim, Number>::create_extended(const Number amount) const
589 {
590 // create and modify copy
591 auto bb = *this;
592 bb.extend(amount);
593
594 return bb;
595 }
596
597
598
599 template <int spacedim, typename Number>
600 inline BoundingBox<spacedim, Number>
601 BoundingBox<spacedim, Number>::create_extended_relative(
602 const Number relative_amount) const
603 {
604 // create and modify copy
605 auto bb = *this;
606
607 for (unsigned int d = 0; d < spacedim; ++d)
608 {
609 bb.boundary_points.first[d] -= relative_amount * side_length(d);
610 bb.boundary_points.second[d] += relative_amount * side_length(d);
611 Assert(bb.boundary_points.first[d] <= bb.boundary_points.second[d],
612 ExcMessage("Bounding Box can't be shrunk this much: the points' "
613 "order should remain bottom left, top right."));
614 }
615
616 return bb;
617 }
618
619
620
621 template <int spacedim, typename Number>
622 template <class Archive>
623 void
624 BoundingBox<spacedim, Number>::serialize(Archive &ar,
625 const unsigned int /*version*/)
626 {
627 // Avoid including boost/serialization/utility.hpp by unpacking the pair
628 // ourselves
629 ar &boundary_points.first;
630 ar &boundary_points.second;
631 }
632
633
634
635 template <typename Number>
636 inline BoundingBox<0, Number>::BoundingBox()
637 {
638 AssertThrow(false, ExcImpossibleInDim(0));
639 }
640
641
642
643 template <typename Number>
644 inline BoundingBox<0, Number>::BoundingBox(
645 const std::pair<Point<0, Number>, Point<0, Number>> &)
646 {
647 AssertThrow(false, ExcImpossibleInDim(0));
648 }
649
650
651
652 template <typename Number>
653 template <class Container>
654 inline BoundingBox<0, Number>::BoundingBox(const Container &)
655 {
656 AssertThrow(false, ExcImpossibleInDim(0));
657 }
658
659
660
661 #endif // DOXYGEN
662 DEAL_II_NAMESPACE_CLOSE
663
664 #endif