Interpolation of the values of points on the surface created by convex hull

I have some 3D points like and their values like . The convex hull of these points are generated by convhull or convexHull (see figure below)

Now I want to interpolate the values of triangle vertices for N new points on the convex hull. What are the possible methods to do this?

[Jose Carrasco]

I have the same question and have been researching for two days now, but could not figure it out yet. Please I would be glad if someone gave an answer to this. Did you manage to solve the problem eventually, Nima?

[John D'Errico]

This got no significant answer, because it was far too vague to get one.

[Jose Carrasco]

Dear all, it seems to me like the original question has been amply answered. However, in my case I want to create and plot the minimal volume with a derivable surface that is tangent to all the vertices of a convex hull. Thanks everyone in advance.

[Matt J]

@Jose Carrasco if your question is different from the original question, you should post that question in its own thread. When you do so, you should clarify why the "minimal volume" you seek would not be the convex hull itself.

[Torsten]

@Jose Carrasco

What do you mean that a surface is tangent to a vertex ?

[Jose Carrasco]

@Torsten

Hi Torsten, I am sorry my point is not clear enough. With "tangent to a vertex" I mean that I want to produce the minimum surface that is "bubbly" (derivable at any point) and tangent to all the vertices of the convex hull made of all the triangular surfaces that connect the boundaries (most external or "extreme" points) of the scatter plot attached to this comment.

open untitled.fig

[Matt J]

@Jose Carrasco The surface you describe does not have a minimal form. It wll always be possible to make a "bubbly" surface smaller and smaller in a manner that converges to the convex hull. Think of a straight line segment in 2D and ask yourself, what is the smallest ellipse that can enclose the line. Clearly the solution must choose the major axis of the ellipse to be the line segment itself. However, the minor axis can be chosen to be any arbitrarily small eps>0.

Answer 1

[Nima]

Hi everyone,

The answer I have already found is: Barycentric coordinate system.

In the section ' Interpolation on a triangular unstructured grid ' I have the solution.

Answer 2

[David Goodmanson]

Hi Jose/Nima,

Suppose you have a triangle with vertex points p1, p2, p3, each of those defined by a column vector of their x,y,z coordinates. You can form the 3x3 matrix

M = [p1 p2 p3]

which is nonsingular if the vertex points are not colinear, which they are not in this case. Any point p0 (also defined by a column vector) is a linear combination of p1,p2,p3 with coefficients c = [c1;c2;c3]. In matrix notation that is M*c = p0

with solution

c = M\p0  

For a quantity A with values A1,A2,A3 at points p1,p2,p3 respectively, the obvious way to interpolate and find the value at p0 is to use c1A1 + c2A2 + c3A3, or in matrix notation

Ainterp = c'*[A1;A2;A3] 

so the three highlighted lines provide a solution. This is true whether p0 lies in the plane of the triangle or not, although it might not be a useful solution if p0 is far away from the triangle. If the point lies inside the triangle on the surface, I believe that 0<=c1<=1, 0<=c2<=1, 0<=c3<=1, c1+c2+c3 = 1 which is appropriate for intepolation.

[John D'Errico]

Yes. As long as the weights, as applied to the three corners of a triangle sum to 1, and all are between 0 and 1, this forms a convex combination. As such, a new point formed from such a linear combination of the corner vertices will lie strictly inside the triangle, and will lie in the plane of the triangle. If any of those weights were exactly 1, then the interpolated point lies exactly on the corresponding vertex. And if any of the weights were exactly 0, this corresponds to a point along the line opposite one of the vertices.

How to "interpolate" such a polytope is undefined, since there was never any direction as to what that interpolation would mean to either @Nima or @Jose Carrasco. For example, was the question targeted at sampling new points on the surface for some unspecified reason and based on some unspecified criteria? Or was the real question how to interpolate values at the corner nodes of the polytope, then trying to evaluate some function f(x,y,z) using interpolation on the surface of the polytope? Give me some time, and I might even guess some other reason behind the questions here, why I would not have touched this post when it originally was made.

[Torsten]

@David Goodmanson

The interpolation suggested assumes that the function can be linearly approximated over the triangle:

f(p0) = f(c1*p1+c2*p2+c3*p3) =(*) c1*f(p1) + c2*f(p2) + c3*f(p3) = c1*A1 + c2*A2 + c3*A3

where at the =(*), the linearity of the function f is used.

This might or might not be a good choice.

Answer 3

[Matt J]

For example, was the question targeted at sampling new points on the surface...?

Assuming that's the correct interpretation, then,

N=10;

P=rand(10,3);
k=convhull(P);
V=P(unique(k),:);  %Generate vertices V

k=num2cell(convhull(V),1);

res=@(z) reshape(z,[],1,3); %Generate affine frame for each triangle
 V0=res( V(k{1},:));
dV1=res( V(k{2},:)) -V0 ;
dV2=res( V(k{3},:)) -V0;

[a,b]=ndgrid(linspace(0,1,10)); %Sweep each triangle with extra samples
idx=a+b<=1;
a=a(idx)'; b=b(idx)';

XYZ=num2cell( reshape(V0+dV1.*a+dV2.*b ,[],3) ,1);


trisurf(cell2mat(k),V(:,1), V(:,2),V(:,3)); hold on  %Visualize
scatter3(XYZ{:},'filled','r'); hold off