Reference documentation for deal.II version 9.1.1
\(\newcommand{\dealcoloneq}{\mathrel{\vcenter{:}}=}\)
bounding_box.cc
1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 2017 - 2019 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15 #include <deal.II/base/bounding_box.h>
16 
17 DEAL_II_NAMESPACE_OPEN
18 
19 template <int spacedim, typename Number>
20 bool
22  const Point<spacedim, Number> &p) const
23 {
24  for (unsigned int i = 0; i < spacedim; ++i)
25  {
26  // Bottom left-top right convention: the point is outside if it's smaller
27  // than the first or bigger than the second boundary point The bounding
28  // box is defined as a closed set
29  if (std::numeric_limits<Number>::epsilon() *
30  (std::abs(this->boundary_points.first[i] + p[i])) <
31  this->boundary_points.first[i] - p[i] ||
32  std::numeric_limits<Number>::epsilon() *
33  (std::abs(this->boundary_points.second[i] + p[i])) <
34  p[i] - this->boundary_points.second[i])
35  return false;
36  }
37  return true;
38 }
39 
40 template <int spacedim, typename Number>
41 void
43  const BoundingBox<spacedim, Number> &other_bbox)
44 {
45  for (unsigned int i = 0; i < spacedim; ++i)
46  {
47  this->boundary_points.first[i] =
48  std::min(this->boundary_points.first[i],
49  other_bbox.boundary_points.first[i]);
50  this->boundary_points.second[i] =
51  std::max(this->boundary_points.second[i],
52  other_bbox.boundary_points.second[i]);
53  }
54 }
55 
56 template <int spacedim, typename Number>
57 NeighborType
59  const BoundingBox<spacedim, Number> &other_bbox) const
60 {
61  if (spacedim == 1)
62  {
63  // In dimension 1 if the two bounding box are neighbors
64  // we can merge them
65  if (this->point_inside(other_bbox.boundary_points.first) ||
66  this->point_inside(other_bbox.boundary_points.second))
67  return NeighborType::mergeable_neighbors;
68  return NeighborType::not_neighbors;
69  }
70  else
71  {
72  std::vector<Point<spacedim, Number>> bbox1;
73  bbox1.push_back(this->get_boundary_points().first);
74  bbox1.push_back(this->get_boundary_points().second);
75  std::vector<Point<spacedim, Number>> bbox2;
76  bbox2.push_back(other_bbox.get_boundary_points().first);
77  bbox2.push_back(other_bbox.get_boundary_points().second);
78 
79  // Step 1: testing if the boxes are close enough to intersect
80  for (unsigned int d = 0; d < spacedim; ++d)
81  if (bbox1[0][d] * (1 - std::numeric_limits<Number>::epsilon()) >
82  bbox2[1][d] ||
83  bbox2[0][d] * (1 - std::numeric_limits<Number>::epsilon()) >
84  bbox1[1][d])
85  return NeighborType::not_neighbors;
86 
87  // The boxes intersect: we need to understand now how they intersect.
88  // We begin by computing the intersection:
89  std::vector<double> intersect_bbox_min;
90  std::vector<double> intersect_bbox_max;
91  for (unsigned int d = 0; d < spacedim; ++d)
92  {
93  intersect_bbox_min.push_back(std::max(bbox1[0][d], bbox2[0][d]));
94  intersect_bbox_max.push_back(std::min(bbox1[1][d], bbox2[1][d]));
95  }
96 
97  // Finding the intersection's dimension
98 
99  unsigned int intersect_dim = spacedim;
100  for (unsigned int d = 0; d < spacedim; ++d)
101  if (std::abs(intersect_bbox_min[d] - intersect_bbox_max[d]) <=
102  std::numeric_limits<Number>::epsilon() *
103  (std::abs(intersect_bbox_min[d]) +
104  std::abs(intersect_bbox_max[d])))
105  --intersect_dim;
106 
107  if (intersect_dim == 0 || intersect_dim + 2 == spacedim)
108  return NeighborType::simple_neighbors;
109 
110  // Checking the two mergeable cases: first if the boxes are aligned so
111  // that they can be merged
112  unsigned int not_align_1 = 0, not_align_2 = 0;
113  bool same_direction = true;
114  for (unsigned int d = 0; d < spacedim; ++d)
115  {
116  if (std::abs(bbox2[0][d] - bbox1[0][d]) >
117  std::numeric_limits<double>::epsilon() *
118  (std::abs(bbox2[0][d]) + std::abs(bbox1[0][d])))
119  ++not_align_1;
120  if (std::abs(bbox1[1][d] - bbox2[1][d]) >
121  std::numeric_limits<double>::epsilon() *
122  (std::abs(bbox1[1][d]) + std::abs(bbox2[1][d])))
123  ++not_align_2;
124  if (not_align_1 != not_align_2)
125  {
126  same_direction = false;
127  break;
128  }
129  }
130 
131  if (not_align_1 <= 1 && not_align_2 <= 1 && same_direction)
132  return NeighborType::mergeable_neighbors;
133 
134  // Second: one box is contained/equal to the other
135  if ((this->point_inside(bbox2[0]) && this->point_inside(bbox2[1])) ||
136  (other_bbox.point_inside(bbox1[0]) &&
137  other_bbox.point_inside(bbox1[1])))
138  return NeighborType::mergeable_neighbors;
139 
140  // Degenerate and mergeable cases have been found, it remains:
141  return NeighborType::attached_neighbors;
142  }
143 }
144 
145 
146 
147 template <int spacedim, typename Number>
148 std::pair<Point<spacedim, Number>, Point<spacedim, Number>> &
150 {
151  return this->boundary_points;
152 }
153 
154 
155 
156 template <int spacedim, typename Number>
157 const std::pair<Point<spacedim, Number>, Point<spacedim, Number>> &
159 {
160  return this->boundary_points;
161 }
162 
163 
164 
165 template <int spacedim, typename Number>
166 double
168 {
169  double vol = 1.0;
170  for (unsigned int i = 0; i < spacedim; ++i)
171  vol *= (this->boundary_points.second[i] - this->boundary_points.first[i]);
172  return vol;
173 }
174 
175 #include "bounding_box.inst"
176 DEAL_II_NAMESPACE_CLOSE
void merge_with(const BoundingBox< spacedim, Number > &other_bbox)
Definition: bounding_box.cc:42
Definition: point.h:110
NeighborType get_neighbor_type(const BoundingBox< spacedim, Number > &other_bbox) const
Definition: bounding_box.cc:58
bool point_inside(const Point< spacedim, Number > &p) const
Definition: bounding_box.cc:21
std::pair< Point< spacedim, Number >, Point< spacedim, Number > > & get_boundary_points()
double volume() const