§ Как рисовать линию?

Допустим, начало линии находится в а конец ее находится в , причем, .
Ясное дело, что если или , то это будут просто прямые линии, такие мы не будем рассматривать, потому что это слишком было бы просто. Нужно нагрузиться материалом так, чтобы мама не горевала.
Я должен вспомнить уравнение прямой, заданной параметрически:

То есть тут параметр указывает на то, где именно мы берем точку, и если , то точка будет тут , если , то правая точка будет находиться в
Еще один важный момент, который нельзя упускать из виду: дело в том, что когда мы работаем с дисплеем, то любой, абы какой брать нельзя, потому что пиксели там, а не непрерывное что-то, и потому можно брать равным так, чтобы попадал в пиксели ровно.
Задача такая: найти по . Все просто, берем уравнение
и начинаем находить по , перенося и деля:
Отлично. Теперь надо подставить полученный в уравнение .
То есть, вуаля - и все работает через магический вхуж.
А теперь давайте просто рассмотрим по шагам весь этот странный процесс. Допустим на секунду, что , что тогда будет? Из верхней формулы ясно и четко видно, что будет , и все справа обнулится, кроме :
Но! Поскольку у нас все попиксельно (да?), то тогда следующий должен быть равен .

§ Инкрементальное вычисление

Конечно, можно брать и вычислять , основываясь на , по той формуле, что сверху написана. Но такие вычисления ужасно затратны, ясное дело. Намного легче вычислять приращение. Почему? Потому что - не дробное число, и поэтому будет принимать значения от до , например, если а , то тогда будет принимать только такие значения 10, 11, 12, 13, 14 и 15. Это значит, что если мы знаем , который получается после вычисления , то тогда можно узнать , который получится путем определения разности между . Тяжело... короче, легче на примере показать
Пример:
Теперь построю таблицу, понимая, что может принимать значения только от 12 до 16, и только целочисленные.

12		5	1,25
13		6,25	1,25
14		7,5	1,25
15		8,75	1,25
16		10	–

Нетрудно заметить, что приращение никак не увеличивается. И это валидно, ибо дело имеем мы с "линейной функцией", а то есть, линией. А линия, как известно, является прямой, без загогулин, и потому в любой точке ее приращение будет тем же самым.
Почему так получается? Элементарно же! Я сделаю расчет, который покажет, что все так. Надо взять любой , добавить к нему +1 и рассчитать формулу, и потом из этой формулы числить формулу, которая просто с , чтобы узнать, что все действительно в порядке.
Так вычтем же!
Начинается магия разложения. Сначала я удалю отсюда лишние иксы
А потом разложу числители
Осталось удалить не нужное (сократить)
Опупеть можно! Почему так сложно делается то, что можно было в уме легко сделать? В математике простых путей не ищут, потому надо нагородить формул, чтобы умнее выглядеть. Вот и ответ. А это еще даже до сути особо не добрались.
На самом деле, тут показано, что можно с помощью обычного приращения построить линию. Единственное, что никак не построишь никакую линию для случая, когда линия прямая, то есть когда .

§ Как переделать в целочисленность?

На самом деле тут так все элементарно, что не знаю, как бы еще доступнее объяснить! Возьму линию (2,4)-(3,8), вычислю , , а значит, приращение с каждым разом будет , что совершенно естественно в данном случае.
Нетрудно заметить, что приращение получается дробным, а именно всегда рациональной дробью. То что это всегда рациональная дробь, и может спасти всех нас от замедления скорости.
Достану таблицу и расскажу что да как:

y	x	+dx	[x]	сумма
4	2,00	+0,25	2	0 : 4
5	2,25	+0,25	2	1 : 4
6	2,50	+0,25	2	2 : 4
7	2,75	+0,25	2	3 : 4
8	3,00	+0,25	2	4 : 4

В первой и второй колонке (где игрек и икс) находятся координаты следующей точки для построения. В третьей колонке - величина приращения при добавлении +1, а в четвертой как раз самое интересное - это общая сумма при постоянном приращении
Вот действительно, если встать на начальную точку, что , если добавить приращение, то тогда будет так
Если добавить еще раз приращение, то будет так
И так далее. Теперь как применить к случаю выше:
Как можно заметить, числитель равномерно складывается, а знаменатель (снизу), остается тем же самым. Это на руку. То есть можно просто сделать так

Y = Y + 1
Числитель = Числитель + (x2-x1)
ПОКА Числитель >= Знаменатель
    Числитель = Числитель - Знаменатель
    X = X + 1

То есть суть такая, что пока числитель меньше знаменателя, то целочисленное значение X не увеличивается (а дробное не нужно), но как только числитель превышает знаменатель, то надо увеличивать X столько раз, пока числитель не станет меньше знаменателя (это вообще процедура деления, между прочим, из 5-го класса!)
Не, ну ты это видел? Это же элементарно и так круто! Вот так и работает рисование линии с помощью целочисленных операции. Ничего сложного, не считая статью сверху.

§ Но есть нюанс

Если внезапно глянуть наверх, то можно увидеть (свернув шею), что последовательность точек по X будет такой: 2, 2, 2, 2, 3. То есть это линия, которая выглядит очень некрасиво! Как исправить? Все просто - надо делать так, чтобы проверялся выход не за пределы полного знаменателя, а через его половину!
Другими словами:

Y = Y + 1
Числитель = Числитель + (x2-x1)
ПОКА Числитель >= (Знаменатель / 2)
    Числитель = Числитель - Знаменатель
    X = X + 1

Ну либо домножить на 2

ПОКА 2*Числитель >= Знаменатель

И будет всем счастье! И все равно Брезенхэм лучше!