Finding an approximate diagonal in a grid

1.3k Views Asked by At

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 
3

There are 3 best solutions below

5
On

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

2
On

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$.

1
On

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.