Find point on line that has integer coordinates
Given a 2D line e.g. (3,10) -> (8.3,16.5), how can I find any point on that line that has has whole-number coordinates?
I can easily iteratively walk along one of the axis in integer steps, seeing if the value on the other axis is integer, but this is slow for very very long lines.
I think, in math-speak, I want to efficiently find all the lattice points between two points?
I mark this as homework because its literally hobby problems I'm inventing myself at home. I don't recall much beyond high-school math anyway.
$\endgroup$1 Answer
$\begingroup$First find the slope of the line, using this formula:
$$\text{Slope of the line} = \frac{\text{Change in y}}{\text{Change in x}}$$
$$m = \frac{y_2 - y_1}{x_2 - x_1} = \frac{16.5-10}{8.3-3} = \frac{6.5}{5.3} = \frac{65}{53}$$
Now using this formula find the equation for the line:
$$y - y_1 = m(x-x_1)$$ $$y - 10 = \frac{65}{53}(x-3)$$ $$y = \frac{65x}{53} + \frac{530 - 195}{53}$$ $$y = \frac{65x + 335}{53}$$
Now $x$ can be any integer, but in order $y$ to be an integer $65x + 335$ needs to be divisible by $53$. In other words:
$$65x + 335 \equiv 0 \pmod{53}$$ $$65x \equiv -335 \pmod {53}$$ $$12x \equiv -70 \pmod {53}$$ $$6x \equiv -35 \equiv -88 \pmod {53}$$ $$3x \equiv -44 \pmod {53}$$ $$3x \equiv -150 \pmod {53}$$ $$x \equiv -50 \equiv 3 \pmod {53}$$
So for every $x=53k + 3; \forall k \in \mathbb{R}$, we have an integer point on the line that pass through the two initial points
So one example will be the point $(x,y) = (56,75)$
$\endgroup$ 5
