15
$\begingroup$

Bug introduced in 10.0 and fixed in 10.1


Context

I am trying to identify contours of a function which is sampled on a cartesian grid within an irregular (triangular) region.

Here is the data

tab = ReadList[
    "https://dl.dropboxusercontent.com/u/659996/tabOmega1.txt"] // 
   Flatten[#, 1] &;

It looks like this:

Map[Point, Map[Most, tab], 1] // Graphics
g3 = ListPointPlot3D[tab , PlotRange -> Full]

Mathematica graphics Mathematica graphics

Now Mathematica (v10.0.2) happily makes contours of it:

g = ListContourPlot[tab , PlotRange -> Full]

Mathematica graphics

But if I try to produce an interpolation function out of it

tabint = tab /. {rp_, ra_, v_} -> {{rp, ra}, v};    
func = Interpolation[tabint, InterpolationOrder -> All];

It produces unrealistic numbers

func[1, 2]

(* 37.9231 *)

Indeed the interpolation is completely off:

Plot3D[func[x, y], {x, y} ∈ dg]

Mathematica graphics

Question

How can I get Mathematica to interpolate properly though this evenly sampled data on an irregular region?

Attempt

Following this post

I can use

func = Nearest[{#, #2} -> #3 & @@@ tab];
ContourPlot[func[{x, y}], {x, 0, 4}, {y, x, 4}]

Mathematica graphics

but the contours are irregular because the interpolation is piecewise constant, as can be seen on this zoom:

 ContourPlot[func[{x, y}], {x, 0, 1}, {y, x, 1}]

Mathematica graphics

An alternative may involve something new in version 10 like

dg = g // DiscretizeGraphics;

Update

Intriguingly the following code seems to work

dat = {#[[1]], #[[2]], 
     If[#[[1]] < #[[2]], Sin[5 #[[1]] #[[2]]], 0]} & /@ 
   RandomReal[1, {2000, 2}];    
if = Interpolation[dat, InterpolationOrder -> 1];    
ContourPlot[if[x, y], {x, 0, 1}, {y, 0, 1}, Contours -> 25]

Mathematica graphics

This would suggest there is something wrong with the tab grid but it is not obvious what exactly?

$\endgroup$
  • $\begingroup$ With InterpolationOrder -> 1 I get "The element mesh has insufficient quality". I wonder if this is related to the fact that your grid is in fact regular. In v9 I don't get this, and there should be no problem. I would report this particular problem (Interpolation[tab, InterpolationOrder -> 1]) to support. As a workaround you could either try rolling your own linear interpolation (start with DelaunayMesh to break it into triangles then interpolate over each triagle), or exploiting the fact that your grid is a regular square grid ... $\endgroup$ – Szabolcs Mar 20 '15 at 15:02
  • $\begingroup$ ... padding it to fill out the missing points so you can put the data in a matrix, and use inerpolation on that matrix. It would be good to change the title of the post. This is a regular square grid on a triangular domain. It is neither an irregular grid, not a triangular one. $\endgroup$ – Szabolcs Mar 20 '15 at 15:03
  • $\begingroup$ No, it's clearly a rectangular grid. That's why the Delaunay triangulation is not unique. It can insert either diagonal to each little square to break it into triangles, and that's probably related to why interpolation fails in v10. $\endgroup$ – Szabolcs Mar 20 '15 at 15:05
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – chris Mar 20 '15 at 15:24
11
$\begingroup$

This is not a full answer, just some analysis of some of the problems we see here.


Interpolation[tab, InterpolationOrder -> 1] should work, but it fails like this:

Interpolation[tab, InterpolationOrder -> 1]

Interpolation::femimq: The element mesh has insufficient quality of -2.05116*10^-13. A quality estimate below 0. may be caused by a wrong ordering of element incidents or self-intersecting elements. >>

Interpolation::fememtlq: The quality -2.05116*10^-13 of the underlying mesh is too low. The quality needs to be larger than 0.`. >>

This is a bug introduced in version 10. It doesn't happen in version 9. Please report it to Wolfram Support.


What does InterpolationOrder -> 1 actually do behind the scenes? It constructs a Delaunay triangulation of the points and does (trivial) linear interpolation over each triangle. Let's look at the Delunay triangulation here:

DelaunayMesh[tab[[All, 1 ;; 2]]]

Mathematica graphics

You'll notice that the points are on a regular square grid. The Delaunay triangulation is not unique. Each square can be split into two triangles along either of the two diagonals. This is somehow confusing the interpolation function. If we break this degeneracy by slightly shuffling the points around, it'll work fine:

Interpolation[{#1 + RandomReal[.0001 {-1, 1}], #2 + 
     RandomReal[.0001 {-1, 1}], #3} & @@@ tab, 
 InterpolationOrder -> 1]

(* no error *)

You could use this as a practical workaround, just use very tiny displacements of the points so precision won't be affected much.


A different workaround is to exploit the regular structure of the point grid and use interpolation on a structured grid.

Let's put the $z$ values in a matrix:

mat = SparseArray[Round[10 {#1 + 0.05, #2 - 0.15}] -> #3 & @@@ tab];

MatrixPlot[mat]

Mathematica graphics

Now this works:

if = ListInterpolation[Normal[mat], {{0.05, 4.65}, {0.25, 4.85}}]

Plot3D[if[x, y], {x, y} \[Element] DelaunayMesh[tab[[All, {1, 2}]]], PlotRange -> All]

Mathematica graphics

$\endgroup$
  • $\begingroup$ Thanks: I had just tried adding small random numbers on the basis of your comments. Your workaround should do the trick for me! $\endgroup$ – chris Mar 20 '15 at 15:38
6
$\begingroup$

I will expand on Szabolcs's answer. Starting with the same triangulation, we can see that the problematic cells consist of "triangle" whose vertices are collinear. These have areas that are either negative (wrong orientation), zero, or nearly zero (below 2.*^-15). They arise no doubt from round-off error. I could not find any means of improving the precision. Rationalizing the coordinates did not help, and I assume DelaunayMesh converts everything to MachinePrecision before going to work.

dtab = DelaunayMesh[tab[[All, 1 ;; 2]]]

(* highlights the bad triangles *)
HighlightMesh[dtab, 
 Style[{2, Flatten@ Position[Chop@ PropertyValue[{dtab, 2}, MeshCellMeasure], 0]},
  EdgeForm[Directive[Thick, Red]]]]

Mathematica graphics

These cells may be deleted from the mesh. Since the goal is an interpolation over an NDSolve`FEM`ElementMesh, it seems better to proceed with FEM functions.

Needs["NDSolve`FEM`"];
emesh = ToElementMesh[
  "Coordinates" -> MeshCoordinates[dtab],
  "MeshElements" ->
   {TriangleElement@
     Pick[
      First@ Thread[MeshCells[dtab, 2], Polygon],
      Unitize[Chop@ Flatten@ PropertyValue[{dtab, 2}, MeshCellMeasure]],
      1]}
  ]
(*  ElementMesh[{{0.05, 4.65}, {0.25, 4.85}}, {TriangleElement["<" 2204 ">"]}]  *)

func = ElementMeshInterpolation[{emesh}, tab[[All, 3]]];

Plot3D[func[x, y], {x, y} ∈ func["ElementMesh"], PlotRange -> All]

Mathematica graphics

The mesh may be inspected with

emesh["Wireframe"]

Now, is it a bug? At a human level, I'd say, yes, it is certainly undesirable and seemingly avoidable. Since it used to work in earlier versions, I'd say doubly yes. The question is, When should a thin triangle on the boundary be treated as an artifact of round-off error? A nicer solution would be some sort of tolerance or precision control.

$\endgroup$
  • $\begingroup$ Thanks! This is very useful to us to study the secular evolution of galactic discs should you care to know :-) $\endgroup$ – chris Jun 16 '15 at 19:14
  • $\begingroup$ @chris You're welcome. Secular evolution of the heavens, huh? I guess it's bound to come. ;P $\endgroup$ – Michael E2 Jun 16 '15 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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