bugGNU Octave - Bugs: bug #50494, griddata loses precision in the...

 
 

bug #50494: griddata loses precision in the linear interpolation of 3 column vectors (using Delaunay triangles)

Submitter:  El Colmo <elcolmo>
Submitted:  Wed 08 Mar 2017 04:48:24 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
Status:  Fixed Assigned to:  None
Originator Name:  Colmo Open/Closed:  * Closed
Release:  * 4.2.1 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 31 Jan 2020 01:48:18 AM UTC, comment #8: 

Fixed the issue in this changeset: https://hg.savannah.gnu.org/hgweb/octave/rev/2e6dc7e2b191.

For 2-D input, Octave now does a first attempt with the more precise options of "Qt Qbb Qc".  If, for some reason, that fails then Octave repeats the call to QHull with the option set "Qt Qbb Qc Qz" to add a point at infinity.

Rik <rik5>
Group administrator
Thu 30 Jan 2020 11:48:39 PM UTC, comment #7: 

It turns out that Matlab also produces the same error from QHull for 2-D input.  So, we're compatible ;).

I'm going to implement a solution by having three sets of QHull options for

ndims = 2
ndims = 3
ndimms >=4

Rik <rik5>
Group administrator
Tue 17 Dec 2019 06:59:46 PM UTC, comment #6: 

Unfortunately that is a potential outcome.  I wonder how Matlab handles this?

One approach might be to do a try/catch and add the extra 'Qz' option if Qhull determines that the particular problem requires it.

Rik <rik5>
Group administrator
Tue 17 Dec 2019 06:46:41 PM UTC, comment #5: 

After 25f914321e7b, I'm seeing the following test failure:


octave:> test griddatan
QH6239 Qhull precision error: Initial simplex is cocircular or cospherical.  Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points.  Option 'Qz' adds a point "at infinity".    Use option 'Qs' to search all points for the initial simplex.

While executing:  | qhull d Qt Qbb Qc
Options selected for Qhull 2015.2 2016/01/18:
  run-id 253565979  delaunay  Qtriangulate  Qbbound-last  Qcoplanar-keep
  _pre-merge  _zero-centrum  Qinterior-keep  Pgood  _max-width  1
  Error-roundoff 1.4e-15  _one-merge 9.7e-15  Visible-distance 2.8e-15
  U-coplanar-distance 2.8e-15  Width-outside 5.5e-15  _wide-facet 1.7e-14
***** testif HAVE_QHULL <56515>
 x = [ 0, 0; 1, 1; 0, 1; 1, 0 ];
 y = [ 1; 2; 3; 4 ];
 xi = [ .5, .5 ];
 yi = griddatan (x, y, xi);
!!!!! known bug: https://octave.org/testfailure/?56515
__delaunayn__: qhull failed
PASSES 2 out of 3 tests (1 known bug)


John W. Eaton <jwe>
Group administrator
Mon 16 Dec 2019 10:45:15 PM UTC, comment #4: 

I checked in a patch to update the underlying options passed to Qhull for 2-D and 3-D cases.  See https://hg.savannah.gnu.org/hgweb/octave/rev/25f914321e7b.

These options are now the same ones used by Matlab, although they differ from NumPy which also adds "Qz".

Marking as fixed and closing report.

Rik <rik5>
Group administrator
Tue 29 Aug 2017 09:30:21 PM UTC, comment #3: 

For the example given in testcase.m, it seems that only {"Qt", "Qbb", "Qc"} has a siginificant effect, so I suppose we should use that?

John W. Eaton <jwe>
Group administrator
Fri 10 Mar 2017 01:38:07 PM UTC, comment #2: 

Sure. Please see the attachments. There is noticeable triangulation (lack of precision) in the un-patched griddata results, compared to the patched results.

(file #39957,

El Colmo <elcolmo>
Fri 10 Mar 2017 05:05:21 AM UTC, comment #1: 

Do you have sample code that demonstrates the problem?  It is important that we be able to verify that the suggested change works.

Rik <rik5>
Group administrator
Wed 08 Mar 2017 04:48:24 PM UTC, original submission:  

The griddata function loses precision when calculating the linear interpolation of 3 column vectors (using Delaunay triangles), since only the x and y parameters are passed to "delaunay" (ie, using the default QHull options). This results in triangle elimination in "delaunay".  When the generated (reduced) set of triangles is searched by "tsearch", the resultant interpolated value is less precise than expected.

The fix is trivial - to change the parameters passed to "delaunay", so that the default QHull options are no longer used, resulting in no triangle elimination by "delaunay", resulting in greatly increased precision of the interpolated values.

The fix is trivial. In Change the following line (in "/usr/share/octave/4.0.3/m/geometry/griddata.m", in my deployment) from:

tri = delaunay (x, y);

to either..

tri = delaunay (x, y, {"Qt", "Qc", "Qz"});   #remove default option Qbb, in order to slightly increase precision (by increasing the triangle count)

or...

tri = delaunay (x, y, {"Qt", "Qbb", "Qc"});   #remove default option Qz, in order to greatly increase precision (by increasing the triangle count)


Note: this is also an issue in the latest available version of Octave (4.2.1).

El Colmo <elcolmo>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #39957:  testcase.m added by elcolmo (99KiB - text/x-objcsrc - Testcase, raw data plotted, and results of griddata (with and without fix) plotted)
file #39958:  Screenshot from 2017-03-10 13-23-52.png added by elcolmo (161KiB - image/png - Testcase, raw data plotted, and results of griddata (with and without fix) plotted)
file #39959:  Screenshot from 2017-03-10 13-23-49.png added by elcolmo (87KiB - image/png - Testcase, raw data plotted, and results of griddata (with and without fix) plotted)
file #39960:  Screenshot from 2017-03-10 13-24-23.png added by elcolmo (191KiB - image/png - Testcase, raw data plotted, and results of griddata (with and without fix) plotted)

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by elcolmo (Submitted the item)
  • -email is unavailable- added by elcolmo
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 12 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-01-30 mtmiller Dependencies- bugs #57468 is dependent
    2019-12-16 rik5 Dependencies- bugs #57399 is dependent
    2019-12-16 rik5 StatusNeed Info Fixed
        Open/ClosedOpen Closed
    2017-08-29 jwe StatusPatch Submitted Need Info
    2017-03-13 rik5 StatusNeed Info Patch Submitted
    2017-03-10 elcolmo Attached File- Added testcase.m, #39957
        Attached File- Added Screenshot from 2017-03-10 13-23-52.png, #39958
        Attached File- Added Screenshot from 2017-03-10 13-23-49.png, #39959
        Attached File- Added Screenshot from 2017-03-10 13-24-23.png, #39960
    2017-03-10 rik5 StatusNone Need Info
    2017-03-08 elcolmo Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code