Jack Bresenham's raster graphics algorithm selects a thin sequence of pixels to represent a line segment by exact incremental integer arithmetic. For a first-octant segment with , a scaled midpoint line decision chooses between the next same-row and next higher-row pixels.
For the implicit equation , the sign of compares the exact line with the midpoint between candidate pixel centres and . Multiplication by two makes the test integral. A consistent equality rule specifies which tied pixel is selected.
Articles by others on the same topic
Bresenham's line algorithm is an efficient algorithm used in computer graphics to determine which points in a grid or raster display should be plotted in order to form a straight line between two given points. It was developed by Jack Bresenham in 1962 and is particularly valued for being a simple, integer-based algorithm that runs quickly and does not require floating-point arithmetic.