How does scatteredinterpolant interpolate points on convex hull?

Hello,

i want to know how scatteredinterpolant calculates query points that lie on the convex hull of the sample points.

I need to know this specifically for natural neighbor interpolation. To my understanding points on the convex hull produce unbounded voronoi cells with an infinite area, which means that all weights used for the interpolation should be zero (since the weights are defined as overlapping area devided by the area of the new voronoi cell), which in return means no interpolation is possible.

The interpolation is tested with the following code. The value of qv is returned as 0.5484.

Points=[-1.5 3.2; 1.8 3.2; -3.7 1.5; -1.5 1.3;
        0.8 1.2; 3.3 1.5; -4.0 -1.0; -2.3 -0.7; 
        0 -0.5; 2.0 -1.5; 3.7 -0.8; -3.5 -2.9; 
        -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];
z=Points(:,2).*sin(Points(:,1)) - Points(:,1).*cos(Points(:,2));
qP=[0.3 3.2];
F = scatteredInterpolant(Points(:,1),Points(:,2),z);
F.Method = 'natural';
qv=F(qP);

figure(1)
voronoi(Points(:,1),Points(:,2));

figure(2)
AllPoints=[Points; qP];
voronoi(AllPoints(:,1),AllPoints(:,2));

Answer 1

[Vidhi Agarwal]

Hi @PatrickF,

The “scatteredInterpolant” function in MATLAB is used for interpolating scattered data points in 2D or 3D space. When using natural neighbor interpolation, the method is based on Voronoi tessellation.

In Voronoi tessellation the dataset is divided into regions (Voronoi cells), where each region corresponds to one data point. Any location within a region is closer to its corresponding data point than to any other data point.

While in Natural neighbor interpolation query a point, the algorithm temporarily adds this point to the dataset, recalculates the Voronoi diagram, and observes how the existing Voronoi cells are altered. The interpolation value is computed as a weighted average of the values of the neighboring points, with weights based on the areas of overlap between the new and existing Voronoi cells.

For points on the convex hull:

• Unbounded Voronoi Cells: These cells are indeed unbounded, but natural neighbor interpolation assigns weights by considering the finite intersections between the new and existing Voronoi cells.
• Weight Calculation: Weights are based on these finite intersection areas, ensuring meaningful interpolation even with unbounded cells.
• Boundary Handling: The method can extrapolate near boundaries, which may affect accuracy, but it still provides useful interpolation results.

To understand more about “scatteredInterpolant” refer to the following command to access the documentation of the same:

• web(fullfile(docroot, " matlab/ref/scatteredinterpolant.html "))

Hope that helps!