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
|
