# Bresenham’s Line Drawing Algorithm

May 10, 2023

Bresenham’s line drawing algorithm is a mathematical algorithm used to draw a line between two points in a computer graphics system. The algorithm is named after its creator, Jack E. Bresenham, who developed it in 1962 while working at IBM. Bresenham’s line drawing algorithm is widely used in computer graphics and is considered one of the fundamental algorithms for drawing lines, circles, and other geometric shapes.

The purpose of Bresenham’s algorithm is to draw a straight line between two points on a computer screen. The algorithm is used in many applications, including computer-aided design (CAD), computer graphics, and video games. It is the most efficient algorithm for drawing lines on a raster display, which is a display system in which the image is made up of a grid of pixels.

## Brief History and Development

Bresenham’s line drawing algorithm was developed in 1962 by Jack E. Bresenham while working at IBM. He was trying to find an algorithm that would draw a straight line on a raster display more efficiently than the existing algorithms. Bresenham’s algorithm was published in the IBM Systems Journal in 1965 and quickly became a standard algorithm used in computer graphics.

## Key Concepts and Principles

The key concept behind Bresenham’s algorithm is to determine which pixels on a raster display should be turned on to create a straight line between two points. The algorithm works by calculating the error or the distance between the line and each pixel on the screen. The algorithm chooses the pixel with the smallest error and draws the line to that pixel. The algorithm iterates this process until it reaches the second point.

The algorithm works by dividing each pixel on the screen into two halves, the upper half and the lower half. The error is calculated for each half of the pixel, and the pixel with the smallest error is chosen. The chosen pixel is then filled in, and the error is recalculated for the next pixel. The process continues until the line reaches the second point.

## Pseudocode and Implementation Details

The pseudocode for Bresenham’s line drawing algorithm is as follows:

``````function drawLine(x1, y1, x2, y2) {
dx = abs(x2 - x1)
dy = abs(y2 - y1)
sx = x1 < x2 ? 1 : -1
sy = y1 < y2 ? 1 : -1
err = dx - dy

x = x1
y = y1

while (x != x2 || y != y2) {
plot(x, y)
e2 = 2 * err

if (e2 >= -dy) {
err -= dy
x += sx
}

if (e2 <= dx) {
err += dx
y += sy
}
}
}``````

The implementation details of the algorithm involve iterating through each pixel on the screen and calculating the error for each pixel. The algorithm chooses the pixel with the smallest error and fills it in. The error is then recalculated for the next pixel, and the process continues until the line reaches the second point.

### Examples and Use Cases

Bresenham’s line drawing algorithm is used in many computer graphics applications, including video games, computer-aided design, and computer graphics software. The algorithm is used to draw straight lines between two points on a computer screen. It is also used to draw circles, ellipses, and other geometric shapes.