Алгоритм рисования линий - Line drawing algorithm

Две растрированные линии. Цветные пиксели показаны кружками. Вверху: монохромный экран; внизу: сглаживание Гупта-Спроулла; идеальная линия здесь рассматривается как поверхность.

В компьютерная графика, а алгоритм рисования линий является алгоритм для аппроксимации отрезок на дискретных графический СМИ, такие как пиксель -на основании отображает и принтеры. На таких носителях для рисования линий требуется приближение (в нетривиальных случаях). Базовые алгоритмы растрировать линии в один цвет. Лучшее представление с несколькими цветовые градации требует продвинутого процесса, пространственное сглаживание.

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

Декартов уравнение угла наклона для прямой линии ${ Displaystyle Y = mx + b}$ С участием $м$ представляющий наклон линии и $б$ как y-перехват. Учитывая, что две конечные точки линейного сегмента указаны в позициях ${ displaystyle (x1, y1)}$ и ${ displaystyle (x2, y2)}$ , можно определить значения наклона $м$ и Y-перехват $б$ со следующими расчетами: ${ Displaystyle м = (y2-y1) / (x2-x1)}$ так, ${ displaystyle b = y1-m * x1}$ .

Список алгоритмов рисования линий

Линии с использованием алгоритма Сяолинь Ву, показывающие "цепкий" вид.

Ниже приводится неполный список алгоритмов рисования линий:

наивный алгоритм
Цифровой дифференциальный анализатор (графический алгоритм) - Похож на простой алгоритм рисования линий, с небольшими вариациями.
Линейный алгоритм Брезенхема - оптимизирован для использования только сложений (то есть без делений или умножений); это также позволяет избежать вычислений с плавающей запятой.
Линейный алгоритм Сяолинь Ву - может выполнять пространственное сглаживание, кажется "цепким" от яркости, меняющейся по длине линии
Алгоритм Гупта-Спроулла

Наивный алгоритм рисования линий

Самый простой метод растрирования - это прямое рисование уравнения, определяющего линию.

dx = x2 − x1dy = y2 − y1для Икс от x1 к x2 делать    у = y1 + dy × (Икс − x1) / dx    сюжет(Икс, у)

Именно здесь баллы уже расставлены так, чтобы ${ displaystyle x_ {2}> x_ {1}}$ .Этот алгоритм отлично работает, когда ${ displaystyle dx> = dy}$ (т.е. наклон меньше или равен 1), но если ${ displaystyle dx$ (т. е. наклон больше 1), линия становится довольно разреженной с большим количеством промежутков, и в предельном случае ${ displaystyle dx = 0}$ , произойдет исключение деления на ноль.

Наивный алгоритм рисования линий неэффективен и поэтому медленен на цифровом компьютере. Его неэффективность связана с количеством операций и использованием вычислений с плавающей запятой. Алгоритмы рисования линий, такие как Bresenham или Ву вместо этого предпочтительнее.

использованная литература

Основы компьютерной графики, 2-е издание, А.К. Питерс Питер Ширли