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

Линия соединяет две точки. Это основной элемент в графике. Чтобы нарисовать линию, вам нужно две точки, между которыми вы можете нарисовать линию. В следующих трех алгоритмах мы обозначаем одну точку линии как $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,