#6038 closed enhancement (fixed)

New gdal_grid interpolation algorithm

Reported by: mckelvym Owned by: warmerdam
Priority: normal Milestone: 2.1.0
Component: Algorithms Version: svn-trunk
Severity: normal Keywords: IDW, Inverse Distance Weighting, Nearest Neighbor, ArcPy, ESRI
Cc: Even Rouault

Description

Hello,

I would like to contribute the attached patch for a new algorithm to be included in gdal_grid. This algorithm option, "invdistnn", is a variation on the existing inverse distance weighting algorithm with the following features:

  • Use a quadtree to search for points only in the neighborhood (within radius) of each grid cell. This dramatically improves on the time to produce an interpolated grid since it is not examining the entire point space like "invdist"
  • Retains up to "max_points" nearest cells instead of arbitrarily the first "max_points + 1" cells

This implementation will produce interpolated grids that match the output of ESRI's ArcPy? arcpy.gp.Idw_sa method.

The affected files are:

  • alg/gdal_alg.h
  • alg/gdalgrid.cpp
  • alg/gdalgrid.h
  • apps/gdal_grid.cpp

Attachments (7)

gdal_grid_invdistnn_20150715.patch (16.9 KB) - added by mckelvym 21 months ago.
Implementation of "invdistnn" for gdal_grid
gdal_utilities_dox_invdistnn_20150716.patch (1.2 KB) - added by mckelvym 21 months ago.
Patch to document invdistnn in apps/gdal_utilities.dox
test_gdal_grid.py_invdistnn_20150716.patch (7.7 KB) - added by mckelvym 21 months ago.
Patch to test_gdal_grid to add test 12 for invdistnn
grid_invdistnn.tif (3.5 KB) - added by mckelvym 21 months ago.
utilities/ref_data/grid_invdistnn*tif reference testing data
grid_invdistnn_250_8minp.tif (3.5 KB) - added by mckelvym 21 months ago.
utilities/ref_data/grid_invdistnn*tif reference testing data
grid_invdistnn_250_10maxp_3pow.tif (3.5 KB) - added by mckelvym 21 months ago.
utilities/ref_data/grid_invdistnn*tif reference testing data
gdal_grid_invdistnn_20150720.patch (17.4 KB) - added by mckelvym 21 months ago.
Implementation of "invdistnn" for gdal_grid. This patch replaces gdal_grid_invdistnn_20150715.patch

Download all attachments as: .zip

Change History (16)

Changed 21 months ago by mckelvym

Implementation of "invdistnn" for gdal_grid

comment:1 Changed 21 months ago by Even Rouault

I didn't actually try it, but it looks good to me. It would also be necessary to document the new alg in apps/gdal_utilities.dox. And having a new test case in autotest/utilities/test_gdal_grid.py would be great also.

Changed 21 months ago by mckelvym

Patch to document invdistnn in apps/gdal_utilities.dox

Changed 21 months ago by mckelvym

Patch to test_gdal_grid to add test 12 for invdistnn

Changed 21 months ago by mckelvym

Attachment: grid_invdistnn.tif added

utilities/ref_data/grid_invdistnn*tif reference testing data

Changed 21 months ago by mckelvym

utilities/ref_data/grid_invdistnn*tif reference testing data

Changed 21 months ago by mckelvym

utilities/ref_data/grid_invdistnn*tif reference testing data

comment:2 Changed 21 months ago by mckelvym

Please let me know if there is anything else. Thanks.

comment:3 Changed 21 months ago by mckelvym

Cc: Even Rouault added

comment:4 Changed 21 months ago by Even Rouault

I'm middly enthousiastic in seeing computed fields in GDALGridInverseDistanceToAPowerNearestNeighborOptions such as dfPowerDiv2PreComp, dfRadiusPower2PreComp and dfRadiusPower4PreComp. Cannot they just be computed in GDALGridInverseDistanceToAPowerNearestNeighbor() ? If their precomputation really improve performance, couldn't those value be passed with the hExtraParamsIn structure ?

Last edited 21 months ago by Even Rouault (previous) (diff)

comment:5 Changed 21 months ago by mckelvym

Yes, these could be computed in GDALGridInverseDistanceToAPowerNearestNeighbor(), but since they are grid cell invariant, it is smarter to compute them in advance. I think hExtraParamsIn may be a better place to introduce this, as you suggest.

The motivation for computing them in advance is a dataset I am working with that has 29 million grid cells -- these extra multiplications * 29+ million is wasted cpu time.

Do you suggest I make these modifications to move dfPowerDiv2PreComp, dfRadiusPower2PreComp, and dfRadiusPower4PreComp from the structure GDALGridInverseDistanceToAPowerNearestNeighborOptions to this structure (GDALGridExtraParameters) instead? If so, I can submit a new patch to use instead of the first one.

Thanks

comment:6 in reply to:  5 Changed 21 months ago by Even Rouault

Do you suggest I make these modifications to move dfPowerDiv2PreComp, dfRadiusPower2PreComp, and dfRadiusPower4PreComp from the structure GDALGridInverseDistanceToAPowerNearestNeighborOptions to this structure (GDALGridExtraParameters) instead? If so, I can submit a new patch to use instead of the first one.

Yes, that would be better

Changed 21 months ago by mckelvym

Implementation of "invdistnn" for gdal_grid. This patch replaces gdal_grid_invdistnn_20150715.patch

comment:7 Changed 21 months ago by mckelvym

rouault, please see attachment:gdal_grid_invdistnn_20150720.patch which contains the changes described above. Use this one instead of gdal_grid_invdistnn_20150715.patch

Note: This patch was generated against [29540].

comment:8 Changed 21 months ago by Even Rouault

trunk r29541, r29542 "gdal_grid: add invdistnn algorithm, variation on the existing inverse distance weighting algorithm with quadtree to search for points only in the neighborhood (patch by mckelvym, #6038)"

comment:9 Changed 20 months ago by Even Rouault

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.