[R-sig-Geo] Need fast method to find indices of cells in a 3-D grid that contain (x, y, z) coordinates

[Waichler, Scott R]

Thanks to Michael Sumner and Brian Gregor for suggesting solutions.  I
ended up using findInterval() as suggested by Brian and an index array
to get what I need.  I couldn't figure out how to use apply() with my
grid having irregular cell sizes.  Here is my code now, which runs much
faster than the previous code, which had multiple-component which()
calls and an explicit loop.

# Number the cells in the 3-D array.
cell.id <- array(1:num.nodes, dim = c(num.x,num.y,num.z))

# Get the numbers of the grid cells containing the coordinates x, y, z.
# x, y, z are the coordinates I want to look up.  
# xnb, ynb, and znb are the boundaries of the cells in the x, y, and z 
# directions, respectively.  
i.ind <- findInterval(x, xnb, all.inside = T)
j.ind <- findInterval(y, ynb, all.inside = T)
k.ind <- findInterval(z, znb, all.inside = T)
index.array <- array(c(i.ind, j.ind, k.ind), dim=c(length(x), 3))
ind.nb <- cell.id[index.array]  # the numbers of the cells I want

Regards,
Scott Waichler
Pacific Northwest National Laboratory
Richland, Washington, USA


> -----Original Message-----
> From: Waichler, Scott R 
> Sent: Thursday, August 16, 2007 3:01 PM
> To: 'R-sig-geo at stat.math.ethz.ch'
> Subject: Need fast method to find indices of cells in a 3-D 
> grid that contain (x,y,z) coordinates
> 
> I am looking for a fast method that will find the indices of 
> cells of a 3-D grid that contain a set of (x,y,z) 
> coordinates.  The grid has I,J,K number of cells in the x-, 
> y-, and z- directions, respectively.  The cells are numbered 
> with integers 1:(I*J*K).  I have multiple sets of coordinates 
> (points in 3-D space) for which I want to rapidly look up the 
> numbers of the cells that contain them.  Here is an example 
> of what I am trying to do, with an explicit loop that 
> evaluates each point separately.  Is there a faster way that 
> can do the whole set of points at once?