Алгоритм Брезенхэма
Рисует прямую на пиксельной сетке одним лишь целочисленным сложением — без плавающей точки и без деления.
Джек Брезенхэм придумал его в 1962 году в IBM для плоттера Calcomp, а опубликовал в 1965-м. Хитрость в члене ошибки, который накапливается шаг за шагом: для каждого пикселя вдоль главной оси знак ошибки решает, сдвинется ли вторая координата или останется на месте. Всё сводится к сложению, вычитанию и сравнению — операциям, которые быстро выполняло даже железо 1960-х.
Вариант для окружности (midpoint circle) рисует круги тем же способом, а сам принцип дожил до растеризации шрифтов и инструмента «линия» в пиксельных редакторах. Сухая правда: почти каждая прямая, которую вы видели на экране, прошла через член ошибки Брезенхэма.