python - 计算线通过的网格象限的有效方法

Question

我有一个二维单位网格和一堆以任何有理数开始和结束的线段。我需要一种有效的方法来计算线穿过哪些网格单元。例如，该行：

从 (2.1, 3.9) 到 (3.8, 4.8) 穿过具有左下点 (2, 3)、(2, 4) 和 (3, 4) 的网格单元。

有没有一种快速有效的方法来从线的端点计算这些象限？

我将在 R 中工作，但 Python 或伪代码中的答案也可以。谢谢！

Answer 1

处理空间数据的人一直在处理这类问题，因此可能值得他们的努力加以支持。这是一个使用 R 的raster包（以及它所依赖的sp包中的函数）的解决方案：

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

我会建议Bresenham 的线算法（或相关的 Wu 算法）的一些变体。这些代码在计算机图形学中广泛用于绘制线条，并且应该适应您的特定需求（例如非整数端点）。