An efficient way to calculate grid quadrants is through

Question

I have a two-dimensional unit grid and a bunch of line segments that start and end on any rational number. I need an efficient way to calculate which mesh cells pass through a line. For example, the line:

From (2.1, 3.9) to (3.8, 4.8) it passes through the grid cells with the lower left points (2, 3), (2, 4) and (3, 4).

Is there a quick and efficient way to calculate these quadrants from the endpoints of a line?

I will work in R, but a Python response or pseudo code will work too. Thanks!

Answer 1

People who work with spatial data are constantly confronted with this question, so it may be worth making friends with their efforts. Here is the solution that the R raster package uses (and the functions from the sp package it depends on):

library(raster) ## Create a SpatialLines object a <- c(2.1, 3.9) b <- c(3.8, 4.8) ## Method #1 -- Uses functions from the sp package. SL <- SpatialLines(list(Lines(list(Line(rbind(a,b))), "ab"))) ## Method #2 -- Uses readWKT() from the rgeos package. Easier to read. # library(rgeos) # string <- paste0("LINESTRING(", paste(a, b, collapse=", "), ")") # SL <- readWKT(string) ## Create a raster object m <- 10 n <- 10 mat <- matrix(seq_len(m*n), nrow = m, ncol = n) r <- raster(mat, xmn = 0, xmx = n, ymn = 0, ymx = m) ## Find which cells are intersected & get coordinates of their lower-left corners ii <- extract(r, SL, cellnumbers=TRUE)[[1]][, "cell"] floor(xyFromCell(r, ii)) # xy # [1,] 2 4 # [2,] 3 4 # [3,] 2 3 ## Confirm that this is correct with a plot image(r) plot(as(rasterize(SL, r), "SpatialPolygons"), border = "darkgrey", lwd = 2, add = TRUE) lines(SL) 

Answer 2

I would suggest some variation of the Bresenham line algorithm (or the associated Wu algorithm ). These codes are widely used in computer graphics for line drawing and should be tailored to your specific needs (for example, non-integer endpoints).