[GIS] Fast and robust open source portable script or tool for interpolation – triangulation or similar

gdalinterpolationportable-gissaga

I am looking for some fast and robust open source interpolation library/script/tool.

The goal is to re-interpolate relatively big (1M+ points) unstructured (xyz) grids into high resolution cartesian grids (tif files or other format I can process with GDAL) to produce nice smooth contours.

So far the only usable way I found is to use triangulation in saga_cmd but the more points I have the longer it takes and from some higher number it is not finished even after hours while if I do the same in other GIS software through GUI it takes only seconds to maximum few minutes.

I wanted to use GDAL but though nearest is fast, it doesn't get me detail I need and other methods took ages even for lower numbers of points… I am not sure if/how could I use GRASS. One of my requirements is that the solution must be portable (so far I used portable python, gdal and saga).

Based on answers so far:

  1. Example of data
    enter image description here

  2. gdal_fillnodata is incredibly fast but leaving spikes no matter how much smoothed, same with SAGA close gaps, where the speed is highly dependent on tension threshold, the bigger the faster
    enter image description here

  3. all (2 and nearest) gdal interpolations are not really suited for this task – nearest just takes the nearest value (not really interpolation), moving average is one step better but creates big steps not suitable for contours, the IDW is very hard to set to some reasonable results and anyway it takes too long
    enter image description here

  4. so far the best results I got are still with triangulation. Bus as I mentioned it takes long time with SAGA for middle size grids and for big it fails
    enter image description here

There are still few things I haven't tried yet or not tested properly:

Both I am not sure about the speed and will be glad for any experience or better sugestions. Thanks.

Best Answer

The legendary triangulation is available http://www.cs.cmu.edu/~quake/triangle.html

from the page:

I timed the Delaunay triangulation of 1,000,000 vertices uniformly randomly distributed in a square. The output contained 1,999,955 triangles. (I used the -I switch to suppress the rewriting of input vertices to another file, since the vertices written would be identical to the ones read. Hence, only the triangles were written to disk.)

Delaunay triangulation time: 20.761 sec
File output time: 28.794 sec
Total time (above plus file input): 56.115 sec

This has been translated to a python library according to http://dzhelil.info/triangle/index.html# which includes documentation, download https://pypi.python.org/pypi/triangle/2013.04.05 - note, these links may become dead as the version changes. I found them with google in under 10 minutes.

Related Question