ВУЗ:
Составители:
Рубрика:
Рис. 2.1. Четвёртая часть
окружности построенной
по её уравнению
Таким образом, если
1
1
+=
+ ii
xx
, то
myy
ii
+=
+1
для всех точек
),(
ii
yx
отрезка, т.е. последующие значения
x
и
y
опреде-
ляются, исходя из предыдущих значений. Если
m
> 1, то единичный шаг по
x
будет приводить к шагу по
y
, большему 1. По-
этому следует
x
и
y
поменять ролями, придавая
y
единичное приращение, а
x
будет увеличиваться на
dx
=
dy
/
m
= 1/
m.
По-
добный алгоритм растрового представления отрезка прямой назван
пошаговым алгоритмом.
Но и в этом случае мы не доби-
ваемся ощутимого прироста в быстродействии алгоритма. Остаются вещественные значения оперируемых величин
y
и
m
и
операция округления ROUND при выводе пикселей в растр.
Чтобы устранить вышеперечисленные недостатки, применяется целочисленный алгоритм Брезенхема [21] для построе-
ния отрезков прямых.
Пусть на бинарной сетке растра графического устройства вывода задан отрезок прямой (начальная точка (
X
1
,
Y
1
) и ко-
нечная точка (
X
2
,
Y
2
)), тангенс угла наклона которого находится в диапазоне 0 – 1. Для построения отрезка используют значе-
ния управляющей переменной
d
i
. На каждом шаге построения отрезка прямой значение переменной
d
i
пропорционально разно-
сти значений расстояний
s
и
t
(см. рис. 1.1). Для
i
-го шага построения
Рис. 1.1. Возможные точки для построения отрезка прямой
отрезка прямой, когда пиксель
P
i
– 1
уже известен, требуется определить какую из точек
T
i
или
S
i
необходимо выбрать. Если
s
<
t
(
s
–
t
< 0), то выбираем точку
S
i
, как наиболее близко расположенную точку к реальному векторному изображению отрез-
ка, в противном случае
T
i
.
На первом шаге работы алгоритма определяется начальное значение управляющей переменной как
dxdyd −= 2
1
, где
dy
=
Y
2
–
Y
1
и
dx
=
X
2
–
X
1
. Для каждого нового значения
1
1
+=
−ii
xx
проверяем знак управляющей переменной
i
d
:
а) если
i
d
> 0, то выбирается пиксель
T
i
, тогда
1
1
+=
−ii
yy
и для следующего шага
(
)
dxdydd
ii
−+=
+
2
1
б) если
i
d
< 0,то выбирается пиксель
S
i
, тогда
1−
=
ii
yy
и для следующего шага
dydd
ii
2
1
+=
+
.
Например, для отрезка, проведённого из точки (5, 8) в точку (9, 11), последовательными значениями
i
d
будут 2, 0, –2, 4
и 2. Установленные пиксели и идеальное прохождение отрезка показаны на рис. 1.2.
Рис. 1.2. Отрезок прямой
Для реализации алгоритма Брезенхема требуются только целые числа и минимальные арифметические целочисленные
операции процессора ЭВМ: они включают сложение, вычитание и сдвиг влево (для осуществления операции умножения на
два), что хорошо отражается на быстродействии построения отрезка прямой.
2. АЛГОРИТМ БРЕЗЕНХЕМА ДЛЯ РАСТРОВОЙ РАЗВЁРТКИ ОКРУЖНОСТИ
Существует несколько простых способов преобразования окружностей в растровую форму. Рассмотрим для простоты
окружность с центром в начале координат, для которой
x
2
+
y
2
=
R
2
. Решая это уравнение относительно
y
, получим
22
xry −±=
.
Чтобы изобразить четвёртую часть окружности, можно увеличить
x
с единичным шагом от 0 до
R
и на каждом шаге вычислять положительные значения
y
(остальные четверти изображаются сим-
метрично). Этот метод работоспособен, но не эффективен, поскольку в него входят операции умно-
жения и извлечения квадратного корня. Более того, при значениях
y
, близких к
R
, в изображении ок-
ружности появляются заметные незаполненные промежутки (рис. 2.1).
Брезенхем разработал пошаговый алгоритм построения дуг [21], который более эффективен,
чем метод построения окружности по его графику.
t
s
X
i –
1
X
i
P
i
– 1
= (
x
i
– 1
,
y
i
– 1
)
S
i
= (
x
i
– 1
+ 1, y
i – 1
)
dx
dy
xy =
T
i
= (
x
i
– 1
+ 1,
y
i
– 1
+ 1)
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
