Р а с т р — совокупность цветов и оттенков в виде прямоугольной матрицы. Их количество, для конкретной графической системы, зависит от видеоадаптера, установленной палитры и др. факторов. Матрица может быть сеткой или целочисленной решеткой. Большинство графических библиотек обладают набором простейших алгоритмов (преобразование идеального объекта в растровый образ, обработка растра), однако этого недостаточно. Введем некоторые важные понятия.
•С в я з н о с т ь — возможность соединения двух пикселей растровой линией в виде последовательного набора. Остается уточнить — когда два пикселя (x1, y1) и (x2, y2) будут связными. Связность классифицируют на:
— 4-х связность (для пикселов, у которых координаты по “x” и по “y” отличаются в сумме на 1. Т.е. верно соотношение:
(1) |x1 — x2| + |y1 — y2| ? 1.
— 8-и связность (для пикселов, у которых координаты по “x” или по “y” отличаются не более чем на 1. Для них справедливо:
(2) |x1 — x2| ? 1, |y1 — y2| ? 1. Четырехсвязность более сильное понятие, чем восьмисвязность, т.е. любой 4-х связный объект будет и 8-ми связным (но не наоборот).
Простой пошаговый алгоритм.
В качестве линии на растровой сетке выступает набор пикселов P1, P2, … Pn , где любые два Pi и Pi+1 — являются смежными. Поэтому наилучшее изображение линии будет для горизонтального, вертикального или наклонного (под ? 45?) расположения. В остальных случаях будет проявляться “эффект ступенчатости”. Выполнение построения линий для других углов требует вычислений (нахождения ?), и потому идет медленно. Для реализации оптимальных алгоритмов используют разные способы.
Например — п о ш а г о в ы й м е т о д на псевдокоде выглядит так:
позиция = начало
шаг = приращение
1 if позиция — конец < точность then 4
if позиция > конец then 2
if позиция < конец then 3
2 позиция = позиция — шаг
go to 1
3 позиция = позиция + шаг
go to 1
4 finish