2
$\begingroup$

I want to interpolate a vector field inside convex polygons in a polygonal mesh.

For triangular meshes the scheme uses a piecewise constant interpolation in the triangle, discretized at the center of the triangle.

I am especially interested in interpolating the gradient of a scalar field on the vertices, so feel free to suggest methods that only work for the gradient.

My current simple ideas:

  1. Increase the degree of the interpolation polynomial.
  2. Solve a least-squares problem.
  3. Use a triangulation to get a continuous but in general non-differential field inside the polygon.
  4. Using hat functions like in the finite element method.

I wonder if there are more advanced techniques and what are the advantages and drawbacks of different ways to interpolate the field.

I think 1) may be a bad idea, because I do not know if it will overfit outliers in the data. In addition it may behave differently for polygons with many vertices and polygons with little vertices in the same mesh.

Approach 2) is probably useful to avoid overfitting and I guess the most common way for interpolating in overdetermined problems.

Option 3) may be the simplest, but will result in a less smooth field inside the polygon and I am not sure what the implications of choosing different triangulations are.

For option 4) I am not sure if interpolating with hat functions of a degree that depends on the number of vertices of the polygon is not equivalent to option 1), i.e., raising the degree of an interpolation polynomial.

What are other ways for interpolating vector fields / gradients in polygonal meshes?


I would like to keep this more general, as the concept can be useful for other applications, but I'll add an example application I am currently looking for.

Application

Using the discrete exterior calculus as defined in Discrete Exterior Calculus (Hirani 2003), a piecewise constant gradient $\nabla \phi_{\sigma^0,\sigma^n}$ is defined (Section 2.7) for a simplex with $\sum_{\sigma^0\prec\sigma^n}\ \phi_{\sigma^0,\sigma^n}(x) = 1$.

The notation in the sum means, that the function is evaluated at all vertices of the simplex.

One discrete $\sharp$ operator is defined in equation 5.7.2., that maps discrete $1$-forms to a vector field defined on the circumcenters of the simplices as

$$ \sum_{\sigma^0 \prec \sigma^n} (f(\sigma^0) - f(v))\nabla\phi_{\sigma^0,\sigma^n} $$

where $v$ is an arbitrary vertex $\sigma^0_i$ of the simplex $\sigma^n$.
(Note that the definition here is only given for the gradient)

This definition certainly works fine for simplices, as the edges $\overline{v\sigma^0}$ form a basis for the tangential space, that is the edges of the simplex (e.g. the two edges adjacent to a vertex of a triangle).

For polygons with more than $n+1$ vertices, there are two problems:

  • $\overline{v\sigma^0}$ is not for all vertices $\sigma^0$ an edge of the polygon.
  • $\overline{v\sigma_1^0}, \dots, \overline{v\sigma_{n+1+k}^0}$ is over defined. For example an quadrilateral would define three vectors to span a 2D tangential space.

There is an underlying reason for the problem, that is that a quadrilateral (or polygon of higher order) does not guarantee that all points lie in the same tangential space, which is a reason why possibly a least squares solution could be an option when one can assume that the polygon is mostly flat and why a higher order interpolation may be useful when the polygon is possibly highly curved.

The question above is, what are the best ways for interpolating, e.g., inside a 2D hexagon and what are the different advantages and problems with the approaches?
I am especially interested in which properties are conserved and which are approximated, as the DEC scheme separates its operators in ones that can be defined such that they hold exactly (on predefined elements, i.e, parts of a mesh only) and ones that involve a metric and are only approximated.

$\endgroup$
  • 1
    $\begingroup$ I am confused by the question. What is the data you have? $\endgroup$ – Wolfgang Bangerth Jul 30 at 14:11
  • $\begingroup$ Is it a high-degree polygon? So basically your vector field is given on a boundary of a domain, and you want to reconstruct it inside? $\endgroup$ – Maxim Umansky Jul 30 at 16:27
  • $\begingroup$ I am having a mesh. For most tasks I have scalar data on the vertices and like to have the gradient inside cells. For triangles this is straightforward, but I think for polygonal cells there are several ways to do it. In the best case the method should be useful for most functions, but when you like to suggest methods for special cases think of fluid problems from a simple diffusion up to navier-stokes equations as the underlying function discretized on vertices and cells (dual vertices or volumes). $\endgroup$ – allo Jul 31 at 8:48
  • 2
    $\begingroup$ I meant that much of the effort involved in FEM is interpolating fields (or approximating them with linear least squares, or some other form of approximation), and their gradients, over polygonal meshes. There is a cottage industry of researchers applying different fitting methods over various geometries. $\endgroup$ – Charlie S Jul 31 at 12:36
  • 3
    $\begingroup$ I think your missing link between discrete exterior calculus and finite element methods are the papers of d.n. Arnold, for an overview and all relevant references see femtable.org , though I recommend his booklet finite element exterior calculus. $\endgroup$ – Bort Aug 1 at 21:48
4
$\begingroup$

Let me try and break the problem down into two steps.

Step 1: You have a polygon (one cell of your mesh) and you have scalar data $d_i$ associated with each vertex $\mathbf x_i$ of that polygon. You want to define a function $u(x)$ so that $u(\mathbf x_i)=d_i$. This is what is called interpolation, and you will find a vast literature on interpolation on polygonal cells. An easy way is to split the polygon into triangles, and then do piecewise linear interpolation on each triangle. But there are other options as well: For example, you can use harmonic functions to interpolate on each polygon (this is the basic idea of the "virtual element method").

Step 2: You want to find something like $\nabla u(\mathbf x_i)$. The problem is of course that while $u$ is a continuous function, it is not differentiable at the vertices $\mathbf x_i$. The solution to this is to use "recovery" procedures -- e.g., what is used in the Zienkiewicv-Zhu (ZZ) estimator. In essence, you are solving a least squares problem of the form $$ \min_{\mathbf g(\mathbf x)} \frac 12 \| \nabla u - \mathbf g\|^2 $$ where the integral in the norm extends over all cells adjacent to the vertex in question, $\mathbf g$ is a polygon of appropriate degree, and then you evaluate $\mathbf g(\mathbf x_i) \approx \nabla u(\mathbf x_i)$. The details are a bit more complicated, but it's an established technique for which you will find a substantial amount of literature.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Your explanation indicates that you generally have little idea what interpolation can do. I think nobody can tell you what is the best interpolation method regardless of your data.

Basically, we can only give you advises:

  1. Supposing you know that the data points are quite accurate in a collocative sense e.g. no noise, and the data is smooth, you may use a high order representation (polynomials or others) inside the polygon. Note that high order does not necessarily mean high accuracy. It only tells you that the error decreases faster with more resolution.

  2. Supposing you know that the data points are quite noisy however still smooth it is more advisable to use some of the data points for a least-squares or Galerkin type approximation within a lower-order representation.

  3. Supposing you know that your data is not smooth e.g. sign function, a high order representation of your data inside the polygon is not advisable. This holds regardless of whether your data is noisy or not.

To sum up:

  • First, you need to know what your data looks like!
  • Secondly, it is up to you what you want to make of it!
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think the problems in communicating what I want to do is, that I would like to have a solution (or maybe 2-3 solutions that can be chosen depending on the problem) to be able to extend a general scheme and not to solve a particular problem. I added a part of the scheme to the application section, but the full definition in the thesis allows to solve a large number of different PDEs and losing this by using an interpolation chosen for one specific problem would mean that each problem needs another extension to the scheme. That's why I started asking without much detail on the implementation. $\endgroup$ – allo Aug 1 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.