[gdal-dev] The slowness of gdal_grid

[Even Rouault]

Tamas,

yes I believe it provides an additionnal performance increment as 
GDALGridInverseDistanceToAPower iterates over the whole set of OGR points 
even if it rejects most of them when it tests whether they are in the ellipse 
or not

The approach in the patch goes further. It starts by making a quadree with all 
the OGR points that are in the neighbourhood of the GDAL block processed by 
GDALGridCreateFromOGRLayer. For that search to be efficient, a spatial 
indexed OGR layer is recommanded.
Then for each cell of the grid in the GDAL block, you define a radius of 
influence (number of neighbour grid cells) to restrict the number of points 
that are going to be taken into account by the interpolation function. 
Fetching those points in the quadtree is very fast.

This approach works well when you are sure that you don't have to take into 
account points that are far from the cell to be interpolated.

Le Friday 31 October 2008 22:32:59 Tamas Szekeres, vous avez écrit :
> Even,
>
> Does this approach provide a significant performance increment
> comparing to the search ellipse option in the inverse distance
> algorithm?
>
> When I've been recently playing with gdal_grid I could gain further
> increment by reducing the number of the floating point operations in
> the inner loop of the algorithm (see
> GDALGridInverseDistanceToAPowerNoSearch for example), like:
>
> 1. Getting out the dfSmoothing * dfSmoothing multiplication from the loop
> 2. In case when dfPower = 2 we could save using of sqrt and pow at all.
> 3. Replace CPLIsEqual with a faster approach
>
> It must be noted that I had no chance to rely on the assumption that
> the distant points doesn't affect the value of the result, especially
> when the points are based on non-geograpic related quantities.
>
> Best regards,
>
> Tamas
>
> 2008/10/31 Even Rouault <even.rouault at mines-paris.org>:
> > Ari,
> >
> > the slowness of gdal_grid when fed with a big number of point features is
> > a known issue. See ticket #2411. I had attached a patch to speed up the
> > process. You could give it a try.
> >
> > Le Friday 31 October 2008 08:09:11 Ari Jolma, vous avez écrit :
> >> I'm doing some laser scanning data -> geotiff interpolations and I'm
> >> finding that they take some time - the current run has been going on for
> >> ~20 hours now.
> >>
> >> The current run is for a 3 by 2 kilometer area, which I'm interpolating
> >> into a raster with 1 m x 1 m cells. The data is in PostGIS but it
> >> shouldn't matter:
> >>
> >> gdal_grid -a invdist:radius1=10:radius2=10 -txe 3350505 3353786 -tye
> >> 6692068 6694105 -outsize 3281 2037 -of GTiff -ot Float32 -l nummela
> >> PG:dbname=nummela nummela.tiff
> >> Grid data type is "Float32"
> >> Grid size = (3281 2037).
> >> Corner coordinates = (3350504.500000 6694105.500000)-(3353786.500000
> >> 6692067.500000).
> >> Grid cell size = (1.000000 1.000000).
> >> Source point count = 2588809.
> >> Algorithm name: "invdist".
> >> Options are
> >> "power=2.000000:smoothing=0.000000:radius1=10.000000:radius2=10.000000:a
> >>ngl e=0.000000:max_points=0:min_points=0:nodata=0.000000"
> >>
> >> Any ideas how to make things faster? I did a interpolation to 2 m x 2 m
> >> raster earlier, which was faster but not very fast either.
> >>
> >> Best regards,
> >>
> >> Ari
> >>
> >> _______________________________________________
> >> gdal-dev mailing list
> >> gdal-dev at lists.osgeo.org
> >> http://lists.osgeo.org/mailman/listinfo/gdal-dev
> >
> > _______________________________________________
> > gdal-dev mailing list
> > gdal-dev at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/gdal-dev