Debian Codegraph @

include/deal.II/grid/grid_tools_geometry.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2023 - 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_grid_tools_geometry_h
16 #define dealii_grid_tools_geometry_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/bounding_box.h>
21 #include <deal.II/base/point.h>
22 #include <deal.II/base/template_constraints.h>
23 #include <deal.II/base/tensor.h>
24
25 #include <deal.II/fe/mapping.h>
26
27 #include <deal.II/grid/manifold.h>
28 #include <deal.II/grid/tria.h>
29
30 #include <algorithm>
31 #include <array>
32 #include <cmath>
33 #include <numeric>
34 #include <utility>
35 #include <vector>
36
37 DEAL_II_NAMESPACE_OPEN
38
39 namespace GridTools
40 {
41 /**
42 * @name Information about meshes and cells
43 */
44 /** @{ */
45
46 /**
47 * Return the diameter of a triangulation. The diameter is computed using
48 * only the vertices, i.e. if the diameter should be larger than the maximal
49 * distance between boundary vertices due to a higher order mapping, then
50 * this function will not catch this.
51 */
52 template <int dim, int spacedim>
53 double
54 diameter(const Triangulation<dim, spacedim> &tria);
55
56 /**
57 * Compute the volume (i.e. the dim-dimensional measure) of the
58 * triangulation. We compute the measure using the integral $\sum_K \int_K 1
59 * \; dx$ where $K$ are the cells of the given triangulation. The integral
60 * is approximated via quadrature. This version of the function uses a
61 * linear mapping to compute the JxW values on each cell.
62 *
63 * If the triangulation is a dim-dimensional one embedded in a higher
64 * dimensional space of dimension spacedim, then the value returned is the
65 * dim-dimensional measure. For example, for a two-dimensional triangulation
66 * in three-dimensional space, the value returned is the area of the surface
67 * so described. (This obviously makes sense since the spacedim-dimensional
68 * measure of a dim-dimensional triangulation would always be zero if dim @<
69 * spacedim).
70 *
71 * This function also works for objects of type
72 * parallel::distributed::Triangulation, in which case the function is a
73 * @ref GlossCollectiveOperation "collective operation".
74 *
75 * @param tria The triangulation.
76 * @return The dim-dimensional measure of the domain described by the
77 * triangulation, as discussed above.
78 */
79 template <int dim, int spacedim>
80 double
81 volume(const Triangulation<dim, spacedim> &tria);
82
83 /**
84 * Compute the volume (i.e. the dim-dimensional measure) of the
85 * triangulation. We compute the measure using the integral $\sum_K \int_K 1
86 * \; dx$ where $K$ are the cells of the given triangulation. The integral
87 * is approximated via quadrature for which we use the mapping argument.
88 *
89 * If the triangulation is a dim-dimensional one embedded in a higher
90 * dimensional space of dimension spacedim, then the value returned is the
91 * dim-dimensional measure. For example, for a two-dimensional triangulation
92 * in three-dimensional space, the value returned is the area of the surface
93 * so described. (This obviously makes sense since the spacedim-dimensional
94 * measure of a dim-dimensional triangulation would always be zero if dim @<
95 * spacedim.
96 *
97 * This function also works for objects of type
98 * parallel::distributed::Triangulation, in which case the function is a
99 * @ref GlossCollectiveOperation "collective operation".
100 *
101 * @param tria The triangulation.
102 * @param mapping The Mapping which computes the Jacobians used to
103 * approximate the volume via quadrature. Explicitly using a higher-order
104 * Mapping (i.e., instead of using the other version of this function) will
105 * result in a more accurate approximation of the volume on Triangulations
106 * with curvature described by Manifold objects.
107 * @return The dim-dimensional measure of the domain described by the
108 * triangulation, as discussed above.
109 */
110 template <int dim, int spacedim>
111 double
112 volume(const Triangulation<dim, spacedim> &tria,
113 const Mapping<dim, spacedim> &mapping);
114
115 /**
116 * Return an approximation of the diameter of the smallest active cell of a
117 * triangulation. See step-24 for an example of use of this function.
118 *
119 * Notice that, even if you pass a non-trivial mapping, the returned value is
120 * computed only using information on the vertices of the triangulation,
121 * possibly transformed by the mapping. While this is accurate most of the
122 * times, it may fail to give the correct result when the triangulation
123 * contains very distorted cells.
124 */
125 template <int dim, int spacedim>
126 double
127 minimal_cell_diameter(
128 const Triangulation<dim, spacedim> &triangulation,
129 const Mapping<dim, spacedim> &mapping =
130 (ReferenceCells::get_hypercube<dim>()
131 #ifndef _MSC_VER
132 .template get_default_linear_mapping<dim, spacedim>()
133 #else
134 .ReferenceCell::get_default_linear_mapping<dim, spacedim>()
135 #endif
136 ));
137
138 /**
139 * Return an approximation of the diameter of the largest active cell of a
140 * triangulation.
141 *
142 * Notice that, even if you pass a non-trivial mapping to this function, the
143 * returned value is computed only using information on the vertices of the
144 * triangulation, possibly transformed by the mapping. While this is accurate
145 * most of the times, it may fail to give the correct result when the
146 * triangulation contains very distorted cells.
147 */
148 template <int dim, int spacedim>
149 double
150 maximal_cell_diameter(
151 const Triangulation<dim, spacedim> &triangulation,
152 const Mapping<dim, spacedim> &mapping =
153 (ReferenceCells::get_hypercube<dim>()
154 #ifndef _MSC_VER
155 .template get_default_linear_mapping<dim, spacedim>()
156 #else
157 .ReferenceCell::get_default_linear_mapping<dim, spacedim>()
158 #endif
159 ));
160
161 /**
162 * Given a list of vertices (typically obtained using
163 * Triangulation::get_vertices()) as the first, and a list of vertex indices
164 * that characterize a single cell as the second argument, return the
165 * measure (area, volume) of this cell. If this is a real cell, then you can
166 * get the same result using <code>cell-@>measure()</code>, but this
167 * function also works for cells that do not exist except that you make it
168 * up by naming its vertices from the list.
169 *
170 * The size of @p vertex_indices, combined with `dim`, implicitly encodes
171 * the ReferenceCell type of the provided cell. For example, if `dim == 2` and
172 * `vertex_indices.size() == 3` then the cell is a triangle, but if
173 * `dim == 2` and `vertex_indices.size() == 4` then the cell is a
174 * quadrilateral. A std::vector is implicitly convertible to an ArrayView, so
175 * it can be passed directly to this function. See the ArrayView class for
176 * more information.
177 *
178 * @note This function is only implemented for codimension zero objects.
179 */
180 template <int dim>
181 double
182 cell_measure(const std::vector<Point<dim>> &all_vertices,
183 const ArrayView<const unsigned int> &vertex_indices);
184
185 /**
186 * Return the highest value among ratios between extents in each of the
187 * coordinate directions of a @p cell. Moreover, return the dimension
188 * relative to the highest elongation.
189 *
190 * @param[in] cell an iterator pointing to the cell.
191 *
192 * @return A std::pair<unsigned int, double> such that the @p first value
193 * is the dimension of the highest elongation and the @p second value is the
194 * ratio among the dimensions of the @p cell.
195 */
196 template <int dim, int spacedim>
197 std::pair<unsigned int, double>
198 get_longest_direction(
199 typename Triangulation<dim, spacedim>::active_cell_iterator cell);
200
201 /**
202 * This function computes an affine approximation of the map from the unit
203 * coordinates to the real coordinates of the form $p_\text{real} = A
204 * p_\text{unit} + b $ by a least squares fit of this affine function to the
205 * $2^\text{dim}$ vertices representing a quadrilateral or hexahedral cell
206 * in `spacedim` dimensions. The result is returned as a pair with the
207 * matrix <i>A</i> as the first argument and the vector <i>b</i> describing
208 * distance of the plane to the origin.
209 *
210 * For any valid mesh cell whose geometry is not degenerate, this operation
211 * results in a unique affine mapping, even in cases where the actual
212 * transformation by a bi-/trilinear or higher order mapping might be
213 * singular. The result is exact in case the transformation from the unit to
214 * the real cell is indeed affine, such as in one dimension or for Cartesian
215 * and affine (parallelogram) meshes in 2d/3d.
216 *
217 * This approximation is underlying the function
218 * TriaAccessor::real_to_unit_cell_affine_approximation() function.
219 *
220 * For exact transformations to the unit cell, use
221 * Mapping::transform_real_to_unit_cell().
222 */
223 template <int dim, int spacedim>
224 std::pair<DerivativeForm<1, dim, spacedim>, Tensor<1, spacedim>>
225 affine_cell_approximation(const ArrayView<const Point<spacedim>> &vertices);
226
227 /**
228 * Computes an aspect ratio measure for all locally-owned active cells and
229 * fills a vector with one entry per cell, given a @p triangulation and
230 * @p mapping. The size of the vector that is returned equals the number of
231 * active cells. The vector contains zero for non locally-owned cells. The
232 * aspect ratio of a cell is defined as the ratio of the maximum to minimum
233 * singular value of the Jacobian, taking the maximum over all quadrature
234 * points of a quadrature rule specified via @p quadrature. For example, for
235 * the special case of rectangular elements in 2d with dimensions $a$ and $b$
236 * ($a \geq b$), this function returns the usual aspect ratio definition
237 * $a/b$. The above definition using singular values is a generalization to
238 * arbitrarily deformed elements. This function is intended to be used for
239 * $d=2,3$ space dimensions, but it can also be used for $d=1$ returning a
240 * value of 1.
241 *
242 * @note Inverted elements do not throw an exception. Instead, a value of inf
243 * is written into the vector in case of inverted elements.
244 *
245 * @note Make sure to use enough quadrature points for a precise calculation
246 * of the aspect ratio in case of deformed elements.
247 *
248 * @note In parallel computations the return value will have the length
249 * n_active_cells but the aspect ratio is only computed for the cells that
250 * are locally owned and placed at index CellAccessor::active_cell_index(),
251 * respectively. All other values are set to 0.
252 *
253 * @note This function can only be used if deal.II was configured with
254 * support for LAPACK.
255 */
256 template <int dim>
257 Vector<double>
258 compute_aspect_ratio_of_cells(const Mapping<dim> &mapping,
259 const Triangulation<dim> &triangulation,
260 const Quadrature<dim> &quadrature);
261
262 /**
263 * Computes the maximum aspect ratio by taking the maximum over all cells.
264 *
265 * @note When running in parallel with a Triangulation that supports MPI,
266 * this is a collective call and the return value is the maximum over all
267 * processors.
268 */
269 template <int dim>
270 double
271 compute_maximum_aspect_ratio(const Mapping<dim> &mapping,
272 const Triangulation<dim> &triangulation,
273 const Quadrature<dim> &quadrature);
274
275 /**
276 * Compute the smallest box containing the entire triangulation.
277 *
278 * If the input triangulation is a `parallel::distributed::Triangulation`,
279 * then each processor will compute a bounding box enclosing all locally
280 * owned, ghost, and artificial cells. In the case of a domain without curved
281 * boundaries, these bounding boxes will all agree between processors because
282 * the union of the areas occupied by artificial and ghost cells equals the
283 * union of the areas occupied by the cells that other processors own.
284 * However, if the domain has curved boundaries, this is no longer the case.
285 * The bounding box returned may be appropriate for the current processor,
286 * but different from the bounding boxes computed on other processors.
287 */
288 template <int dim, int spacedim>
289 BoundingBox<spacedim>
290 compute_bounding_box(const Triangulation<dim, spacedim> &triangulation);
291
292 /**
293 * Compute and return a bounding box, defined through a pair of points
294 * bottom left and top right, that surrounds a subdomain of the @p mesh.
295 * Here, the "subdomain" consists of exactly all of those
296 * active cells for which the @p predicate returns @p true.
297 *
298 * For a description of how @p predicate works,
299 * see compute_active_cell_halo_layer().
300 *
301 * @note This function was written before the BoundingBox class was invented.
302 * Consequently, it returns a pair of points, rather than a BoundingBox
303 * object as one may expect. However, BoundingBox has a conversion constructor
304 * from pairs of points, so the result of this function can still be assigned
305 * to a BoundingBox object.
306 *
307 * @dealiiConceptRequires{concepts::is_triangulation_or_dof_handler<MeshType>}
308 */
309 template <typename MeshType>
310 DEAL_II_CXX20_REQUIRES(concepts::is_triangulation_or_dof_handler<MeshType>)
311 std::pair<
312 Point<MeshType::space_dimension>,
313 Point<MeshType::
314 space_dimension>> compute_bounding_box(const MeshType &mesh,
315 const std::function<bool(
316 const typename MeshType::
317 active_cell_iterator &)>
318 &predicate);
319
320 /**
321 * Return the point on the geometrical object @p object closest to the given
322 * point @p trial_point. For example, if @p object is a one-dimensional line
323 * or edge, then the returned point will be a point on the geodesic that
324 * connects the vertices as the manifold associated with the object sees it
325 * (i.e., the geometric line may be curved if it lives in a higher
326 * dimensional space). If the iterator points to a quadrilateral in a higher
327 * dimensional space, then the returned point lies within the convex hull of
328 * the vertices of the quad as seen by the associated manifold.
329 *
330 * @note This projection is usually not well-posed since there may be
331 * multiple points on the object that minimize the distance. The algorithm
332 * used in this function is robust (and the output is guaranteed to be on
333 * the given @p object) but may only provide a few correct digits if the
334 * object has high curvature. If your manifold supports it then the
335 * specialized function Manifold::project_to_manifold() may perform better.
336 */
337 template <typename Iterator>
338 Point<Iterator::AccessorType::space_dimension>
339 project_to_object(
340 const Iterator &object,
341 const Point<Iterator::AccessorType::space_dimension> &trial_point);
342 /** @} */
343 } // namespace GridTools
344
345 #ifndef DOXYGEN
346 namespace GridTools
347 {
348 namespace internal
349 {
350 namespace ProjectToObject
351 {
352 /**
353 * The method GridTools::project_to_object requires taking derivatives
354 * along the surface of a simplex. In general these cannot be
355 * approximated with finite differences but special differences of the
356 * form
357 *
358 * df/dx_i - df/dx_j
359 *
360 * <em>can</em> be approximated. This <code>struct</code> just stores
361 * the two derivatives approximated by the stencil (in the case of the
362 * example above <code>i</code> and <code>j</code>).
363 */
364 struct CrossDerivative
365 {
366 const unsigned int direction_0;
367 const unsigned int direction_1;
368
369 CrossDerivative(const unsigned int d0, const unsigned int d1);
370 };
371
372 inline CrossDerivative::CrossDerivative(const unsigned int d0,
373 const unsigned int d1)
374 : direction_0(d0)
375 , direction_1(d1)
376 {}
377
378
379
380 /**
381 * Standard second-order approximation to the first derivative with a
382 * two-point centered scheme. This is used below in a 1d Newton method.
383 */
384 template <typename F>
385 inline auto
386 centered_first_difference(const double center,
387 const double step,
388 const F &f) -> decltype(f(center) - f(center))
389 {
390 return (f(center + step) - f(center - step)) / (2.0 * step);
391 }
392
393
394
395 /**
396 * Standard second-order approximation to the second derivative with a
397 * three-point centered scheme. This is used below in a 1d Newton method.
398 */
399 template <typename F>
400 inline auto
401 centered_second_difference(const double center,
402 const double step,
403 const F &f) -> decltype(f(center) - f(center))
404 {
405 return (f(center + step) - 2.0 * f(center) + f(center - step)) /
406 (step * step);
407 }
408
409
410
411 /**
412 * Fourth order approximation of the derivative
413 *
414 * df/dx_i - df/dx_j
415 *
416 * where <code>i</code> and <code>j</code> are specified by @p
417 * cross_derivative. The derivative approximation is at @p center with a
418 * step size of @p step and function @p f.
419 */
420 template <int structdim, typename F>
421 inline auto
422 cross_stencil(
423 const CrossDerivative cross_derivative,
424 const Tensor<1, GeometryInfo<structdim>::vertices_per_cell> &center,
425 const double step,
426 const F &f) -> decltype(f(center) - f(center))
427 {
428 Tensor<1, GeometryInfo<structdim>::vertices_per_cell> simplex_vector;
429 simplex_vector[cross_derivative.direction_0] = 0.5 * step;
430 simplex_vector[cross_derivative.direction_1] = -0.5 * step;
431 return (-4.0 * f(center) - 1.0 * f(center + simplex_vector) -
432 1.0 / 3.0 * f(center - simplex_vector) +
433 16.0 / 3.0 * f(center + 0.5 * simplex_vector)) /
434 step;
435 }
436
437
438
439 /**
440 * The optimization algorithm used in GridTools::project_to_object is
441 * essentially a gradient descent method. This function computes entries
442 * in the gradient of the objective function; see the description in the
443 * comments inside GridTools::project_to_object for more information.
444 */
445 template <int spacedim, int structdim, typename F>
446 inline double
447 gradient_entry(
448 const unsigned int row_n,
449 const unsigned int dependent_direction,
450 const Point<spacedim> &p0,
451 const Tensor<1, GeometryInfo<structdim>::vertices_per_cell> &center,
452 const double step,
453 const F &f)
454 {
455 Assert(row_n < GeometryInfo<structdim>::vertices_per_cell &&
456 dependent_direction <
457 GeometryInfo<structdim>::vertices_per_cell,
458 ExcMessage("This function assumes that the last weight is a "
459 "dependent variable (and hence we cannot take its "
460 "derivative directly)."));
461 Assert(row_n != dependent_direction,
462 ExcMessage(
463 "We cannot differentiate with respect to the variable "
464 "that is assumed to be dependent."));
465
466 const Point<spacedim> manifold_point = f(center);
467 const Tensor<1, spacedim> stencil_value = cross_stencil<structdim>(
468 {row_n, dependent_direction}, center, step, f);
469 double entry = 0.0;
470 for (unsigned int dim_n = 0; dim_n < spacedim; ++dim_n)
471 entry +=
472 -2.0 * (p0[dim_n] - manifold_point[dim_n]) * stencil_value[dim_n];
473 return entry;
474 }
475
476 /**
477 * Project onto a d-linear object. This is more accurate than the
478 * general algorithm in project_to_object but only works for geometries
479 * described by linear, bilinear, or trilinear mappings.
480 */
481 template <typename Iterator, int spacedim, int structdim>
482 Point<spacedim>
483 project_to_d_linear_object(const Iterator &object,
484 const Point<spacedim> &trial_point)
485 {
486 // let's look at this for simplicity for a quadrilateral
487 // (structdim==2) in a space with spacedim>2 (notate trial_point by
488 // y): all points on the surface are given by
489 // x(\xi) = sum_i v_i phi_x(\xi)
490 // where v_i are the vertices of the quadrilateral, and
491 // \xi=(\xi_1,\xi_2) are the reference coordinates of the
492 // quadrilateral. so what we are trying to do is find a point x on the
493 // surface that is closest to the point y. there are different ways to
494 // solve this problem, but in the end it's a nonlinear problem and we
495 // have to find reference coordinates \xi so that J(\xi) = 1/2 ||
496 // x(\xi)-y ||^2 is minimal. x(\xi) is a function that is
497 // structdim-linear in \xi, so J(\xi) is a polynomial of degree
498 // 2*structdim that we'd like to minimize. unless structdim==1, we'll
499 // have to use a Newton method to find the answer. This leads to the
500 // following formulation of Newton steps:
501 //
502 // Given \xi_k, find \delta\xi_k so that
503 // H_k \delta\xi_k = - F_k
504 // where H_k is an approximation to the second derivatives of J at
505 // \xi_k, and F_k is the first derivative of J. We'll iterate this a
506 // number of times until the right hand side is small enough. As a
507 // stopping criterion, we terminate if ||\delta\xi||<eps.
508 //
509 // As for the Hessian, the best choice would be
510 // H_k = J''(\xi_k)
511 // but we'll opt for the simpler Gauss-Newton form
512 // H_k = A^T A
513 // i.e.
514 // (H_k)_{nm} = \sum_{i,j} v_i*v_j *
515 // \partial_n phi_i *
516 // \partial_m phi_j
517 // we start at xi=(0.5, 0.5).
518 Point<structdim> xi;
519 for (unsigned int d = 0; d < structdim; ++d)
520 xi[d] = 0.5;
521
522 Point<spacedim> x_k;
523 for (const unsigned int i : GeometryInfo<structdim>::vertex_indices())
524 x_k += object->vertex(i) *
525 GeometryInfo<structdim>::d_linear_shape_function(xi, i);
526
527 do
528 {
529 Tensor<1, structdim> F_k;
530 for (const unsigned int i :
531 GeometryInfo<structdim>::vertex_indices())
532 F_k +=
533 (x_k - trial_point) * object->vertex(i) *
534 GeometryInfo<structdim>::d_linear_shape_function_gradient(xi,
535 i);
536
537 Tensor<2, structdim> H_k;
538 for (const unsigned int i :
539 GeometryInfo<structdim>::vertex_indices())
540 for (const unsigned int j :
541 GeometryInfo<structdim>::vertex_indices())
542 {
543 Tensor<2, structdim> tmp = outer_product(
544 GeometryInfo<structdim>::d_linear_shape_function_gradient(
545 xi, i),
546 GeometryInfo<structdim>::d_linear_shape_function_gradient(
547 xi, j));
548 H_k += (object->vertex(i) * object->vertex(j)) * tmp;
549 }
550
551 const Tensor<1, structdim> delta_xi = -invert(H_k) * F_k;
552 xi += delta_xi;
553
554 x_k = Point<spacedim>();
555 for (const unsigned int i :
556 GeometryInfo<structdim>::vertex_indices())
557 x_k += object->vertex(i) *
558 GeometryInfo<structdim>::d_linear_shape_function(xi, i);
559
560 if (delta_xi.norm() < 1e-7)
561 break;
562 }
563 while (true);
564
565 return x_k;
566 }
567 } // namespace ProjectToObject
568
569 // We hit an internal compiler error in ICC 15 if we define this as a lambda
570 // inside the project_to_object function below.
571 template <int structdim>
572 inline bool
573 weights_are_ok(
574 const Tensor<1, GeometryInfo<structdim>::vertices_per_cell> &v)
575 {
576 // clang has trouble figuring out structdim here, so define it
577 // again:
578 static const std::size_t n_vertices_per_cell =
579 Tensor<1, GeometryInfo<structdim>::vertices_per_cell>::
580 n_independent_components;
581 std::array<double, n_vertices_per_cell> copied_weights;
582 for (unsigned int i = 0; i < n_vertices_per_cell; ++i)
583 {
584 copied_weights[i] = v[i];
585 if (v[i] < 0.0 || v[i] > 1.0)
586 return false;
587 }
588
589 // check the sum: try to avoid some roundoff errors by summing in order
590 std::sort(copied_weights.begin(), copied_weights.end());
591 const double sum =
592 std::accumulate(copied_weights.begin(), copied_weights.end(), 0.0);
593 return std::abs(sum - 1.0) < 1e-10; // same tolerance used in manifold.cc
594 }
595 } // namespace internal
596
597
598
599 template <typename Iterator>
600 Point<Iterator::AccessorType::space_dimension>
601 project_to_object(
602 const Iterator &object,
603 const Point<Iterator::AccessorType::space_dimension> &trial_point)
604 {
605 const int spacedim = Iterator::AccessorType::space_dimension;
606 const int structdim = Iterator::AccessorType::structure_dimension;
607
608 Point<spacedim> projected_point = trial_point;
609
610 if (structdim >= spacedim)
611 return projected_point;
612 else if (structdim == 1 || structdim == 2)
613 {
614 using namespace internal::ProjectToObject;
615 // Try to use the special flat algorithm for quads (this is better
616 // than the general algorithm in 3d). This does not take into account
617 // whether projected_point is outside the quad, but we optimize along
618 // lines below anyway:
619 const int dim = Iterator::AccessorType::dimension;
620 const Manifold<dim, spacedim> &manifold = object->get_manifold();
621 if (structdim == 2 && dynamic_cast<const FlatManifold<dim, spacedim> *>(
622 &manifold) != nullptr)
623 {
624 projected_point =
625 project_to_d_linear_object<Iterator, spacedim, structdim>(
626 object, trial_point);
627 }
628 else
629 {
630 // We want to find a point on the convex hull (defined by the
631 // vertices of the object and the manifold description) that is
632 // relatively close to the trial point. This has a few issues:
633 //
634 // 1. For a general convex hull we are not guaranteed that a unique
635 // minimum exists.
636 // 2. The independent variables in the optimization process are the
637 // weights given to Manifold::get_new_point, which must sum to 1,
638 // so we cannot use standard finite differences to approximate a
639 // gradient.
640 //
641 // There is not much we can do about 1., but for 2. we can derive
642 // finite difference stencils that work on a structdim-dimensional
643 // simplex and rewrite the optimization problem to use those
644 // instead. Consider the structdim 2 case and let
645 //
646 // F(c0, c1, c2, c3) = Manifold::get_new_point(vertices, {c0, c1,
647 // c2, c3})
648 //
649 // where {c0, c1, c2, c3} are the weights for the four vertices on
650 // the quadrilateral. We seek to minimize the Euclidean distance
651 // between F(...) and trial_point. We can solve for c3 in terms of
652 // the other weights and get, for one coordinate direction
653 //
654 // d/dc0 ((x0 - F(c0, c1, c2, 1 - c0 - c1 - c2))^2)
655 // = -2(x0 - F(...)) (d/dc0 F(...) - d/dc3 F(...))
656 //
657 // where we substitute back in for c3 after taking the
658 // derivative. We can compute a stencil for the cross derivative
659 // d/dc0 - d/dc3: this is exactly what cross_stencil approximates
660 // (and gradient_entry computes the sum over the independent
661 // variables). Below, we somewhat arbitrarily pick the last
662 // component as the dependent one.
663 //
664 // Since we can now calculate derivatives of the objective
665 // function we can use gradient descent to minimize it.
666 //
667 // Of course, this is much simpler in the structdim = 1 case (we
668 // could rewrite the projection as a 1d optimization problem), but
669 // to reduce the potential for bugs we use the same code in both
670 // cases.
671 const double step_size = object->diameter() / 64.0;
672
673 constexpr unsigned int n_vertices_per_cell =
674 GeometryInfo<structdim>::vertices_per_cell;
675
676 std::array<Point<spacedim>, n_vertices_per_cell> vertices;
677 for (unsigned int vertex_n = 0; vertex_n < n_vertices_per_cell;
678 ++vertex_n)
679 vertices[vertex_n] = object->vertex(vertex_n);
680
681 auto get_point_from_weights =
682 [&](const Tensor<1, n_vertices_per_cell> &weights)
683 -> Point<spacedim> {
684 return object->get_manifold().get_new_point(
685 make_array_view(vertices.begin(), vertices.end()),
686 make_array_view(weights.begin_raw(), weights.end_raw()));
687 };
688
689 // pick the initial weights as (normalized) inverse distances from
690 // the trial point:
691 Tensor<1, n_vertices_per_cell> guess_weights;
692 double guess_weights_sum = 0.0;
693 for (unsigned int vertex_n = 0; vertex_n < n_vertices_per_cell;
694 ++vertex_n)
695 {
696 const double distance =
697 vertices[vertex_n].distance(trial_point);
698 if (distance == 0.0)
699 {
700 guess_weights = 0.0;
701 guess_weights[vertex_n] = 1.0;
702 guess_weights_sum = 1.0;
703 break;
704 }
705 else
706 {
707 guess_weights[vertex_n] = 1.0 / distance;
708 guess_weights_sum += guess_weights[vertex_n];
709 }
710 }
711 guess_weights /= guess_weights_sum;
712 Assert(internal::weights_are_ok<structdim>(guess_weights),
713 ExcInternalError());
714
715 // The optimization algorithm consists of two parts:
716 //
717 // 1. An outer loop where we apply the gradient descent algorithm.
718 // 2. An inner loop where we do a line search to find the optimal
719 // length of the step one should take in the gradient direction.
720 //
721 for (unsigned int outer_n = 0; outer_n < 40; ++outer_n)
722 {
723 const unsigned int dependent_direction =
724 n_vertices_per_cell - 1;
725 Tensor<1, n_vertices_per_cell> current_gradient;
726 for (unsigned int row_n = 0; row_n < n_vertices_per_cell;
727 ++row_n)
728 {
729 if (row_n != dependent_direction)
730 {
731 current_gradient[row_n] =
732 gradient_entry<spacedim, structdim>(
733 row_n,
734 dependent_direction,
735 trial_point,
736 guess_weights,
737 step_size,
738 get_point_from_weights);
739
740 current_gradient[dependent_direction] -=
741 current_gradient[row_n];
742 }
743 }
744
745 // We need to travel in the -gradient direction, as noted
746 // above, but we may not want to take a full step in that
747 // direction; instead, guess that we will go -0.5*gradient and
748 // do quasi-Newton iteration to pick the best multiplier. The
749 // goal is to find a scalar alpha such that
750 //
751 // F(x - alpha g)
752 //
753 // is minimized, where g is the gradient and F is the
754 // objective function. To find the optimal value we find roots
755 // of the derivative of the objective function with respect to
756 // alpha by Newton iteration, where we approximate the first
757 // and second derivatives of F(x - alpha g) with centered
758 // finite differences.
759 double gradient_weight = -0.5;
760 auto gradient_weight_objective_function =
761 [&](const double gradient_weight_guess) -> double {
762 return (trial_point -
763 get_point_from_weights(guess_weights +
764 gradient_weight_guess *
765 current_gradient))
766 .norm_square();
767 };
768
769 for (unsigned int inner_n = 0; inner_n < 10; ++inner_n)
770 {
771 const double update_numerator = centered_first_difference(
772 gradient_weight,
773 step_size,
774 gradient_weight_objective_function);
775 const double update_denominator =
776 centered_second_difference(
777 gradient_weight,
778 step_size,
779 gradient_weight_objective_function);
780
781 // avoid division by zero. Note that we limit the gradient
782 // weight below
783 if (std::abs(update_denominator) == 0.0)
784 break;
785 gradient_weight =
786 gradient_weight - update_numerator / update_denominator;
787
788 // Put a fairly lenient bound on the largest possible
789 // gradient (things tend to be locally flat, so the gradient
790 // itself is usually small)
791 if (std::abs(gradient_weight) > 10)
792 {
793 gradient_weight = -10.0;
794 break;
795 }
796 }
797
798 // It only makes sense to take convex combinations with weights
799 // between zero and one. If the update takes us outside of this
800 // region then rescale the update to stay within the region and
801 // try again
802 Tensor<1, n_vertices_per_cell> tentative_weights =
803 guess_weights + gradient_weight * current_gradient;
804
805 double new_gradient_weight = gradient_weight;
806 for (unsigned int iteration_count = 0; iteration_count < 40;
807 ++iteration_count)
808 {
809 if (internal::weights_are_ok<structdim>(tentative_weights))
810 break;
811
812 for (unsigned int i = 0; i < n_vertices_per_cell; ++i)
813 {
814 if (tentative_weights[i] < 0.0)
815 {
816 tentative_weights -=
817 (tentative_weights[i] / current_gradient[i]) *
818 current_gradient;
819 }
820 if (tentative_weights[i] < 0.0 ||
821 1.0 < tentative_weights[i])
822 {
823 new_gradient_weight /= 2.0;
824 tentative_weights =
825 guess_weights +
826 new_gradient_weight * current_gradient;
827 }
828 }
829 }
830
831 // the update might still send us outside the valid region, so
832 // check again and quit if the update is still not valid
833 if (!internal::weights_are_ok<structdim>(tentative_weights))
834 break;
835
836 // if we cannot get closer by traveling in the gradient
837 // direction then quit
838 if (get_point_from_weights(tentative_weights)
839 .distance(trial_point) <
840 get_point_from_weights(guess_weights).distance(trial_point))
841 guess_weights = tentative_weights;
842 else
843 break;
844 Assert(internal::weights_are_ok<structdim>(guess_weights),
845 ExcInternalError());
846 }
847 Assert(internal::weights_are_ok<structdim>(guess_weights),
848 ExcInternalError());
849 projected_point = get_point_from_weights(guess_weights);
850 }
851
852 // if structdim == 2 and the optimal point is not on the interior then
853 // we may be able to get a more accurate result by projecting onto the
854 // lines.
855 if (structdim == 2)
856 {
857 std::array<Point<spacedim>, GeometryInfo<structdim>::lines_per_cell>
858 line_projections;
859 for (unsigned int line_n = 0;
860 line_n < GeometryInfo<structdim>::lines_per_cell;
861 ++line_n)
862 {
863 line_projections[line_n] =
864 project_to_object(object->line(line_n), trial_point);
865 }
866 std::sort(line_projections.begin(),
867 line_projections.end(),
868 [&](const Point<spacedim> &a, const Point<spacedim> &b) {
869 return a.distance(trial_point) <
870 b.distance(trial_point);
871 });
872 if (line_projections[0].distance(trial_point) <
873 projected_point.distance(trial_point))
874 projected_point = line_projections[0];
875 }
876 }
877 else
878 {
879 DEAL_II_NOT_IMPLEMENTED();
880 return projected_point;
881 }
882
883 return projected_point;
884 }
885 } // namespace GridTools
886 #endif // DOXYGEN
887
888 DEAL_II_NAMESPACE_CLOSE
889
890 #endif