Pierre Roudier wrote:
Dear list,
I am processing gridded data like DEMs, imported in R from geotiff
files. Of course, such data is regularly gridded, but very often with
NA values. In the framwork of some tests, I have to generate a
neighbourhood of the DEM, so that to extract local extrema of the
layer. For this task, I wrote a function based on the knearneig()
function from the spdep package, with k=4 or k=8, to generate and
analyse the neighbourhood of each point.
Unfortunately, I often have to process big datasets (let's say grids
with between 50,000 and 350,000 points), and that's working but
knearneigh() takes *hours* to process.
Does anybody would have any suggestion to improve the efficiency of this step ?
the algorithm (knn.c file in the spdep sources) seems to compute all
distances between all grid cells, and for each grid cell find the
nearest k by some kind of insertion sort. That makes it general for all
kinds of spatial data points, including irregularly spread ones, but
makes it also inefficient (because O(n^2) with n the number of grid
cells) for large data sets.
Suggestions to improve this would be to use an index structure (for the
generic case of possibly irregularly spread data) such as the PR-bucket
quadtree used in package gstat (nsearch.c), or specifically for gridded
data to write a special knearneigh() that exploits the grid indexing
already present: you can explicitly address the nearest 4/8/12/...
neighbours by using row/col indexes. In this latter case you'd probably
want to rewrite the test function for the full grid, instead of looping
over the cells.
Thanks,
Pierre
_______________________________________________
R-sig-Geo mailing list
[email protected]
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
--
Edzer Pebesma
Institute for Geoinformatics (ifgi), University of Münster
Weseler Straße 253, 48151 Münster, Germany. Phone: +49 251
8333081, Fax: +49 251 8339763 http://ifgi.uni-muenster.de
http://www.52north.org/geostatistics [email protected]
_______________________________________________
R-sig-Geo mailing list
[email protected]
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
