Въведение в алгоритма за рисуване на линии

В тази статия ще видим контур на алгоритъма за рисуване на линии. Рисуването на линии на компютъра означава, че екранът на компютъра се разделя на две части редове и колони. Тези редове и колони са известни също като пиксели. В случай, че трябва да начертаем линия на компютъра, първо трябва да знаем кои пиксели трябва да са. Линията е част от права линия, която се простира в обратна посока за неопределено време. Линията се определя от две крайни точки. Плътността му трябва да бъде отделна от дължината на линията.
Формулата за прихващане на линията на наклона: Y = mx + b
В тази формула m е линия на наклона и b е прихващане на y в линията. В позиции (x1, y1) и (x2, y2) са посочени две крайни точки за линейния сегмент.

Стойността на наклона m и b може да се определи съответно
• m = y2 - y1 / x2 - x1
• т.е. M = Δy / Δx

Пример:

Крайните точки на линията са (0, 0) и (4, 12). Начертайте резултата, за да изчислите всяка стойност на y като x стъпки от 0 до 4.

Решение:

Така че имаме формула на уравнение на права: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
След това y прехващането b се намира чрез свързване на y1 и x1 с y = 3 x + b формулата, 0 = 3 (0) + b. Следователно, b = 0, така че y = 3x линия формула.
Целта е да се определи следващото x, y местоположение възможно най-бързо от предишното.

Видове алгоритъм за рисуване на линии

По-долу са дадени типовете на алгоритъма:

1. Цифров диференциален алгоритъм (DDA)

Методът на инкрементално преобразуване е алгоритъм на DDA и също така нарекохме дигитален диференциален алгоритъм (DDA). Този подход се характеризира с използването на резултатите от предишния етап при всяко изчисление.

Нека разгледаме примерите, дадени по-долу:

Пример №1

Линията на крайната точка са (x1, y1) и (x2, y2)

  • dx = x2 - x1
  • dy = y2 - y1

така че сега ще определим дължината на линията, ако abs (dx)> = abs (dy), тогава дължината = abs (dx) иначе дължината = abs (dy)

  • Δx = dx / дължина
  • Δy = dy / дължина
  • X = x1
  • Y = y1

Setpixel (кръг (x), кръг (y));

  • i = 1

докато (i <= дължина)

  • x = x + Δx;
  • y = y + Δy;

setpixel (кръг (x), кръг (y));
i = i + 1
край докато

Пример №2

Линия от крайни точки (5, 4) и (6, 9) може да се преобразува с DDA.

Решение:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Както, dx <dy тогава,
• дължина = y2 - y1 = 5
• dx = (x2 - x1) / дължина = 1/5 = 0.2
• dy = (y2-y1) / дължина = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Резултат:

X1

Y1

X2

Y2

L

Dx

Dy

аз

х

Y

резултат

3

2

4

7

5

0.2

1

0

3.5

5.5

3.5, 5.5

1

3.9

1.5

3.9, 1.5

2

4.9

3.5

4.9, 3.5

3

5.1

7.5

5.1, 7.5

4

3.7

4.5

3.7, 4.5

5

4.5

7.5

4.5, 7.5

Ограничение на алгоритма на DDA

  • Аритметиката за плаващи и заоблени точки е отнемаща време процедури.
  • Грешката при закръгляване може да доведе до разстояние от истинския път на сегмента на дълга линия до мястото на измерените пиксели.

2. Алгоритъмът на линията на Брезенхам

Алгоритъмът за преобразуване на сканиране е Bresenham-алгоритъм. Този алгоритъм предлага основното предимство на използването само на цели изчисления.

1. Крайните точки на реда и запаметете лявата крайна точка в (x1, y1)
2. За да получите параметър за решение първата стойност Δx, т.е. Dx, Δy, т.е. Dy, 2 Δy и 2 Δx.
3. Инициализирайте стартирането
4. Инициализирайте i = 1 като брояч,
В противен случай следващата точка за начертаване е (xk + 1, yk + 1) и повторете стъпка 4 (Δx - 1) пъти.
регулиране
За m> 1 можем да кажем, ако увеличаваме x всеки път, когато увеличаваме y.
След като променливата pk на решение ще бъде разрешена, формулата е много сходна, само x и y в уравнението ще бъдат заменени.

Резюме на алгоритма на линията на Bresenham

Това са следните предимства на алгоритъма на Bresenham line:
• Бърз инкрементален алгоритъм.
• Това използва само изчисления на цели числа.
DDA има следните проблеми в сравнение с алгоритъма на DDA:
• Пикселираната линия може да бъде далеч от очакваното натрупване на грешки в закръгленото състояние.
• Времето е необходимо за операции на закръгляване и аритметика с плаващи точки.

Препоръчителни статии

Това е ръководство за алгоритъм за рисуване на линии. Тук обсъждаме какво е алгоритъмът за чертане на линии заедно с различните примери. Можете също така да разгледате следните статии, за да научите повече -

  1. Алгоритми за машинно обучение
  2. SVM алгоритъм
  3. Проста линейна регресия
  4. Многовариантна регресия
  5. Топ сравнение на линейна регресия с логистична регресия

Категория:

Голяма информация