Представление линии в квадратном растре - История изменений

Nadya.cats: /* Код */

2022-10-31T19:26:49Z

Код

← Предыдущая		Версия 19:26, 31 октября 2022
Строка 14:		Строка 14:
	== Код ==		== Код ==
	<br>1. Создаем переменные d, dx, dy, где		<br>1. Создаем переменные d, dx, dy, где
	<br><b>d</b> - величина, которая показывает, где прямая пересекла ~~пиксел~~.		<br><b>d</b> - величина, которая показывает, где прямая пересекла пиксель.
	<br><b>x</b> - координата первого ~~пиксела~~ по оси x.		<br><b>x</b> - координата первого пикселя по оси x.
	<br><b>y</b> - координата первого ~~пиксела~~ по оси y.		<br><b>y</b> - координата первого пикселя по оси y.

	<br>2. Заходим в цикл, в котором движемся по x до момента, пока не дойдем до конца отрезка. Мы предполагаем, что координата конца больше координаты начала по x. Если же наоборот, то можно поменять их местами.		<br>2. Заходим в цикл, в котором движемся по x до момента, пока не дойдем до конца отрезка. Мы предполагаем, что координата конца больше координаты начала по x. Если же наоборот, то можно поменять их местами.
	<br>3. Закрашиваем ~~нынешний пиксел~~.		<br>3. Закрашиваем текущий пиксель.
	<br>4. Изменяем величину d, чтобы показать пересечение стенки отрезком в данном пикселе.		<br>4. Изменяем величину d, чтобы показать пересечение стенки отрезком в данном пикселе.
	<br>4.1. Если у нас d ≥ 0, то увеличиваем y(то есть поднимаемся вверх).		<br>4.1. Если у нас d ≥ 0, то увеличиваем y(то есть поднимаемся вверх).

Nadya.cats: /* Алгоритм */

2022-10-31T14:56:56Z

Алгоритм

← Предыдущая		Версия 14:56, 31 октября 2022
Строка 5:		Строка 5:
	== Алгоритм ==		== Алгоритм ==
	Мы работаем с отрезками(экран компьютера не может быть бесконечным).		Мы работаем с отрезками(экран компьютера не может быть бесконечным).
	По условию нам даны начало и конец отрезка. Угол поворота ~~отрезка~~ может быть любым. Обозначим ~~его~~ за <math>\alpha</math>.		По условию нам даны начало и конец отрезка. Угол его поворота может быть любым. Обозначим за <math>\alpha</math>.
	Давайте рассмотрим случай, где <math>\alpha = \frac{\pi}{4}</math>:<br>Закрасим первый ~~пиксел~~. Если бы мы строили отрезок в реальной жизни, то он бы пересекал стенки клеток в разных местах. Будем опираться на этот факт и скажем, что если отрезок пересекает стенку клетки ниже середины, то мы остаемся на той же строке и закрашиваем соседнюю клетку(соседний ~~пиксел~~). Если же отрезок пересекает стенку клетки выше половины, то сдвигаемся вправо, а потом вверх(т.е. по диагонали) и закрашиваем этот ~~пиксел~~. <br>		Давайте рассмотрим случай, где <math>\alpha = \frac{\pi}{4}</math>:<br>Закрасим первый пиксель. Если бы мы строили отрезок в реальной жизни, то он бы пересекал стенки клеток в разных местах. Будем опираться на этот факт и скажем, что если отрезок пересекает стенку клетки ниже середины, то мы остаемся на той же строке и закрашиваем соседнюю клетку(соседний пиксель). Если же отрезок пересекает стенку клетки выше половины, то сдвигаемся вправо, а потом вверх(т.е. по диагонали) и закрашиваем этот пиксель. <br>
	Обозначим разность координаты конца и координаты начала по оси x - <b>dx</b>. Соответственно по оси y - <b>dy</b>		Обозначим разность координаты конца и координаты начала по оси x - <b>dx</b>. Соответственно по оси y - <b>dy</b>

	Так как мы работаем с углом <math>\alpha = 45^{\circ}</math> заметим, что всегда должно выполняться условие <b>dx</b> ≥ <b>dy</b>.		Так как мы работаем с углом <math>\alpha = 45^{\circ}</math> заметим, что всегда должно выполняться условие <b>dx</b> ≥ <b>dy</b>.
	----		----

	== Код ==		== Код ==
	<br>1. Создаем переменные d, dx, dy, где		<br>1. Создаем переменные d, dx, dy, где

T.o.r.t.i.k1: Новая страница: «== Алгоритм Брезенхема == Алгоритм Брезенхема - алгоритм, который позволяет построить пря...»

2022-10-30T21:01:52Z

Новая страница: «== Алгоритм Брезенхема == Алгоритм Брезенхема - алгоритм, который позволяет построить пря...»

Новая страница

== Алгоритм Брезенхема ==
Алгоритм Брезенхема - алгоритм, который позволяет построить прямую на мониторе, независимо от угла наклона прямой. Это эффективный метод, поскольку он включает в себя только целочисленные операции сложения, вычитания и умножения.

== Алгоритм ==
Мы работаем с отрезками(экран компьютера не может быть бесконечным).
По условию нам даны начало и конец отрезка. Угол поворота отрезка может быть любым. Обозначим его за <math>\alpha</math>.
Давайте рассмотрим случай, где <math>\alpha = \frac{\pi}{4}</math>: Закрасим первый пиксел. Если бы мы строили отрезок в реальной жизни, то он бы пересекал стенки клеток в разных местах. Будем опираться на этот факт и скажем, что если отрезок пересекает стенку клетки ниже середины, то мы остаемся на той же строке и закрашиваем соседнюю клетку(соседний пиксел). Если же отрезок пересекает стенку клетки выше половины, то сдвигаемся вправо, а потом вверх(т.е. по диагонали) и закрашиваем этот пиксел. 
Обозначим разность координаты конца и координаты начала по оси x - dx. Соответственно по оси y - dy

Так как мы работаем с углом <math>\alpha = 45^{\circ}</math> заметим, что всегда должно выполняться условие dx ≥ dy.
----
== Код ==
 1. Создаем переменные d, dx, dy, где
 d - величина, которая показывает, где прямая пересекла пиксел.
 x - координата первого пиксела по оси x.
 y - координата первого пиксела по оси y.

 2. Заходим в цикл, в котором движемся по x до момента, пока не дойдем до конца отрезка. Мы предполагаем, что координата конца больше координаты начала по x. Если же наоборот, то можно поменять их местами.
 3. Закрашиваем нынешний пиксел.
 4. Изменяем величину d, чтобы показать пересечение стенки отрезком в данном пикселе.
 4.1. Если у нас d ≥ 0, то увеличиваем y(то есть поднимаемся вверх).
 5. Инкрементируем x, чтобы перейти вправо.
<code>
d = 2*dy-dx;
x = x1; y = y1;
do {
PutPixel(x, y);
if (d<0)
d += 2*dy;
else{
d += 2*(dy-dx);
++y;
}
++x;
} while(x<=x2);</code>

== Важно ==
 Если угол наклона более 45, то dx ≤ dy, следовательно, алгоритм "разворачивается" и мы начинаем идти не по x, а по y. В коде переменные поменяются местами.
 Если угол наклона отрицательный, то мы идем не вверх(++y), а вниз(--y).