Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question arose in response to a comment by Leonid to my answer for this question. He noted that for unstructured grids, Interpolation can only use InterpolationOrder->1. For example:

data = Flatten[Table[{x, y, x^2 + y^2}, {x, -10, 10}, {y, -10, 10}], 1];
dataDelete = Delete[data, RandomInteger[{1, Length[data]}]]
intD = Interpolation[dataDelete]
(* Interpolation::udeg: Interpolation on unstructured grids is currently only supported for InterpolationOrder->1 or InterpolationOrder->All. Order will be reduced to 1. *)

which gives a result much worse than All-order Interpolation. So, here's my question:

For data that is largely structured, but is missing one (or a few?) grid points, is there any way to figure out where the grid is missing points? This would allow you to first use linear interpolation to find a good guess for the value of the function at the missing grid points, then add that grid point to the dataset, only to interpolate the whole thing after. Then the error in the interpolation will be localized to the reconstructed region. Something like

dataReconstructed=Append[dataDelete,Sequence @@ Flatten@{#, intD @@ #} & /@missingcoords]
intReconstructed = Interpolation[dataReconstructed]

A manual example:

todelete = RandomInteger[{1, Length[data]}];
dataDelete = Delete[data, todelete];
intD = Interpolation[dataDelete]
missingcoords = {data[[todelete, {1, 2}]]}

dataReconstructed = Append[dataDelete,Sequence @@ Flatten@{#, intD @@ #} & /@missingcoords]
intReconstructed = Interpolation[dataReconstructed]

Comparing these two methods using exact[x_, y_] := x^2 + y^2:

Plot3D[intD[x, y] - exact[x, y], {x, -10, 10}, {y, -10, 10}]

Mathematica graphics

has differences all over the interpolated region, worse at the missing point. But:

Plot3D[intReconstructed[x, y] - exact[x, y], {x, -10, 10}, {y, -10, 10}]

Mathematica graphics

is much better everywhere except for the missing points.

In order to do this for a set where I don't know which grid points are missing, is there a way to figure out where the missing grid points are in a mostly structured grid?

share|improve this question
To figure out where the missing points are, you can build on my answer here: Sorry, no time to look in details now, but I might come back tomorrow morning CET. – Szabolcs Apr 26 '12 at 18:05
up vote 8 down vote accepted

How to figure out where the missing grid points are... This maybe not as robust as it gets

Take your data

data = Flatten[Table[{x, y, x^2 + y^2}, {x, -10, 10}, {y, -10, 10}], 
dataDelete = Delete[data, RandomInteger[{1, Length[data]}]];

and extract the domain coordinates

d = dataDelete[[All, ;; -2]];

Choose the step to be the commonest of the differences in each direction

step = #2@
       Join @@ Differences /@ Sort /@ GatherBy[d, #]] & @@@ {
    {First, Last},
    {Last, First}

Choose the range, the limits, to be the minimum and maximum of all rows and coloumns

limits = Through@{Min, Max}[#] & /@ Transpose@d;

Take the complement of a perfect grid and your data grid

Complement[Tuples[Range @@ Transpose@limits], d]

I got {{-3, 6}}

share|improve this answer

Here is a simplistic one:

gridReconstruct[unstructuredGrid_List] :=
   Tuples[Range[Min[#], Max[#], First@Sort@Differences@Union@#] & /@ 

It just determines the minimal step along each direction, as well as maximal and minimal coordinate value, and constructs a grid based on that. Should work in any number of dimensions.

As an example, I construct a simple 2D grid and delete 5 random points from it:

grid = Flatten[Outer[List, Range[-1, 1, 0.5], Range[-1, 1, 0.5]], 1];
unstgrid = Delete[grid, Transpose[{RandomSample[Range[Length[grid]], 5]}]]


{{-1., -0.5}, {-1., 0.}, {-1., 0.5}, {-1., 1.}, {-0.5, 0.}, {-0.5, 0.5}, 
 {0., -1.}, {0., -0.5}, {0., 0.}, {0., 0.5}, {0.,1.}, {0.5, -1.}, 
 {0.5, -0.5}, {0.5, 0.}, {0.5, 0.5}, {1., -1.}, {1., -0.5}, {1., 0.}, 
 {1., 0.5}, {1., 1.}}


Now, call gridReconstruct

gridReconstruct[unstgrid] == grid


This is, of course, a very simplistic approach.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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