Opened 9 years ago
Closed 9 years ago
#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)
Change History (16)
by , 9 years ago
Attachment: | gdal_grid_invdistnn_20150715.patch added |
---|
comment:1 by , 9 years ago
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.
by , 9 years ago
Attachment: | gdal_utilities_dox_invdistnn_20150716.patch added |
---|
Patch to document invdistnn in apps/gdal_utilities.dox
by , 9 years ago
Attachment: | test_gdal_grid.py_invdistnn_20150716.patch added |
---|
Patch to test_gdal_grid to add test 12 for invdistnn
by , 9 years ago
Attachment: | grid_invdistnn.tif added |
---|
utilities/ref_data/grid_invdistnn*tif reference testing data
by , 9 years ago
Attachment: | grid_invdistnn_250_8minp.tif added |
---|
utilities/ref_data/grid_invdistnn*tif reference testing data
by , 9 years ago
Attachment: | grid_invdistnn_250_10maxp_3pow.tif added |
---|
utilities/ref_data/grid_invdistnn*tif reference testing data
comment:3 by , 9 years ago
Cc: | added |
---|
comment:4 by , 9 years ago
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 ?
follow-up: 6 comment:5 by , 9 years ago
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 by , 9 years ago
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
by , 9 years ago
Attachment: | gdal_grid_invdistnn_20150720.patch added |
---|
Implementation of "invdistnn" for gdal_grid. This patch replaces gdal_grid_invdistnn_20150715.patch
comment:7 by , 9 years ago
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 by , 9 years ago
comment:9 by , 9 years ago
Resolution: | → fixed |
---|---|
Status: | new → closed |
Implementation of "invdistnn" for gdal_grid