計算一條直線穿過的網格象限的有效方法

我有一個2維的單位網格，以及一堆以任意有理數開始和結束的線段。我需要一種有效的方法來計算線路經過的網格單元。例如，線條：計算一條直線穿過的網格象限的有效方法

從（2.1,3.9）到（3.8,4.8）通過具有左下點（2,3），（2,4）和（3,4）的網格單元。

有沒有一種快速有效的方法來計算線路端點上的這些象限？

我將在R工作，但Python或僞代碼的答案也可以。謝謝！

來源

2012-12-11 Bonnie Scott

你大概平均網格*細胞*代替*象限*。 – lhf

謝謝是的，你可以稱它們爲細胞。有什麼建議麼？ –

http://stackoverflow.com/questions/11694886/traverse-a-2-5d-grid的可能重複（忽略z部分）。 – lhf

從事空間數據工作的人一直都在處理這類問題，因此可能值得他們的努力捎帶。下面是一個使用的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)

enter image description here

來源

2012-12-11 02:50:36

謝謝喬希效果不錯！ –

不錯，我不知道提取可以做到這一點，它挑出所有的細胞，並似乎處理零長度的行也行。 – mdsumner

@mdsumner - 很高興知道這一點，但我並不感到驚訝：**柵格**是一個非常精心構建的軟件包，ennit？ –

我會建議一些Bresenham's line algorithm（或相關的Wu's algorithm）的變體。這些代碼廣泛用於計算機圖形繪製線條，並應適應您的特定需求（如非整數端點）。

來源

2012-12-11 02:27:49 Blckknght

Bresenham的算法沒有找到該段穿過的所有單元格。 – lhf

嗨，儘管據我所知佈雷森漢姆並沒有得到這條線經過的每一個細胞，吳的細胞比直接通過細胞的細胞更多。 –

我認爲很容易修改其中的一個或兩個工作。例如，在Brasenham's中，您可以在每次增加y時標記兩個像素（除非該線完全通過四個單元格之間的角）。我將嘗試在Python中制定一個實現。 – Blckknght

計算一條直線穿過的網格象限的有效方法

回答

相關問題