Efektywny sposób obliczania kwadrantów kwadratu, linia przechodzi przez

Question

Mam dwuwymiarową siatkę jednostek i kilka segmentów linii, które rozpoczynają się i kończą na dowolnej liczbie wymiernej. Potrzebuję skutecznego sposobu obliczania, które komórki siatki przechodzi przez linię. Na przykład linia:

Od (2.1, 3.9) do (3.8, 4.8) przechodzi przez komórki siatki z dolnymi lewymi punktami (2, 3), (2, 4) i (3, 4).

Czy istnieje szybki i skuteczny sposób obliczenia tych kwadrantów z punktów końcowych linii?

Będę pracował w R, ale zadziała również odpowiedź w Pythonie lub pseudokod. Dzięki!

Answer 1

Ludzie, którzy pracują z danymi przestrzennymi, przez cały czas zajmują się tego rodzaju pytaniami, więc może warto wspierać ich wysiłki. Oto rozwiązanie, które wykorzystuje rastrowych pakiet R (oraz funkcji z sp pakietu, od której zależy):

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)) 
#  x y 
# [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

Proponuję jakiś wariant Bresenham's line algorithm (lub powiązany z nim Wu's algorithm). Kody te są szeroko stosowane w grafice komputerowej do rysowania linii i powinny być dostosowane do twoich potrzeb (takich jak niecałkowite punkty końcowe).