bugGNU Octave - Bugs: bug #35178, griddata: cubic interpolation not...

 
 

bug #35178: griddata: cubic interpolation not yet implemented

Submitter:  None
Submitted:  Mon 26 Dec 2011 06:51:14 PM UTC
   
 
Category:  Octave Function Severity:  1 - Wish
Priority:  1 - Later Item Group:  Feature Request
Status:  Need Info Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * dev
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 14 Apr 2020 08:49:53 PM UTC, comment #11: 

Well, at least 8 [1]. Trusting the 'not-a-knot' statement pins down the 'cubic' in 1D as s^3(x) is equal across splines endpoints. Need to make sure that's interpreted correct for 2D nodes / edges.    The 'natural' one was pretty straight forward as having 'endpoint curvatures = 0'. 

[1] https://core.ac.uk/download/pdf/35472972.pdf

Nicholas Jankowski <nrjank>
Group Member
Tue 14 Apr 2020 03:05:35 PM UTC, comment #10: 

How many boundary conditions possibilities are there?  It doesn't seem to me that there are that many choices.

Take a look at www.maths.lth.se/na/courses/FMN081/FMN081-06/lecture11.pdf, which I've attached.  They define just 4 different end conditions including "natural" and "not-a-knot" which is what they claim Matlab uses.  The first part of the algorithm for interior points might always be the same and it is only adjustment for the boundary conditions which changes with "natural" and "cubic".



(file #48834)

Rik <rik5>
Group administrator
Mon 13 Apr 2020 09:09:57 PM UTC, comment #9: 

I started looking around but didn't get very far.  Based on the matlab docs stating triangulation based and C2 continuous, I started searching, but there a quite a few options for cubic interpolation. A common one I saw does triangulation, then generates a cubic spline on each edge and does a local interpolation base on those. The key is what boundary conditions to set on the spline endpoints. And I was hoping to come across a borrow-able algorithm somewhere, but haven't yet. Not something as straightforward as the v4 algorithm. Might just have to pick one and run with it.

Nicholas Jankowski <nrjank>
Group Member
Mon 13 Apr 2020 04:33:40 PM UTC, comment #8: 

Matlab's description of "natural" and "cubic" isn't much help.  You might also take a look at the documentation for interp1.  In that case, "cubic" is the same as "pchip", which uses Hermite polynomials rather than just ordinary cubic polynomials.

As a guess, it may be that the Delaunay triangulation is used to quickly locate the 4 nearest points in the original source data to the query point and then construct a cubic spline.  This could still be a win computationally, when compared to interp2 (..., "spline"), because splines would only be created for regions with query points.  In the case of interp2, it creates a spline for every single gap between data points.

Rik <rik5>
Group administrator
Fri 20 Mar 2020 06:54:15 PM UTC, comment #7: 

correction. the QHull paper is about efficient facet generation/triangulation, not necessarily the cubic interpolation method on top of it.

Nicholas Jankowski <nrjank>
Group Member
Thu 19 Mar 2020 08:42:40 PM UTC, comment #6: 

after some searching, the report:

From: J.C. Chan, J. Ma, F. Canters "A comparison of superresolution reconstruction methods for multiangle CHRIS/Proba images", SPIE Image and Signal Processing for Remote Sensing XIV. Vol. 7109, 2008
"For the interpolation, the griddata function in
Matlab is used with the option of triangle-based cubic interpolation. This interpolation function is based on the Quickhull algorithm described in [21]"

[21] Barber, C. B., Dobkin, D.P. and Huhdanpaa, H.T., “The Quickhull Algorithm for Convex Hulls”, ACM
Transactions on Mathematical Software, 22(4), 469-483 (1996)

so, progress.

Nicholas Jankowski <nrjank>
Group Member
Wed 18 Mar 2020 02:00:05 AM UTC, comment #5: 

I've implemented the 'v4' method in response to bug #33539.  I could look at 'cubic' and 'natural' as well if someone can suggest a particular cubic model.  a quick search shows there are a couple of options depending on what matlab chose.  from the help it only says:


'cubic' Triangulation-based cubic interpolation supporting 2-D interpolation only. Continuity: C2

'natural' Triangulation-based natural neighbor interpolation supporting 2-D and 3-D interpolation. This method is an efficient tradeoff between linear and cubic. Continuity: C1 except at sample points


Nicholas Jankowski <nrjank>
Group Member
Tue 10 Mar 2020 07:47:17 PM UTC, comment #4: 

minor update: in another griddata bug (bug #57323), the pending patch updates the help text to indicate that Octave only supports the options linear and nearest, and a 'not yet implemented' error appears if methods v4, cubic, or natural are called.


Nicholas Jankowski <nrjank>
Group Member
Mon 11 Mar 2019 08:02:46 PM UTC, comment #3: 

Still same error persists; kindly review error and fix.

Ankit Jain <jain369in>
Sat 19 Nov 2016 07:58:24 PM UTC, comment #2: 

This bug is still present in Octave 4.2.0.

The function griddata.m claims to support the method "cubic" in its help text, but trying to use it results in an error message: "error: griddata: cubic interpolation not yet implemented".

A simple script to reproduce this:

xy = gallery('uniformdata',[100 2],0);
x = xy(:,1);
y = xy(:,2);
v = exp(-x.^2-y.^2);
[xq,yq] = meshgrid(-2:.5:2, -2:.5:2);
vq = griddata(x,y,v,xq,yq, "cubic");


Hartmut <hardy>
Fri 08 Jun 2012 12:42:48 AM UTC, comment #1: 

Out of curiosity, with the possible intention of implementing this feature, what type of cubic mapping is used? Splines? If I am told what type we should use, I will try to implement this version of the function.

Anonymous
Mon 26 Dec 2011 06:51:14 PM UTC, original submission:  

Using the 3.4.3 binary distribution for Windows, I receive the error:

griddata: cubic interpolation not yet implemented

when using the following:

griddata(x,y,z,xx,yy, "cubic");

According to the documentation, "cubic" is a valid parameter.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #48834:  lecture11.pdf added by rik5 (110KiB - application/pdf)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by buepro (griddata cubic)
  • -email is unavailable- added by jain369in (Posted a comment)
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by rik5 (Updated the item)
  •  

    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 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-04-14 rik5 Attached File- Added lecture11.pdf, #48834
    2019-09-14 buepro Carbon-Copy- Added -email is unavailable-
    2019-03-11 mtmiller Carbon-CopyRemoved 80942 -
    2015-03-14 mtmiller Priority2 1 - Later
    2014-01-06 mtmiller CategoryNone Octave Function
        Severity3 - Normal 1 - Wish
        StatusNone Need Info
        Release3.4.3 dev
        Operating SystemMicrosoft Windows Any
    2012-01-08 rik5 Priority5 - Normal 2
        Item GroupOther Feature Request

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code