Identify which cells a line travels through

[Griffyn]

Hi all,

Here's a challenge!

I'm working with a TDrawGrid. Give it, say, 10 rows and 10 columns, which means it has 100 cells. Now pick any two cells in the grid and draw a line that connects the centre of each.

What I want to know is, how can I tell what cells that line travels through? Anyone have any code snippets?

I want to use this algorithm to identify when a drawn indicator is moved around the grid and I only want to Invalidate the necessary cells to reduce flicker and drawing time.

I've made a good start on this, but it's a little unwieldy (my code requires 4 copies to handle the 4 different diagonal directions), plus my maths is thrown off because the line is drawn from the centre of the cell, and not from the nearest corners.

Many thanks!

 

[Glenn9999]

it sounds like you need a palette swapping algorithm.

What you do is use a display cell and a non-display cell. You draw on the non-display cell, and then when you are ready to display, then you do an assign of the non-display cell to the display one.

That's what reduces flicker and drawing time. At least time people see stuff being drawn on the screen.

 

[donvittorio]

If you know the position and size information of any cell then it's simple enough to find the coordinate of the centre, of course it's this easy:

X = Left + (Width/2) Y = Top + (Height/2)

Assuming that you have the coordinates of each end of the line, we now need to use the good old equation of a straight line that we were all taught at school (y = mx + c).
For the sake of this explanation I'll keep it simple by assuming that my origin is bottom left (of course Delphi uses top left). If your diagonal line start at (x1,y1) and ends at (x2,y2) then you know the origin and can find the gradient:

c = y1 m = (y2-y1) / (x2-x1)

Imagine a 3x3 grid, with a diagonal line from the middle of the bottom left cell (x1,y1) to the middle of the top right cell (x2,y2), I can't include a drawing so you'll have to use your imagination for this bit!
We can visualise that for the line to pass through a cell it must pass below the cell's top left corner and above the cell's bottom right corner. If we consider the centre cell then its top left corner is at point A (xA,yA) and its bottom right corner is at point B (xB,yB). We can use our equation to find the height of the diagonal line at these points, for the top left:

y = m.xA + c

if y < yA then the line passes below the top left corner. Similarly for the bottom right:

y = m.xB + c

if y > yB then the line passes above the bottom right corner. If both these conditions are true then we know that the line passes through the cell.

You wouldn't need to run the equation for the corners of every cell, for example if we have a line with a positive gradient (i.e. bottom left to top right) then if we start at B and find that the line passes below point B then we know that the line must also pass below point A.

I hope that was some help. Of course as your grid gets bigger then the amount of maths your program will need to perform will grow and hence take longer to perform, so you may be better off finding a different approach to avoid flickering of your grid, as suggested by Glenn

Steve