ग्रिड क्वाड्रंट्स की गणना करने के लिए कुशल तरीका

Question

के माध्यम से एक लाइन गुजरता है मेरे पास 2-आयामी यूनिट ग्रिड है, और रेखा खंडों का एक गुच्छा है जो किसी भी तर्कसंगत संख्या से शुरू होता है और समाप्त होता है। लाइन की गुजरने वाली ग्रिड कोशिकाओं की गणना करने के लिए मुझे एक कुशल तरीका चाहिए। उदाहरण के लिए, रेखा:

(2.1, 3.9) से (3.8, 4.8) नीचे बाएं बिंदुओं (2, 3), (2, 4), और (3, 4) वाले ग्रिड कोशिकाओं के माध्यम से गुजरता है।

क्या लाइन के अंतराल से इन चतुर्भुजों की गणना करने का एक त्वरित, प्रभावी तरीका है?

मैं आर में काम कर रहा हूं, लेकिन पायथन या छद्म कोड में एक जवाब भी काम करेगा। धन्यवाद!

Answer 1

लोग जो इस तरह के प्रश्न के साथ स्थानिक डेटा सौदे के साथ काम करते हैं, इसलिए यह उनके प्रयासों पर पिग्गी-बैकिंग के लायक हो सकता है। यहाँ एक समाधान (एसपी पैकेज जिस पर यह निर्भर करता है से और कार्यों) आर के रेखापुंज पैकेज का उपयोग करता है है:

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) के कुछ संस्करण का सुझाव दूंगा। उन कोडों को व्यापक रूप से लाइनों को आकर्षित करने के लिए कंप्यूटर ग्राफिक्स में उपयोग किया जाता है और आपकी विशिष्ट आवश्यकताओं (जैसे गैर-पूर्णांक अंतराल) के अनुकूल होना चाहिए।