# [Gdal-dev] Algorithm Development

Frank Warmerdam warmerdam at pobox.com
Mon Sep 8 23:22:11 EDT 2008

```Fodder wrote:
>
>
> Frank Warmerdam-2 wrote:
>>
>> - An algorithm for interpolation in regions of a raster.
>>
>>
>
> Hi Frank,
>
> Happy to hear about your research. I'm interested in the interpolation in
> regions of a raster algorithm. In particular:
> - What interpolation methods with be supported?

Fodder,

A simple "four quadrant inverse distance" interpolation is used.  That is,
I find the closest valid pixel for each of the four quadrants and then
mix them based on inverse distance weighting.

Then I apply some number of 3x3 average filtering in the interpolated areas
to smooth out various artifacts somewhat.

While this approach has a number of problems, I feel it is suitable for
use in a variety of circumstances, including sparse data (such as might
be the result of burning a bunch of known sample points into a raster),
holes in data (such as SRTM or interferometry DEM holes), or to interpolate
in data after burning contours into a raster.

This is in contrast to approaches such as the spline interpolation in
GRASS which produces (presumably) superior results when interpolating in
modest sized holes in rasters but that does not scale well to sparse data
or to large empty regions like with contours.

> - What vector sources will be supported (if any) (points only, or polyline
> polygon etc)?

The fill algorithm does not directly use vector data.  If you want to produce
raster data by interpolating from vectors you would need to first use
gdal_rasterize to turn the vectors into a raster, and then use the fill
program/functions to interpolate in the holes.  I believe someone
(Andrey? Even?) has been improving gdal_rasterize to support additional
data types.

> - Will it be incorporated in Gdal_Grid?

No.  I'm only moderately familiar with gdal_grid but my understanding
is that it does not scale particularly well to handling huge numbers of
points to interpolate from.  But generally speaking gdal_grid will still
be much superior for interpolating reasonable amounts of point data
to build a raster.

> - When you say regions, do you mean vector polygons or raster zones?

Raster zones.

Note that this algorithm is already in trunk as the function
GDALFillNodata().  However, I've had some problems with the post
fill smoothing filtering and haven't really finished cleaning things
up and documenting them.

Best regards,
--
---------------------------------------+--------------------------------------
I set the clouds in motion - turn up   | Frank Warmerdam, warmerdam at pobox.com
light and sound - activate the windows | http://pobox.com/~warmerdam
and watch the world go round - Rush    | Geospatial Programmer for Rent

```