# Finding an approximate diagonal in a grid

Imagine a 2 dimensional grid, with a variable size of $x*y$. For this example of figure 1, let $x=14; y=5$.
Now one may position "pixels" in this gird. They can only be placed on the grid's points and not in between, meaning that $x$ and $y$ are integers ($x=ℤ; y=ℤ$).

Let there be two points $a(0|0)$ and $b(x-1|y-1)$, which mark the end points of a diagonal crossing the grid.

Constructing a function which gives the diagonal would be pretty trivial, if we would allow $x=ℚ; y=ℚ$. But how can I create a function (or algorithm) that returns a diagonal as shown in figure 2, that has rotational symmetry?
It may also look like figure 3, distributing the pixels as evenly as possible, but without regarding any symmetry.

Figure 1
o o o o o o o o o o o o o b
o o o o o o o o o o o o o o
o o o o o o o o o o o o o o
o o o o o o o o o o o o o o
a o o o o o o o o o o o o o

Figure 2                            Figure 3
o o o o o o o o o o o + + b    |    o o o o o o o o o o o o + b
o o o o o o o o + + + o o o    |    o o o o o o o o o + + + o o
o o o o o o + + o o o o o o    |    o o o o o o + + + o o o o o
o o o + + + o o o o o o o o    |    o o o + + + o o o o o o o o
a + + o o o o o o o o o o o    |    a + + o o o o o o o o o o o

-
There is a problem with off-by-1 in this sort of lattices. You have said $x=14, y=5$ but people often assume the lower left corner is $(0,0)$ in which case the upper right corner is $(13,4)$, so the span is $13$ horizontally and $4$ vertically. –  Ross Millikan Jan 19 '13 at 4:16
Just found a grea (German) Wikipedia article: de.wikipedia.org/wiki/Rasterung_von_Linien Everybody interested should search for the "Bresenham algorithm". –  silvinci Jan 22 '13 at 11:31

How about the function, vertical coordinate is nearest integer to ($5/14$ times horizontal coordinate)?

-
Thanks! Don't know, why I couldn't get my head around this. Haha. This would solve Figure 3. –  silvinci Jan 19 '13 at 3:59
@silvinci: No, this will give exactly one point on each row. It will be symmetric around the center. –  Ross Millikan Jan 19 '13 at 4:01
Did I got that right? $\Delta y_1 \longrightarrow round(y/x * x_1)$ –  silvinci Jan 19 '13 at 4:08
@Ross, I think my formula gives exactly one point in each column. –  Gerry Myerson Jan 19 '13 at 4:37
You are right. Still symmetric. It feels to me like OP wants more points than that, but a good option. –  Ross Millikan Jan 19 '13 at 4:53

Let $y \geq x$ without loss of generality. One way is to start at $a$ and drop $\left \lfloor\dfrac{y}x \right \rfloor$ pixels to right of $a$ in the furst row and then go one row up and repeat this till you reach $b$.

-
y maybe smaller then x, meaning that the grid could go into a negative direction. x and y are Z (without 0). –  silvinci Jan 19 '13 at 4:02
@silvinci: you can check which of $x,y$ is smaller and interchange roles if necessary. This one will give exactly one pixel per row (if there are more columns than rows) but may not give the fit you want. In your case, note that the upper coordinate is $(4,13),\ \ \left \lfloor\dfrac{y}x \right \rfloor=2$, so the point above the bottom will be $(1,7)$ which is not close to $(0,0)$ –  Ross Millikan Jan 19 '13 at 4:07

If your grid is $x \times y$ with $x \ge y$ and $x$ horizontal (as in your figures), and the lower left is $(0,0)$, the upper right is $(x-1,y-1)$ the true diagonal will cross row $a$ at $\frac {a(y-1)}{x-1}$. You could check whether this is an integer, then if it is take only that point, otherwise take the two points on either side: $(a,\lfloor \frac {a(y-1)}{x-1} \rfloor)$ and $(a,\lceil \frac {a(y-1)}{x-1} \rceil)$. This will be symmetric around the center.

The variety of answers you have gotten shows that there are many reasonable answers-you need to try them and find which suits your needs.

-
Thanks. I'll try them out. :) –  silvinci Jan 19 '13 at 4:23