Debian Codegraph @

include/deal.II/grid/grid_tools_topology.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2023 - 2024 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_grid_tools_topology_h
16 #define dealii_grid_tools_topology_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/point.h>
21 #include <deal.II/base/template_constraints.h>
22
23 #include <deal.II/grid/tria.h>
24 #include <deal.II/grid/tria_description.h>
25
26 #include <deal.II/lac/dynamic_sparsity_pattern.h>
27
28 #include <list>
29 #include <map>
30 #include <set>
31 #include <tuple>
32 #include <utility>
33 #include <vector>
34
35 DEAL_II_NAMESPACE_OPEN
36
37 namespace GridTools
38 {
39 /**
40 * @name Querying or modifying topological information
41 */
42 /** @{ */
43 /**
44 * Return the arrays that define the coarse mesh of a Triangulation. This
45 * function is the inverse of Triangulation::create_triangulation() in the
46 * sense that if one called this function on a triangulation, then that
47 * triangulation could be recreated by some kind of refinement from the
48 * results of this function.
49 *
50 * The return value is a tuple with the vector of vertices, the vector of
51 * cells, and a SubCellData structure. The latter contains additional
52 * information about faces and lines. These three objects are exactly
53 * the arguments to Triangulation::create_triangulation().
54 *
55 * This function is useful in cases where one needs to deconstruct a
56 * Triangulation or manipulate the numbering of the vertices in some way: an
57 * example is GridGenerator::merge_triangulations().
58 */
59 template <int dim, int spacedim>
60 std::
61 tuple<std::vector<Point<spacedim>>, std::vector<CellData<dim>>, SubCellData>
62 get_coarse_mesh_description(const Triangulation<dim, spacedim> &tria);
63
64 /**
65 * Remove vertices that are not referenced by any of the cells. This
66 * function is called by all <tt>GridIn::read_*</tt> functions to eliminate
67 * vertices that are listed in the input files but are not used by the cells
68 * in the input file. While these vertices should not be in the input from
69 * the beginning, they sometimes are, most often when some cells have been
70 * removed by hand without wanting to update the vertex lists, as they might
71 * be lengthy.
72 *
73 * This function is called by all <tt>GridIn::read_*</tt> functions as the
74 * triangulation class requires them to be called with used vertices only.
75 * This is so, since the vertices are copied verbatim by that class, so we
76 * have to eliminate unused vertices beforehand.
77 *
78 * Not implemented for the codimension one case.
79 */
80 template <int dim, int spacedim>
81 void
82 delete_unused_vertices(std::vector<Point<spacedim>> &vertices,
83 std::vector<CellData<dim>> &cells,
84 SubCellData &subcelldata);
85
86 /**
87 * Remove vertices that are duplicated, due to the input of a structured
88 * grid, for example. If these vertices are not removed, the faces bounded
89 * by these vertices become part of the boundary, even if they are in the
90 * interior of the mesh.
91 *
92 * This function is called by some <tt>GridIn::read_*</tt> functions. Only
93 * the vertices with indices in @p considered_vertices are tested for
94 * equality. This speeds up the algorithm, which is, for worst-case hyper
95 * cube geometries $O(N^{3/2})$ in 2d and $O(N^{5/3})$ in 3d: quite slow.
96 * However, if you wish to consider all vertices, simply pass an empty
97 * vector. In that case, the function fills @p considered_vertices with all
98 * vertices.
99 *
100 * Two vertices are considered equal if their difference in each coordinate
101 * direction is less than @p tol. This implies that nothing happens if
102 * the tolerance is set to zero.
103 */
104 template <int dim, int spacedim>
105 void
106 delete_duplicated_vertices(std::vector<Point<spacedim>> &all_vertices,
107 std::vector<CellData<dim>> &cells,
108 SubCellData &subcelldata,
109 std::vector<unsigned int> &considered_vertices,
110 const double tol = 1e-12);
111
112 /**
113 * Remove vertices that are duplicated.
114 *
115 * Two vertices are considered equal if their difference in each coordinate
116 * direction is less than @p tol. This implies that nothing happens if
117 * the tolerance is set to zero.
118 */
119 template <int dim>
120 void
121 delete_duplicated_vertices(std::vector<Point<dim>> &vertices,
122 const double tol = 1e-12);
123
124 /**
125 * Grids generated by grid generators may have an orientation of cells which
126 * is the inverse of the orientation required by deal.II.
127 *
128 * In 2d and 3d this function checks whether all cells have negative or
129 * positive measure/volume. In the former case, all cells are inverted. It
130 * does nothing in 1d.
131 *
132 * The inversion of cells might also work when only a subset of all cells
133 * have negative volume. However, grids consisting of a mixture of negative
134 * and positively oriented cells are very likely to be broken. Therefore, an
135 * exception is thrown, in case cells are not uniformly oriented.
136 *
137 * @note This function should be called before GridTools::consistently_order_cells().
138 *
139 * @param all_vertices The vertices of the mesh.
140 * @param cells The array of CellData objects that describe the mesh's topology.
141 */
142 template <int dim, int spacedim>
143 void
144 invert_all_negative_measure_cells(
145 const std::vector<Point<spacedim>> &all_vertices,
146 std::vector<CellData<dim>> &cells);
147
148 /**
149 * Check the given cells and inverts any cell that is considered to have
150 * negative measure/volume in the orientation required by deal.II.
151 *
152 * This function is identical to invert_all_negative_measure_cells() except it
153 * does not throw an error if only some of the cells are inverted. Instead,
154 * this function returns how many cells were inverted. Additionally, it will
155 * always throw an exception outside of codimension 0.
156 */
157 template <int dim, int spacedim>
158 std::size_t
159 invert_cells_with_negative_measure(
160 const std::vector<Point<spacedim>> &all_vertices,
161 std::vector<CellData<dim>> &cells);
162
163 /**
164 * Given a vector of CellData objects describing a mesh, reorder their
165 * vertices so that all lines are consistently oriented.
166 *
167 * The expectations on orientation and a discussion of this function are
168 * available in the
169 * @ref reordering "reordering topic".
170 *
171 * @param cells The array of CellData objects that describe the mesh's topology.
172 * @ingroup reordering
173 */
174 template <int dim>
175 void
176 consistently_order_cells(std::vector<CellData<dim>> &cells);
177
178 /**
179 * Return a std::map with all vertices of faces located in the boundary
180 *
181 * @param[in] tria The Triangulation object.
182 */
183 template <int dim, int spacedim>
184 std::map<unsigned int, Point<spacedim>>
185 get_all_vertices_at_boundary(const Triangulation<dim, spacedim> &tria);
186
187 /**
188 * Return a std::vector that contains a map for each closed boundary.
189 * Each closed boundary is described by a std:vector of pairs
190 * `vertex index , Point<spacedim>`.
191 *
192 * The vertices are in counter-clockwise ordering for the outer boundary.
193 * The vertices are in clockwise ordering for inner boundaries (holes).
194 *
195 * It is generally not guaranteed that the first entry of the vector is the
196 * outer boundary. However, when cell 0 is located on the outer boundary this
197 * is the case.
198 *
199 * The mapping argument enables the use of e.g. MappingQEulerian.
200 *
201 * @param[in] tria The Triangulation object.
202 * @param[in] mapping The mapping used to map the vertices of the cell
203 */
204 template <int dim, int spacedim>
205 std::vector<std::vector<std::pair<unsigned int, Point<spacedim>>>>
206 extract_ordered_boundary_vertices(
207 const Triangulation<dim, spacedim> &tria,
208 const Mapping<dim, spacedim> &mapping =
209 (ReferenceCells::get_hypercube<dim>()
210 #ifndef _MSC_VER
211 .template get_default_linear_mapping<dim, spacedim>()
212 #else
213 .ReferenceCell::get_default_linear_mapping<dim, spacedim>()
214 #endif
215 ));
216
217 /**
218 * Remove hanging nodes from a grid. If the @p isotropic parameter is set
219 * to @p false (default) this function detects cells with hanging nodes and
220 * refines the neighbours in the direction that removes hanging nodes.
221 * If the @p isotropic parameter is set
222 * to @p true, the neighbours refinement is made in each directions.
223 * In order to remove all hanging nodes this procedure has to be repeated:
224 * this could require a large number of iterations.
225 * To avoid this a max number (@p max_iterations) of iteration is provided.
226 *
227 * Consider the following grid:
228 * @image html remove_hanging_nodes-hanging.png
229 *
230 * @p isotropic == @p false would return:
231 * @image html remove_hanging_nodes-aniso.png
232 *
233 * @p isotropic == @p true would return:
234 * @image html remove_hanging_nodes-isotro.png
235 *
236 * @param[in,out] tria Triangulation to refine.
237 *
238 * @param[in] isotropic If true refine cells in each directions, otherwise
239 * (default value) refine the cell in the direction that removes hanging node.
240 *
241 * @param[in] max_iterations At each step only closest cells to hanging nodes
242 * are refined. The code may require a lot of iterations to remove all
243 * hanging nodes. @p max_iterations is the maximum number of iteration
244 * allowed. If @p max_iterations == numbers::invalid_unsigned_int this
245 * function continues refining until there are no hanging nodes.
246 *
247 * @note In the case of parallel codes, this function should be combined
248 * with GridGenerator::flatten_triangulation.
249 */
250 template <int dim, int spacedim>
251 void
252 remove_hanging_nodes(Triangulation<dim, spacedim> &tria,
253 const bool isotropic = false,
254 const unsigned int max_iterations = 100);
255
256 /**
257 * Refine a mesh anisotropically such that the resulting mesh is composed by
258 * cells with maximum ratio between dimensions less than @p max_ratio.
259 * This procedure requires an algorithm that may not terminate. Consequently,
260 * it is possible to set a maximum number of iterations through the
261 * @p max_iterations parameter.
262 *
263 * Starting from a cell like this:
264 * @image html remove_anisotropy-coarse.png
265 *
266 * This function would return:
267 * @image html remove_anisotropy-refined.png
268 *
269 * @param[in,out] tria Triangulation to refine.
270 *
271 * @param[in] max_ratio Maximum value allowed among the ratio between
272 * the dimensions of each cell.
273 *
274 * @param[in] max_iterations Maximum number of iterations allowed.
275 *
276 * @note In the case of parallel codes, this function should be combined
277 * with GridGenerator::flatten_triangulation and
278 * GridTools::remove_hanging_nodes.
279 */
280 template <int dim, int spacedim>
281 void
282 remove_anisotropy(Triangulation<dim, spacedim> &tria,
283 const double max_ratio = 1.6180339887,
284 const unsigned int max_iterations = 5);
285
286 /**
287 * Return a map `vertex index -> Point<spacedim>` containing the used
288 * vertices of the given `container`. The key of the returned map (i.e.,
289 * the first element of the pair above) is the global index in the
290 * triangulation, whereas the value of each pair is the physical
291 * location of the corresponding vertex. The used vertices are obtained by
292 * looping over all cells,
293 * and querying for each cell where its vertices are through the (optional)
294 * `mapping` argument.
295 *
296 * In serial Triangulation objects and parallel::shared::Triangulation
297 * objects, the size of the returned map
298 * equals Triangulation::n_used_vertices() (not Triangulation::n_vertices()).
299 * Note that in parallel::distributed::Triangulation objects, only vertices in
300 * locally owned cells and ghost cells are returned, as for all other vertices
301 * their real location might not be known (e.g. for distributed computations
302 * using MappingQEulerian).
303 *
304 * If you use the default `mapping`, the returned map satisfies the following
305 * equality:
306 *
307 * @code
308 * const auto used_vertices = extract_used_vertices(tria);
309 * auto all_vertices = tria.get_vertices();
310 *
311 * for(const auto &id_and_v : used_vertices)
312 * all_vertices[id_and_v.first] == id_and_v.second; // true
313 * @endcode
314 *
315 * Notice that the above is not satisfied for mappings that change the
316 * location of vertices, like MappingQEulerian.
317 *
318 * @ref ConceptMeshType "MeshType concept".
319 * @param container The container to extract vertices from.
320 * @param mapping The mapping to use to compute the points locations.
321 */
322 template <int dim, int spacedim>
323 std::map<unsigned int, Point<spacedim>>
324 extract_used_vertices(
325 const Triangulation<dim, spacedim> &container,
326 const Mapping<dim, spacedim> &mapping =
327 (ReferenceCells::get_hypercube<dim>()
328 #ifndef _MSC_VER
329 .template get_default_linear_mapping<dim, spacedim>()
330 #else
331 .ReferenceCell::get_default_linear_mapping<dim, spacedim>()
332 #endif
333 ));
334
335 /**
336 * Return the adjacent cells of all the vertices. If a vertex is also a
337 * hanging node, the associated coarse cell is also returned. The vertices
338 * are ordered by the vertex index. This is the number returned by the
339 * function <code>cell-@>vertex_index()</code>. Notice that only the indices
340 * marked in the array returned by
341 * Triangulation<dim,spacedim>::get_used_vertices() are used.
342 */
343 template <int dim, int spacedim>
344 std::vector<
345 std::set<typename Triangulation<dim, spacedim>::active_cell_iterator>>
346 vertex_to_cell_map(const Triangulation<dim, spacedim> &triangulation);
347
348 /**
349 * Produce a sparsity pattern in which nonzero entries indicate that two
350 * cells are connected via a common face. The diagonal entries of the
351 * sparsity pattern are also set.
352 *
353 * The rows and columns refer to the cells as they are traversed in their
354 * natural order using cell iterators.
355 */
356 template <int dim, int spacedim>
357 void
358 get_face_connectivity_of_cells(
359 const Triangulation<dim, spacedim> &triangulation,
360 DynamicSparsityPattern &connectivity);
361
362 /**
363 * Produce a sparsity pattern in which nonzero entries indicate that two
364 * cells are connected via a common vertex. The diagonal entries of the
365 * sparsity pattern are also set.
366 *
367 * The rows and columns refer to the cells as they are traversed in their
368 * natural order using cell iterators.
369 */
370 template <int dim, int spacedim>
371 void
372 get_vertex_connectivity_of_cells(
373 const Triangulation<dim, spacedim> &triangulation,
374 DynamicSparsityPattern &connectivity);
375
376 /**
377 * Produce a sparsity pattern for a given level mesh in which nonzero entries
378 * indicate that two cells are connected via a common vertex. The diagonal
379 * entries of the sparsity pattern are also set.
380 *
381 * The rows and columns refer to the cells as they are traversed in their
382 * natural order using cell iterators.
383 */
384 template <int dim, int spacedim>
385 void
386 get_vertex_connectivity_of_cells_on_level(
387 const Triangulation<dim, spacedim> &triangulation,
388 const unsigned int level,
389 DynamicSparsityPattern &connectivity);
390
391 /** @} */
392
393 /**
394 * @name Comparing different meshes
395 */
396 /** @{ */
397
398 /**
399 * Given two meshes (i.e. objects of type Triangulation or DoFHandler) that
400 * are based on the same coarse mesh, this function figures out a set of cells
401 * that are matched between the two meshes and where at most one of the meshes
402 * is more refined on this cell. In other words, it finds the smallest cells
403 * that are common to both meshes, and that together completely cover the
404 * domain.
405 *
406 * This function is useful, for example, in time-dependent or nonlinear
407 * application, where one has to integrate a solution defined on one mesh
408 * (e.g., the one from the previous time step or nonlinear iteration)
409 * against the shape functions of another mesh (the next time step, the next
410 * nonlinear iteration). If, for example, the new mesh is finer, then one
411 * has to obtain the solution on the coarse mesh (mesh_1) and interpolate it
412 * to the children of the corresponding cell of mesh_2. Conversely, if the
413 * new mesh is coarser, one has to express the coarse cell shape function by
414 * a linear combination of fine cell shape functions. In either case, one
415 * needs to loop over the finest cells that are common to both
416 * triangulations. This function returns a list of pairs of matching
417 * iterators to cells in the two meshes that can be used to this end.
418 *
419 * Note that the list of these iterators is not necessarily ordered, and
420 * does also not necessarily coincide with the order in which cells are
421 * traversed in one, or both, of the meshes given as arguments.
422 *
423 * @tparam MeshType A type that satisfies the requirements of the
424 * @ref ConceptMeshType "MeshType concept".
425 *
426 * @note This function can only be used with
427 * parallel::distributed::Triangulation when both meshes use the same
428 * Triangulation since, with a distributed Triangulation, not all cells are
429 * stored locally, so the resulting list may not cover the entire domain.
430 *
431 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
432 */
433 template <typename MeshType>
434 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
435 std::list<std::pair<
436 typename MeshType::cell_iterator,
437 typename MeshType::cell_iterator>> get_finest_common_cells(const MeshType
438 &mesh_1,
439 const MeshType
440 &mesh_2);
441
442 /**
443 * Return true if the two triangulations are based on the same coarse mesh.
444 * This is determined by checking whether they have the same number of cells
445 * on the coarsest level, and then checking that they have the same
446 * vertices.
447 *
448 * The two meshes may have different refinement histories beyond the coarse
449 * mesh.
450 */
451 template <int dim, int spacedim>
452 bool
453 have_same_coarse_mesh(const Triangulation<dim, spacedim> &mesh_1,
454 const Triangulation<dim, spacedim> &mesh_2);
455
456 /**
457 * The same function as above, but working on arguments of type DoFHandler.
458 * This function is provided to allow calling have_same_coarse_mesh for all
459 * types of containers representing triangulations or the classes built on
460 * triangulations.
461 *
462 * @tparam MeshType A type that satisfies the requirements of the
463 * @ref ConceptMeshType "MeshType concept".
464 *
465 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
466 */
467 template <typename MeshType>
468 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
469 bool have_same_coarse_mesh(const MeshType &mesh_1, const MeshType &mesh_2);
470
471 /** @} */
472
473 /**
474 * @name Exceptions
475 */
476 /** @{ */
477
478 /**
479 * An exception that is thrown whenever the edges of a mesh are not
480 * orientable.
481 *
482 * @ingroup Exceptions
483 */
484 DeclExceptionMsg(ExcMeshNotOrientable,
485 "The edges of the mesh are not consistently orientable.");
486
487 /** @} */
488 } // namespace GridTools
489
490 DEAL_II_NAMESPACE_CLOSE
491
492 #endif