# Efficient line vs grid algorithm?

This topic is 4553 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok I have been pondering on this for 2 days now and cannot find a satisfying solution while I'm sure there must be one (for which im probably going to slap myself in the face for not seeing it). The blue line is a limited line from coordinates A to B. These are floating point coordinates, hence the resolution is virtually infinite. The grid are integer cells (rows and columns), they are square and of fixed size. I want to know what cells are touched by the line. (as I indicated here by coloring the cells red) I can come up with several inefficient algorithms like, for example, running through all cells and see if they touch the line, but that is not acceptable. Does anyone know of a way to do this properly? Any tutorial describing it maybe? Any help would be much appreciated!

##### Share on other sites
check this out:
http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

##### Share on other sites
Unfortunately, Bresenham doesn't work without modification because it only considers integer coordinates.

"Grid traversal" is a good search term for what you want. A nice and simple algorithm is presented here, for example (scroll down a couple of pages).

##### Share on other sites
Anonymous Poster: No, I looked at that (actually worked with the algorithm before in a previous project) and its not what I'm looking for. This is NOT the same situation here. Please see me picture and description of the problem.

##### Share on other sites
How about Xiaolin Wu's line algorithm. It's linked under references under the previously posted bresenham's algortihm page.

http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm

The only modification you'd need is instead of rendering alpha adjusted values to simply tag those fields.

It has been a long time since I did manual line anti-aliasing, but from a quick look, this should work. Given that it considers two pixels (instead of one as per Bresenham case), it should cover all the cases. Looking at the problem naively, I'd say that the difference between Bresenham's and your algorithm will be at most two pixels per scanline (one at each edge), so Wu's should work.

##### Share on other sites
Antheus: I looked at that also (I am familliar with google and wikis :P) but also that is not exactly what I need. I do not want nearby cells (which is what anti-aliasing colors), only the cells actually touched.

Sharlin: That looks like the solution im looking for! However the article is somewhat vague on some parts, like "we determine how far we must move along the ray to cross one cell. Again, we do this for x, y and z; the result is stored in tDeltaX, tDeltaY and tDeltaZ."... How do they do that?

##### Share on other sites
Why not just walk the line?
find starting cell at one end of line (easily done with a few divisions)
find which side of current cell the line exits, left or right or top or bottom (just some line intersection test)
repeat for the cell in that direction
continue till reach cell that contains endpoint of line

##### Share on other sites
All the intersection tests that would have to be done along the line would be less efficient than the method Sharlin proposed.

I would like an answer to the vague description in that method Sharlin proposed though, as I wrote in my previous post. This could be the most efficient solution I've encountered so far.

##### Share on other sites
This may have already been mentioned in one of the above links, but you're probably looking for DDA or 3D-DDA. These are algorithms that are related to some of the line-drawing algorithms mentioned above, but are geared toward the problem you mention, that is, finding all cells touched by a given ray.

##### Share on other sites
Quote:
 Original post by CodeImpAll the intersection tests that would have to be done along the line would be less efficient than the method Sharlin proposed.

DDA
Yeah, thats basically what I was suggesting. He gets 'tMaxX' and 'tMaxY' by doing the gridline interesection I mentioned, but omitted the details in the description. It's also optimized to take advantage of line directionality so only 2 of 4 cell walls need to be checked. Either that or its psuedocode...

I didn't know that algorithm had a name...
Good to know

whats DDA an acronym for? I just call it 'line walking'

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5
frob
12

• 9
• 21
• 12
• 9
• 17
• ### Forum Statistics

• Total Topics
632607
• Total Posts
3007387

×