Graphics / Reference / Naïve line algorithm
Naïve line algorithm
The naïve first-octant line algorithm evaluates the mathematical line separately at each integer x coordinate, rounds the resulting real-valued y position, and draws the corresponding pixel.
For integer endpoints in the first-octant case, initialise:
m = (y1 - y0)/(x1 - x0) c = y0 - m*x0 x = x0 y = y0
Then iterate while x <= x1:
DRAW(x,y) x = x + 1 yi = m*x + c y = ROUND(yi)
yi is a floating-point value: the y coordinate where the mathematical line intersects the vertical line at the current x. The source describes this as the floating-point "y-intercept" at that vertical line; it is distinct from the constant c, which is the usual y-axis intercept.
In this site's direct implementation, ROUND uses the half-up policy y = floor(yi + 0.5), so an exact half is assigned to the larger integer y value.
The defining implementation property is that yi is recomputed from the full equation in every column. Each update therefore performs the multiplication m*x and then adds c before rounding.
The associated diagram shows the continuous line crossing the vertical line for column x, with yi marked at that intersection.
Builds on
Read
- Read the chapter: Naïve line algorithm