I have two lattice (grid) end points of the line, how can I generate intermediate points of the line segment between them?
One way is iterate through all the x points or y points and check (solve line equation) if the coordinates we get each time are integral solution or not.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ I suggest rephrasing the question to include all necessary details, as well as to clearly indicate what the desired output is like. Please spend a few minutes making your question as clear as possible, using as many words as necessary. $\endgroup$– Yuval FilmusFeb 9, 2018 at 15:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
For a line segment defined by two integral lattice points $(x_0,y_0), (x_1,y_1)$ there will be $gcd(y_1-y_0,x_1-x_0)-1$ additional integral points along the line segment. To find them move along line by largest value in the reduced slope.
-
$\begingroup$ Let the slope be in p/q (reduced form) .Now how do I move? $\endgroup$ Feb 10, 2018 at 4:46
-
1$\begingroup$ Add q,p to x,y until you reach end of line segment. $\endgroup$– TomokiFeb 10, 2018 at 6:37
$\begingroup$
$\endgroup$
It seems that you are interested in line rasterization or digitization algorithm, meaning that you want efficiently find continous representation of line in discrete grid.
Very efficient algorithm was made by Bresenham. There are other algorithms like DDA, or anialiased Wu line algorithm.
The core idea is to calculate gradient of the line, iterate by discrete step (here exactly pixel) and determine the exact position (one of two adjacent pixels).