[R-sig-Geo] cell2nb

[Roger Bivand]

On Mon, 21 Jun 2010, Nikhil Kaza wrote:

> While answering a question on R-help, I was monkeying with the code in 
> cell2nb  in spdep (5.11) to see if it can be made faster.
>
> Getting rid of the for loop and replacing with lapply and apply only 
> marginally improves the performance
>
> n <- nrow*ncol
>   for (i in 1:n) {
>       res[[i]] <- sort(mrc2vi(xcell(vi2mrc(i, nrow, ncol),
>           nrow, ncol, torus), nrow, ncol))
>       rownames[i] <- paste(vi2mrc(i, nrow, ncol), collapse = ":")
>   }
>
> However, I do not understand why the loop has to run through 1:n. If the 
> adjacency matrix is symmertic, should we not just make ceil[n/2] comparisons 
> and take advantage of its symmetry? Am I missing something? Not sure if it 
> makes it any faster though.
>

The reason why cell2nb() was written was originally to provide a way of 
generating neighbours for grids on a torus, which is hard to do for 
coordinates of a planar grid. These are typically needed to simulate 
processes without edge effects, for modest grid sizes. Agreed, neighbours 
in grids are symmetric, but an "nb" object contains both symmetric links 
for generality (the "neig" class in ade4 does not), so these would have to 
be added in afterwards. Typically, dnearneigh() with the step distance as 
its threshold generates rook neighbours in acceptable time, with the 
diagonal distance it yields queen neighbours:

> library(spdep)
> system.time(res <- cell2nb(10, 10))
    user  system elapsed
   0.099   0.000   0.099
> system.time({grd <- GridTopology(c(0,0), c(1,1), c(10,10));
+ resd <- dnearneigh(coordinates(grd), 0, 1)})
    user  system elapsed
   0.003   0.000   0.002
> all.equal(res, resd, check.attributes=FALSE)
[1] TRUE
> system.time(res <- cell2nb(50, 50))   user  system elapsed
   2.404   0.001   2.407
> system.time({grd <- GridTopology(c(0,0), c(1,1), c(50,50));
+ resd <- dnearneigh(coordinates(grd), 0, 1)})
    user  system elapsed
   0.267   0.000   0.267
> all.equal(res, resd, check.attributes=FALSE)[1] TRUE
> system.time(res <- cell2nb(100, 100))   user  system elapsed
   9.817   0.003   9.872
> system.time({grd <- GridTopology(c(0,0), c(1,1), c(100,100));
+ resd <- dnearneigh(coordinates(grd), 0, 1)})
    user  system elapsed
   4.125   0.001   4.127
> all.equal(res, resd, check.attributes=FALSE)[1] TRUE

It degrades but not as fast, and may be speeded up using rgeos soon (using 
a spatial index on the points to cherry-pick, rather than brute-force as 
now).

Roger


>
>
>
> Nikhil Kaza
> Asst. Professor,
> City and Regional Planning
> University of North Carolina
>
> nikhil.list at gmail.com
>
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at stat.math.ethz.ch
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo

-- 
Roger Bivand
Economic Geography Section, Department of Economics, Norwegian School of
Economics and Business Administration, Helleveien 30, N-5045 Bergen,
Norway. voice: +47 55 95 93 55; fax +47 55 95 95 43
e-mail: Roger.Bivand at nhh.no