[Numpy-discussion] adaptive interpolation on a regular 2d grid

[denis bzowy]

Folks,
  here's a simple adaptive interpolator;
drop me a line to chat about it

    adalin2( func, near, nx=300, ny=150, xstep=32, ystep=16,
        xrange=(0,1), yrange=(0,1), dtype=np.float, norm=abs )

Purpose:
    interpolate a function on a regular 2d grid:
    take func() where it changes rapidly, bilinear interpolate where it's smooth.

Keywords:
    adaptive interpolation, recursive splitting, bilinear, Python, numpy

Example:
    x,y,z = adaline( ... )
    fig = pylab.figure()
    ax = mpl_toolkits.mplot3d.Axes3D( fig )
    X, Y = np.meshgrid( x, y )
    ax.plot_wireframe( X, Y, z, rstride=5, cstride=5 )

Out:  x,y,z = adalin2( ... )
    x = linspace( xrange[0], xrange[1], nx' )  # nx' = nx + a bit, see below
    y = linspace( yrange[0], yrange[1], ny' )
    z[ny'][nx'] some func(), some interpolated values
        
In:
    func( x, y ):
        a scalar or vector function
    nx=300, ny=150:
        the output array z[][] is this size, plus a bit.  For example,
        with nx=300, ny=150, xstep=32, ystep=16, z will be 161 x 321 (up to
z[160][320])
        so that 32 x 16 tiles fit exactly in z.
    xstep=32, ystep=16:
        the size of the initial coarse grid, z[::ystep][::xstep] = func( x, y ).
        These must be powers of 2 (so that the recursive splitting works).
    near = .02 * fmax
        is either a number for absolute error,
        or a callable function, near( x, y, f(x,y), av4 ) -> True if near enough.
    norm:
        if func() is vector-valued, supply e.g. norm=np.linalg.norm
    more=1:
        return [x,y,z, percent func eval, ...] 

How it works:
    Initially, sample func() at a coarse xstep x ystep grid:
        increase nx, ny to nx', ny' if need be
        z = array((ny', nx'))
        z[::ystep][::xstep] = func( x, y )

    If near=infinity, just bilinear-interpolate all the other points.
    else
        for each xstep x ystep rectangle
            if average func( 4 corners ) is near func( midpoint )
                fill it with bilinear-interpolated values
            else
                split the rectangle on its longer dimension,
                recurse.

Dependencies: numpy

Notes:
    One can interpolate (blend, tween) just about anything:
    colors in a color space, or musical sounds, or curves ...

Song: Sweet Adeline