グリッド象限を計算する効率的な方法は、行が通過する

Question

私は2次元単位格子と任意の有理数で始まりそして終わる線分の束を持っています。ラインが通過するグリッドセルを計算する効率的な方法が必要です。たとえば、行：

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

ラインのエンドポイントからこれらの象限を計算するための迅速、効率的な方法はありますか？

私はRで作業することがありますが、Pythonや擬似コードで答えがあまりにも動作します。ありがとう！

Answer 1

人々。ここでは（それが依存しているSPパッケージと機能）Rのラスタパッケージを使用するソリューションです：

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's line algorithm（または関連Wu's algorithm）のいくつかのバリエーションをお勧めします。これらのコードは、線を描くためにコンピュータグラフィックスで広く使用されており、特定のニーズ（非整数のエンドポイントなど）に適応できる必要があります。それは彼らの努力の上にピギーバッキング価値があるかもしれので、質問のこの種のすべての時間と空間データの契約で作業