Цифровой дифференциальный анализатор

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

или

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

(1)

 

где x₁, y₁ и x_{2 ,} y₂ – концы разлагаемого отрезка и y_i – начальное значение для очередного шага вдоль отрезка. Фактически уравнение (1.) представляет собой рекуррентное соотношение для последовательных значений y вдоль нужного отрезка. Этот метод, используемый для разложения в растр отрезков, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо , либо (большее из приращений) выбирается в качестве единицы растра. Ниже приводится простой алгоритм, работающий во всех квадрантах:

 

Процедура разложения в растр отрезка по методу цифрового дифференциального анализатора (ЦДА)

предполагается, что концы отрезка (x₁,y₁) и (x₂,y₂) не совпадают

Integer – функция преобразования вещественного числа в целое.

Примечание: во многих реализациях функция Integer означает взятие целой части, т.е. Integer (- 8.5) = - 9, а не - 8. В алгоритме используется именно такая функция.

Sign - функция, возвращающая - 1, 0, 1 для отрицательного нулевого и положительного аргумента соответственно.

if abs (x₂ -x₁ ) ³ abs (y₂ - y₁ ) then

Длина = abs (x₂ - x₁ )

else

Длина = abs (y₂ - y₁ )

end if

полагаем большее из приращений Dx или Dy равным единице растра

Dx = (x₂ -x₁ ) / Длина

Dy = (y₂ - y₁ ) / Длина

округляем величины, а не отбрасываем дробную часть

использование знаковой функции делает алгоритм пригодным для всех квадрантов

x = x₁ + 0.5 * Sign (Dx)

y = y₁ + 0.5 * Sign (Dy)

начало основного цикла

i =1

while (i £ Длина)

Plot (Integer (x), Integer (y))

x = x + Dx

y = y + Dy

i = i + 1

end while

finish

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