2.2. Простейший алгоритм разложения в растр

Один из методов разложения отрезка в растр состоит в решении дифференциального уравнения, описывающего этот процесс. Для прямой линии имеем:

dy dx

= const

или

Δy Δx

=

y2 - y1 x2 - x1

    

Решение представляется в виде:

yi+1 = yi + Δy

yi+1 = yi +

y2 - y1 x2 - x1

Δx

где х₁, y₁ и х₂, y₂ - концы разлагаемого отрезка и y_i - начальное значение для очередного шага вдоль отрезка. Ниже приводится простой алгоритм, работающий в первом квадранте:

Процедура разложения в растр отрезка простейшим методом.
Abs (x) - функция взятия модуля числа х.
Round (x) - функция округления вещественного числа x до целого.
Plot (x,y) - функция вывода точки с координатами (x,y) на экран.

 

Длина = x2 - х1;	/ аппроксимируем длину отрезка
Dx = 1; Dy = abs((y2-y1)/(x2-x1));	/ полагаем Dx равным единице растра
x = x1; y = y1; i = 1;	/ устанавливаем координаты начальной точки
while (i < Длина); Plot (x, Round(y)); x = x + Dx y = y + Dy i = i + 1; end while finish	/ начало основного цикла

Заметим, что концевые точки при таком разложении определены точно и выбранные пикселы равномерно распределены вдоль отрезка.Однако, в некоторых случаях в отрезке, разложенным в растр простейшим методом, могут появиться разрывы, например, если выбрать такой отрезок, у которого разброс по оси Y больше разброса по оси X в несколько раз. Вдобавок предложенный алгоритм имеет тот недостаток, что он использует вещественную арифметику. В следующем разделе описан более приемлемый алгоритм.