TransWikia.com

What are the best ways to interpolate a vector field inside (convex) polygons?

Computational Science Asked on October 4, 2021

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^0precsigma^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))nablaphi_{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{vsigma^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{vsigma^0}$ is not for all vertices $sigma^0$ an edge of the polygon.
  • $overline{vsigma_1^0}, dots, overline{vsigma_{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.

2 Answers

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!

Answered by ConvexHull on October 4, 2021

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.

Answered by Wolfgang Bangerth on October 4, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP