# Interpolation of a Concave Mesh

I would like to have an algorithm that interpolates the values attached to nodes in a concave mesh mesh.

To be me precise, assume we have a point cloud P (e.g. in 3 dimensions) and a list of edges E connecting it with form a concave mesh in the form $$E=[[i_1,i_2],[j_,j_2],...]$$, where $$i,j$$ are nodes. Further assume that each point in P is associated with a value V (e.g. Temperature).

The algorithm I am looking for takes these objects together with an arbitrary point x in space and returns an interpolated value iff the point lies within the concave mesh and something unique if it doesn't (e.g. NaN). Hence if has a signature like:

f(P,E,V,x) -> float


To illustrate this a bit. The point cloud might look like this with the hull of the edges shown in gray.

The algorithms I found mostly deal with convex point clouds exclusively. In that case the Delaunay triangulation is unique (except in some edge cases) and the interpolation can be done e.g. with a linear barycentric interpolation. However, I haven't found anything general about concave meshes. Yet I assume that this is something that has some general use as well and there must exist something already that I am not aware of.

• I would consider splitting the domain into convex parts and constructing triangulation for each of those. Jan 11 at 14:36
• The problem with concave sets is that you need to know which points are on the boundary. If you don't know that, just skip a point in the gray line -- it just becomes an interior point. You have to label manually which points you want to consider as interior/boundary. Jan 11 at 16:19
• Is your $E$ represent the connectivity by showing the ids of first and second points of the edge? Something like this: $E = [[i_{1},i_{2}],[j_{1},j_{2}],...]$? If yes, this becomes so easy. Jan 12 at 1:14
• You find the surface points by taking unique values of flattened array of $E$. Then, you reconstruct a surface by using your surface points based on Poisson surface reconstruction algorithm and then it's possible to build a distance function to examine if an arbitrary given point $x$ is in inside the reconstructed surface or not and then if it is inside, return an interpolated value based on your chosen stencil for interpolation. Jan 12 at 1:14
• @AloneProgrammer Yes I have the connectivity. Why are the surface points unique values in the flattened E? Each node on the surface is connected to two edges. These edges are not oriented in a specific way. Hence, the surface points are not unique (or am I mistaken?) What kind of distance function works for an arbitrary shaped n-dimentionsional polygon?
– ls.
Jan 12 at 9:09