Алгоритм генерации линии

Линия соединяет две точки. Это основной элемент в графике. Чтобы нарисовать линию, вам нужно две точки, между которыми вы можете нарисовать линию. В следующих трех алгоритмах мы обозначаем одну точку линии как $ X_ {0}, Y_ {0} $, а вторую точку линии как $ X_ {1}, Y_ {1} $.

Алгоритм DDA

Алгоритм цифрового дифференциального анализатора (DDA) - это простой алгоритм генерации линий, который объясняется здесь шаг за шагом.

Шаг 1 - Получить ввод двух конечных точек $ (X_ {0}, Y_ {0}) $ и $ (X_ {1}, Y_ {1}) $.

Шаг 2 - Рассчитайте разницу между двумя конечными точками.

dx = X 1 - X 0
dy = Y 1 - Y 0

Шаг 3 - Исходя из рассчитанной разницы в шаге 2, вам необходимо определить количество шагов для помещения пикселя. Если dx> dy, то вам нужно больше шагов в координате x; в противном случае по координате у.

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

Шаг 4 - Рассчитать приращение по координате х и координате у.

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

Шаг 5 - Поместите пиксель, успешно увеличивая координаты x и y соответственно, и завершите рисование линии.

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Линия Брезенхэма

Алгоритм Брезенхэма - это еще один алгоритм преобразования инкрементного сканирования. Большим преимуществом этого алгоритма является то, что он использует только целочисленные вычисления. Перемещаясь по оси x в единичных интервалах и на каждом шаге выбирайте между двумя разными координатами y.

Например, как показано на следующем рисунке, из позиции (2, 3) необходимо выбрать между (3, 3) и (3, 4). Вам бы хотелось, чтобы точка была ближе к исходной линии.

В позиции выборки $ X_ {k} + 1, $ вертикальное отделение от математической линии обозначено как $ d_ {upper} $ и $ d_ {lower} $.

дуппер и пуховик

На приведенном выше рисунке координата y на математической линии в $ x_ {k} + 1 $ равна -

Y = m ($ X_ {k} $ + 1) + b

Итак, $ d_ {upper} $ и $ d_ {lower} $ определяются следующим образом:

$$ d_ {lower} = y-y_ {k} $$

$$ = m (X_ {k} + 1) + b - Y_ {k} $$

и

$$ d_ {upper} = (y_ {k} + 1) - y $$

$ = Y_ {k} + 1 - m (X_ {k} + 1) - b $

Вы можете использовать их, чтобы принять простое решение о том, какой пиксель ближе к математической линии. Это простое решение основано на разнице между двумя позициями пикселей.

$$ d_ {нижний} - d_ {верхний} = 2 м (x_ {k} + 1) - 2y_ {k} + 2b - 1 $$

Заменим m на dy / dx, где dx и dy - различия между конечными точками.

$$ dx (d_ {нижний} - d_ {верхний}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dy + 2dx (2b-1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Таким образом, параметр решения $ P_ {k} $ для k- го шага вдоль линии определяется как -

$$ p_ {k} = dx (d_ {нижний} - d_ {верхний}) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Знак параметра решения $ P_ {k} $ такой же, как и у $ d_ {lower} - d_ {upper} $.

Если $ p_ {k} $ отрицательно, выберите нижний пиксель, в противном случае выберите верхний пиксель.

Помните, что изменения координат происходят вдоль оси x с шагом в единицу, поэтому вы можете делать все с помощью целочисленных вычислений. На этапе k + 1 параметр решения задается как -

$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$

Вычитая из этого $ p_ {k} $, мы получаем -

$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$

Но $ x_ {k + 1} $ - это то же самое, что $ (xk) + 1 $. Итак -

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$

Где $ Y_ {k + 1} - Y_ {k} $ равен 0 или 1 в зависимости от знака $ P_ {k} $.

Первый параметр решения $ p_ {0} $ оценивается как $ (x_ {0}, y_ {0}) $ и определяется как -

$$ p_ {0} = 2dy - dx $$

Теперь, учитывая все вышеперечисленные моменты и расчеты, вот алгоритм Брезенхема для наклона m <1 -

Шаг 1 - Введите две конечные точки линии, сохраняя левую конечную точку в $ (x_ {0}, y_ {0}) $.

Шаг 2 - Постройте точку $ (x_ {0}, y_ {0}) $.

Шаг 3 - Рассчитайте константы dx, dy, 2dy и (2dy - 2dx) и получите первое значение для параметра решения как -

$$ p_ {0} = 2dy - dx $$

Шаг 4 - На каждом $ X_ {k} $ вдоль линии, начиная с k = 0, выполните следующий тест -

Если $ p_ {k} $ <0, следующая точка на графике - это $ (x_ {k} +1, y_ {k}) $ и

$$ p_ {k + 1} = p_ {k} + 2dy $$ В противном случае,

$$ (x_ {k}, y_ {k} +1) $$

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$

Шаг 5 - Повторите шаг 4 (дх - 1) раз.

При m> 1 выясните, нужно ли увеличивать x при каждом увеличении y.

После решения уравнение для параметра решения $ P_ {k} $ будет очень похожим, только x и y в уравнении взаимозаменяются.

Алгоритм средней точки

Алгоритм средней точки обусловлен Брезенхэмом, который был изменен Питтуэем и Ван Акеном. Предположим, что вы уже поместили точку P в координату (x, y), а наклон линии равен 0 ≤ k ≤ 1, как показано на следующем рисунке.

Теперь вам нужно решить, поставить ли следующую точку в точке E или N. Это можно выбрать путем определения точки пересечения Q, ближайшей к точке N или E. Если точка пересечения Q находится ближе всего к точке N, то N рассматривается как следующий пункт; в противном случае Е.

Алгоритм средней точки

Чтобы определить это, сначала вычислите среднюю точку M (x + 1, y + ½). Если точка пересечения Q линии с вертикальной линией, соединяющей Е и N, находится ниже М, то в качестве следующей точки выберите Е; в противном случае примите N в качестве следующего пункта.

Чтобы проверить это, нам нужно рассмотреть неявное уравнение -

F (x, y) = mx + b - y

Для положительного m в любом данном X,

  • Если у на линии, то F (x, y) = 0
  • Если у выше линии, то F (х, у) <0
  • Если у ниже линии, то F (х, у)> 0
Неявное уравнение