04. Требования, предъявляемые к алгоритмам вычерчивания отрезков. Пошаговый алгоритм разложения отрезка в растр. Разложение в растр по методу цифрового дифференциального анализатора.

Разложение отрезка в растр - процесс определения пикселей, наилучшим образом аппроксимирующих положение отрезка.

Требования к алгоритмам

1. Отрезок должен выглядить как отрезок прямой (отрезок должен быть определенной длины). В силу дискретной природы растрового дисплея выполнено всегда быть не может, однако чтобы визуально отрезок казался отрезком одной прямой, зачастую прибегают к методам устраненения ступенчатости.
2. Отрезок должен заканчиваться и начинаться в заданных точках.
3. Яркость или интенсивность не должна зависить от длины, угла наклона. Должна быть постоянной в промежутке отрезка. Данное требование не может быть выполнено всегда в силу дискретной природы дисплея. Так, например, вертикальные и горизонтальные отрезки будут выглядеть более яркими, нежели отрезок в 45 градусов, в связи с меньшим расстоянием между пикселями.
4. Алгоритмы должны работать быстро. Для этого стараются избегать операций в вещественных числах, а также заменять умножение и деление сложением и вычитанием

Пошаговый алгоритм (из материалов Курова)

Базовые алгоритмы могут использовать численные и инкрементные (пошаговые) методы. В численных методах построения кривых и отрезков используется уравнение кривой (отрезка) и частные производные. Обычно исследуются точки пересечения кривой с горизонтальными линиями (y = n, где n-константа). В пошаговых методах на каждом шаге вычисляется направление элементарного движения от текущей точки к следующей. При этом удается использовать целочисленную арифметику и избежать выполнения операций умножения и деления.

ЦДА

Прямая линия на плоскости описывается уравнением Ax + By + C, отсюда dy / dx = const.
Δy / Δx = (ук - yн) / (хк - хн). Подставляем и получаем:

y(i+1) = yi + Δy  
y(i+1) = yi +  (ук - yн) / (хк - хн) * Δx

• Единицей растра выбирается большее из приращений (Δx или Δy)

Псевдокод ЦДА

1. Ввод (xн, ун), (хк, ук)
2. dx = xк - хн, dy = ук - ун
3. Δx = |dx|, Δy = |dy|
4. Если Δx > Δy, то l = Δx, иначе l = Δy
5. dx = dx / l, dy = dy / l
6. x = хн, у = ун (х, у вещественные)
7. Цикл построения отрезка (по i от 1 до i + 1)
   7.1. Высветить точку (округление(x), округлуние(у))
   7.2. x = x + dx, y = y + dy
   7.3 Конец цикла
8. Конец. 

Алгоритм медленный из-за округления.

Следующий вопрос: 05. Алгоритмы Брезенхема разложения отрезков в растр. Простой алгоритм Брезенхема. Целочисленный алгоритм Брезенхема. Общий алгоритм Брезенхема.

Предыдущий вопрос: 03. Построение плоских кривых. Выбор шага изменения аргумента. Алгоритм построения эллипса и окружности по методу средней точки.