On Feb 15, 9:11 am, "Anush" <itsanushshe...@[EMAIL PROTECTED]
> wrote:
> On Feb 15, 6:15 pm, "Cari Elf" <cbe...@[EMAIL PROTECTED]
> wrote:
>
>
>
>
>
> > On Feb 14, 12:15 pm, "Anush" <itsanushshe...@[EMAIL PROTECTED]
> wrote:
>
> > > On Feb 14, 7:51 pm, "Cari Elf" <cbe...@[EMAIL PROTECTED]
> wrote:
>
> > > > On Feb 14, 3:47 am, "Anush" <itsanushshe...@[EMAIL PROTECTED]
> wrote:
>
> > > > > I have a square grid of unit size. If i have a line between any
two
> > > > > points, how do i find out the number of the intersecting
squares.
>
> > > > > -
> > > > > Anush
>
> > > > Well, if you label each cell from (0,0) to (N,N), you can convert
from
> > > > the points to cell coordinates by dividing the point coordinates
by
> > > > the width of a cell. Then all you need to do is find the ceiling
of
> > > > the Euclidean distance between the two points--in other words,
round
> > > > up to the nearest whole integer. This worked with a small test
> > > > sample, but you should probably test it with several test cases to
> > > > make sure that it works in all cases. I think that you can do a
brute
> > > > force test using the method described here if you make the Z
> > > > coordiantes 0:
>
> > > >http://mathworld.wolfram.com/Line-PlaneIntersection.html
>
> > > Oh ok..
>
> > > Correct me if I am wrong.
> > > so if the grid is from (0,0) to (3,3) and if the line is between
> > > (0,1 ) and (1, 3) , then the cell coordinates for the line is
(0,1/3)
> > > and and (1/3,1) and then compute the euclidean distance between the
> > > two points right.
>
> > > Thanks
>
> > > -
> > > Anush- Hide quoted text -
>
> > > - Show quoted text
>
> > Let's say rather that the total size of the grid is 30 pixels by 30
> > pixels, with 3 cells across and 3 cells down, like a tic tac toe game.
> > That means that each cell is a 10 x 10 square. Now we have nice
> > numbers to work with. :)
>
> > If you have the points (0,11) and (24,20), divide the coordinates by
> > 10. So your first point becomes (in cell coordinates) (0, 1) and
> > your second point becomes (2, 2) because we're only interested in
> > which cell the point is in, not its exact location. Now plug that
> > into the forumula c * c = (a*a + b * b).
>
> > c = sqrt((2-0) * (2-0) + (2 - 1) * (2-1)) = sqrt(2 * 2 + 1 * 1) = sqrt
> > (4 + 1) = sqrt(5). Round up to 3, and you have your answer.
>
> Wonderful.. you rock :)
>
> One thing I need to keep in mind that when I am computing the square
> root , i need to round the value to the nearest square no (lower-bound
> or upper-bound). For eg. for line from (0,0) to (10, 20) , when I
> divide it by 10, i get (0,0) to (1,2) and c = sqrt(1+4) and the
> nearest square no is 4 .. so the no of squares is 2.
>
> But I think we need to take diagonal as a special case. For a line
> from (0,0) to (30,30) , its cell coordinates are (0,0) and (3,3). and
> the c =sqrt(3*3 + 3*3) and the value we obtain is 4 which is wrong.
>
> -
> Anush- Hide quoted text -
>
> - Show quoted text -
Actually, if your grid is 30 x 30 pixels then the coordinate (30,30)
is outside of your range. So you will have to test to make sure that
the points are between 0 and 29, inclusive.
But I don't understand why you have to round to the nearest square
number instead of rounding up to the nearest whole number to get the
number of cells that you pass through.
|
