Алгоритм №1. Несимметричный цифровой дифференциальный анализатор (несимметричный ЦДА)

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

Алгоритм «несимметричный ЦДА» использует эту величину, чтобы рассчитать значение смещения по одной из координат, при смещении по другой на 1. Этот алгоритм можно описать следующей последовательностью действий (подразумевается, что хотя бы одно из значений или не равно нулю).

1. Рассчитаем величину и определим, ось, вдоль которой будем продвигаться, следующим образом:
Если , то наш отрезок является вертикальным, тогда , продвигаться будем вдоль оси .
Если , то наш отрезок является горизонтальным, тогда , и продвигаться будем вдоль оси .
Если , тогда, продвигаться будем вдоль оси .
В противном случае, , и продвигаться будем вдоль оси .

2. Подсветим пиксель с координатами .

3. Увеличим координату, соответствующую оси, вдоль которой продвигаемся, на 1 (-1), а другую на , и подсветим пиксель, соответствующий этим координатам.

4. Повторять пункт 3, до тех пор, пока не нарисуем весь отрезок.

Рассмотрим работу алгоритма на следующих примерах рис. 1.2.

Рис. 1.2. Генерация отрезков несимметричным ЦДА.

Отрезок а):

1. Поскольку , то , продвигаться будем
вдоль оси y.

2. Подсветим пиксель с координатами (3, 1).

3. Увеличим на 1, а на . Получим . Подсветим пиксель с координатами (3 (), 2).

4. Далее повторяем пункт 3, пока не нарисуем весь отрезок.

На следующем шаге получим . Подсветим пиксель (3, 2). Далее получим . Подсветим пиксель (4, 2) и т.д.

Отрезок б):

1. Поскольку , то , продвигаться будем
вдоль оси x.

2. Подсветим пиксель с координатами (7, 1).

3. Увеличим на 1, а на 0,5 Получим . Подсветим пиксель с координатами (8, 2 (1,5≈2)).

4. Далее повторяем пункт 3, пока не нарисуем весь отрезок.

На следующем шаге получим . Подсветим пиксель (9, 2). Далее получим . Подсветим пиксель (10, 3) и т.д.