Is there a way to change the interpolation scheme used in ListDensityPlot?

Question

Recently I was trying to answer this question on how to make a smooth ListDensityPlot when I found that the output depends on the order of the data if you are using InterpolationOrder>0. For example

data = Flatten[Table[{x, y, If[x==y, 1, 0]}, {x, 0, 1, 1/10}, {y, 0, 1, 1/10}],1];
ListDensityPlot[data] 

It becomes better if you reorder the data.

data2 = Sort[data, #1[[1]] < #2[[1]] &];
ListDensityPlot[data2]

Instead of changing the data, I guess the same result could be obtained if we can change the interpolation scheme MMA is using. Is there any way to do that?

By interpolation scheme I mean the algorithm MMA is using to produce the data in between two data points to make a smooth figure.

Just for curiosity, I try the same thing with M9.0.1 and this is the result with data2.

Answer 1

ListDensityPlot interpolated by constructing a Delaunay triangulation of the data points and interpolating linearly on each triangle. For a perfectly rectangular point grid, there are two ways to break each rectangle into triangles.

If we distort the grid slightly and make each rectangle a parallelogram, then there will only be one way to construct the Delaunay triangulation.

So we can do this:

data = Flatten[
   Table[{x, y + 0.0001 x, If[x == y, 1, 0]}, {x, 0, 1, 1/10}, {y, 0, 
     1, 1/10}], 1];
ListDensityPlot[data, Mesh -> All]

data = Flatten[
   Table[{x, y - 0.0001 x, If[x == y, 1, 0]}, {x, 0, 1, 1/10}, {y, 0, 
     1, 1/10}], 1];
ListDensityPlot[data, Mesh -> All]

This is a hack so you might want to wait for other answers ...