I would like to thank you very much for making this clear. It seems that the 
solution you suggested is right one as the second attempt does find all the 
cells that are touched.
Now I ll try to find out how much the line gets into one of this cell as every 
cell affects acts like a weight. The more you are in a cell the higher the 
weight will be.

Best Regards
Alex




________________________________
From: David Winsemius <dwinsemius@comcast.net>

Cc: Rhelp list <r-help@r-project.org>
Sent: Fri, September 17, 2010 6:36:51 PM
Subject: Re: [R] Interpolate? a line


On Sep 17, 2010, at 7:22 AM, Alaios wrote:

> I would like to thank you again for your help.
> But it seems that the floor function (ceiling, round too) create more dots in 
>the matrix that line really "touches".

You said "cells" not "dots". Are you trying to change the problem now? My 
concern is rather that it can still miss cells.

> 
> unique( floor( cbind( seq(2,62, by=0.1), linefn(seq(2,62, by=0.1)) ) )  )
> 
> You can see that in the picture below
> 
> http://yfrog.com/5blineswj
> 
> So, how to select the only the cells that the line "touches"?

If you had taken my suggestion of overlaying a grid rather than plotting dots 
that fail to represent a "cell" (which I was taking to be a square of dimension 
1 x 1) you would see that my solution was correct (at least to the point of not 
missing any cells so defined that were touched up to a tolerance of 0.01 cell 
units. If you want to define "cells" differently, then it's your turn to step up 
and get mathematically precise. Calculus still works if you define neighborhoods 
as hyperspheres s  rather than epsilon by delta hyper-rectangles.

# Here is the the illustrated sequence of getting to what I am calling my "final 
answer",
# even though it could still miss an occasional cell.

interp <- approx(c(2, 62), c(3, 34), method="linear", xout=2:62)
m <- matrix(c(interp$x, round(interp$y)), ncol=2)
tie <- m[,2] == c(-Inf, m[-nrow(m),2])
m <- m[ !tie, ]

plot(m)  # plots points
lines(c(2,62), c(3, 34))  # overlay line for comparison
#you can add a grid with
abline(v=2:62, h=3:34)

## First attempt at integer values of x

linefn <- function(x) 3+((34-3)/(62-2)) *(x-2)
findInterval(linefn(2:62), 3:34)

# Second attempt at 0.1 intervals

#########
cellidxs <- unique( floor( cbind( seq(2,62, by=0.1), # There will be many 
duplicates after rounding down
                    linefn(seq(2,62, by=0.1)) ) )  ) # the same function that 
just gets a y value

rect(cellidxs[,1], cellidxs[,2], cellidxs[,1]+1, cellidxs[,2]+1, col="red")

#redraw line :
lines(2:62, 3+(34-3)/(62-2)*(0:60))
# That is the first plot with coarse tolerances
#Third attempt:
# Now calculate a set of cell ids with tolerances that at ten-fold more numerous

cellid2 <-unique( floor(cbind(seq(2,62, by=0.01), linefn(seq(2,62, by=0.01) )) ) 
)
NROW(cellid2) # 91 cells
rect(cellid2[,1], cellid2[,2], cellid2[,1]+1, cellid2[,2]+1, col="blue")
rect(cellidxs[,1], cellidxs[,2], cellidxs[,1]+1, cellidxs[,2]+1, col="red")
lines(2:62, 3+(34-3)/(62-2)*(0:60))

--Best
David.

> 
> I would like to thank you in advance for your help
> best Regards
> Alex
> 
> From: David Winsemius <dwinsemius@comcast.net>

> Cc: Rhelp list <r-help@r-project.org>
> Sent: Wed, September 15, 2010 1:55:10 PM
> Subject: Re: [R] Interpolate? a line
> 
> 
> On Sep 15, 2010, at 7:24 AM, David Winsemius wrote:
> 
> > Replacing context:
> >
> >>> Hello everyone.
> >>> I have created a 100*100 matrix in R.
> >>> Let's now say that I have a line that starts from (2,3) point and ends to 
>the
> >>> (62,34) point. In other words this line starts at cell (2,3) and ends at 
>cell
> >>> (62,34).
> >>>
> >>> Is it possible to get by some R function all the matrix's cells that this 
>line
> >>> transverses?
> >>>
> >>> I would like to thank you for your feedback.
> >>>
> >>> Best Regards
> >>> Alex
> >
> > On Sep 15, 2010, at 6:52 AM, Michael Bedward wrote:
> >
> >> Hello Alex,
> >>
> >> Here is one way to do it. It works but it's not pretty :)
> >
> > If you want an alternative, consider that produces the Y cell indices (since 
>the x cell indices are already 2:62):
> >
> > > linefn <- function(x) 3+((34-3)/(62-2)) *(x-2)
> > > findInterval(linefn(2:62), 3:34)
> > [1]  1  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  9  9 10 10 11 11 12 12 
>13 13 14
> > [28] 14 15 15 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 
>27 27 28
> > [55] 28 29 29 30 30 31 32
> > # that seems "off" by two
> > > linefn(62)
> > [1] 34
> > > linefn(2)
> > [1] 3 # but that checks out and I realized those were just indices for the 
>3:34 findInterval vector
> >
> > > (3:34)[findInterval(linefn(2:62), 3:34)]
> > [1]  3  3  4  4  5  5  6  6  7  7  8  8  9  9 10 10 11 11 12 12 13 13 14 14 
>15 15 16
> > [28] 16 17 17 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 
>29 29 30
> > [55] 30 31 31 32 32 33 34
> >
> > ( no rounding and I think the logic is clearer.)
> 
> But I also realized it didn't enumerate all the the cells were crossed either, 
>only indicating which cell was associated with an integer value of x. Also would 
>have even more serious problems if the slope were greater than unity. To 
>enumerate the cell indices that were crossed, try:
> 
> unique( floor( cbind( seq(2,62, by=0.1), linefn(seq(2,62, by=0.1)) ) )  )
>       [,1] [,2]
> [1,]    2    3
> [2,]    3    3
> [3,]    4    4
> [4,]    5    4
> [5,]    5    5
> [6,]    6    5
> [7,]    7    5
> [8,]    7    6
> snipping interior results
> [83,]  58  32
> [84,]  59  32
> [85,]  60  32
> [86,]  60  33
> [87,]  61  33
> [88,]  62  34
> 
> That could probably be passed to rect() to illustrate (and check logic):
> 
> rect(cellidxs[,1], cellidxs[,2], cellidxs[,1]+1, cellidxs[,2]+1, col="red")
> 
> #redraw line :
> lines(2:62, 3+(34-3)/(62-2)*(0:60))
> 
> 
> >
> > --David.
> >
> >>
> >> interp <- approx(c(2, 62), c(3, 34), method="linear", xout=2:62)
> >> m <- matrix(c(interp$x, round(interp$y)), ncol=2)
> >> tie <- m[,2] == c(-Inf, m[-nrow(m),2])
> >> m <- m[ !tie, ]
> >>
> >> You might want to examine the result like this...
> >>
> >> plot(m)  # plots points
> >> lines(c(2,26), c(3, 34))  # overlay line for comparison
> > you can add a grid with
> > abline(v=2:62, h=3:34)
> >>
> >> Michael
> >>
> 

David Winsemius, MD
West Hartford, CT


      
	[[alternative HTML version deleted]]

