   Get the squares touching line in a grid
  Hello,I need to find all the squares in the grid which include a part of the line drawn in a grid. A similar(same) topic was created long backhttp://www.gamedev.net/community/forums/topic.asp?topic_id=385303(I am definitely not looking for Bresenham's algorithm)Does somebody have source code for this problem or some links? Thank you in advance for ur help!Best Regards   
  I just implemented a similar thing, though it only checks one rectangle. But if you add a loop, it should be fine.I wrote it 2 minutes ago, so the code is crappy, messy and C... But it works perfectly and that is all I care about ATM.It's 2D but I use 3D functions (so I don1t have to write the 2D equivalents)/*bx1,by2-------bx2,by2|  ||  ||  ||  |bx1,by1-------bx2,by1*/int AxisOrientedBox_LineIntersection(double bx1,double by1,double bx2, double by2,   double *p1,double *p2){    //edited here: removed the unnecessary check.    //if one of the endpoints is inside the box, then the line intersects    if( (p1[0] >= bx1 && p1[0] <= bx2   &&   p1[1] >= by1 && p1[1] <= by2) ||   (p2[0] >= bx1 && p2[0] <= bx2   &&   p2[1] >= by1 && p2[1] <= by2) )    {   return TRUE;    }    //if both endpoints is on one side of the box, then the line doesn't intersect    if( (p1[0] < bx1 && p2[0] < bx1)   ||   (p1[0] > bx2 && p2[0] > bx2)   ||   (p1[1] < by1 && p2[1] < by1)   ||   (p1[1] > by2 && p2[1] > by2) )    {   return FALSE;    }    //here's the tricky part://if one of the rectangle points is on the opposite side of the line compared to the others:    // the line intersects. If all of them are on one side, there's no intersectionelse    { // direction of line and the perpendicular direction:   double line_dir[3],line_perp[3];    double up[3] = { 0.0f,0.0f,1.0f };   double to_corner[3];   double first;   line_dir[0] = p2[0] - p1[0];   line_dir[1] = p2[1] - p1[1];   line_dir[2] = 0;   CrossProduct(line_perp,line_dir,up); // params: out,v1,v2; winding: CCW   to_corner[0] = bx1 - p1[0];   to_corner[1] = by1 - p1[1];   to_corner[2] = 0;   first = DotProduct(line_perp,to_corner);   to_corner[0] = bx2 - p1[0];   to_corner[1] = by1 - p1[1];   if( first * DotProduct(line_perp,to_corner) < 0 ) // other side!   {    return TRUE;   }   to_corner[0] = bx2 - p1[0];   to_corner[1] = by2 - p1[1];   if( first * DotProduct(line_perp,to_corner) < 0 ) // other side!   {    return TRUE;   }   to_corner[0] = bx1 - p1[0];   to_corner[1] = by2 - p1[1];   if( first * DotProduct(line_perp,to_corner) < 0 ) // other side!   {    return TRUE;   }    }    return FALSE;}BTW I don't get your problem with Bresenham's algorithm.EDIT: removed an irrelevant thing and added some comments.BTW my algo is for line selection, so id does what you want (the irrelevant thing was to check in the 'z' direction: my function checks for a box).[Edited by - szecs on October 7, 2010 8:05:55 AM];  I found a code which does exactly what I need but dont understand it :(What confuses me is that all the variables in the code are defined as 'int', which sucks coz it looks like the algorithm has to work with fractional parts. Secondly, I dont understand is the program works for all grid square sizes or only for a grid squares having a width of 1.http://lifc.univ-fcomte.fr/~ededu/projects/bresenham/Any comments?   ;Quote:Original post by szecsBTW I don't get your problem with Bresenham's algorithm.You see the link provided in my prev reply ( http://lifc.univ-fcomte.fr/~ededu/projects/bresenham/ ). The first picture in it depicts the difference between what Breshans algorithm does and my requirement;Quote:Original post by luckycuspQuote:Original post by szecsBTW I don't get your problem with Bresenham's algorithm.You see the link provided in my prev reply ( http://lifc.univ-fcomte.fr/~ededu/projects/bresenham/ ). The first picture in it depicts the difference between what Breshans algorithm does and my requirementAhh, okay I see, I missed that. Anyway, my code does that, if you can understand it.Or just pass the approproate parameters.*p1 and *p2 are pointers to double[2].So if you have the dot and cross product functions in 3D, you can copy and use the function as it is.   ;Quote: Or just pass the approproate parameters.*p1 and *p2 are pointers to double[2].So if you have the dot and cross product functions in 3D, you can copy and use the function as it is.How come u r accessing p1[2], p2[2] in some places of ur code if its an array of length 2?EDIT: I see that u have modified the code now!   ;  You should read up on Bresenham's algorithm found here because the algorithm you found makes use of it. Bresenham's algorithm is meant for fast line drawing because it avoids using floating point values.However, if you are not concerned with speed, you can very easily achieve what you want using basic math (line equation y = mx+b) with floats. When you calculate the pixel's y value with the equation, do a check on it to see if its exact an integer (i.e. 5.0, not 4.8 or 5.1). If it is, just draw that one pixel, if not, otherwise, floor and ceiling the value to get both pixels.   ;Quote:So if you have the dot and cross product functions in 3D, you can copy and use the function as it is.Thanks for trying to help Szecs but its not what I need. Your function just checks for 1 rectangle, but I need an algorithm which would traverse all the touching squares from point 1 to point 2. (And that is not just a simple loop!)   ;  The coordinate system:  y  |  |  |  |  |  0----------- x /z;Quote:Original post by enigmatixYou should read up on Bresenham's algorithm found here because the algorithm you found makes use of it. Bresenham's algorithm is meant for fast line drawing because it avoids using floating point values.However, if you are not concerned with speed, you can very easily achieve what you want using basic math (line equation y = mx+b) with floats. When you calculate the pixel's y value with the equation, do a check on it to see if its exact an integer (i.e. 5.0, not 4.8 or 5.1). If it is, just draw that one pixel, if not, otherwise, floor and ceiling the value to get both pixels.Hmm, ok. The modified Bresenham's algorithms really do my head in, how they achieve the result without floating point numbers. I will try to spend more time on it trying to understand.   