python - ラインが通過するグリッド象限を計算する効率的な方法

Question

2次元の単位グリッドと、任意の有理数で開始および終了する一連の線分があります。ラインが通過するグリッドセルを計算する効率的な方法が必要です。たとえば、次の行です。

（2.1、3.9）から（3.8、4.8）までは、左下の点（2、3）、（2、4）、および（3、4）を持つグリッドセルを通過します。

ラインの端点からこれらの象限を計算するための迅速で効率的な方法はありますか？

私はRで作業しますが、Pythonまたは擬似コードでの回答も機能します。ありがとう！

Answer 1

空間データを扱う人々は常にこの種の質問に対処するので、彼らの努力に便乗する価値があるかもしれません。Rのラスターパッケージ（およびそれが依存する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

ブレゼンハムのラインアルゴリズム（または関連するウーのアルゴリズム）のいくつかの変形を提案します。これらのコードは、線を描くためにコンピュータグラフィックスで広く使用されており、特定のニーズ（非整数のエンドポイントなど）に適応できる必要があります。