При выборе очередного пикселя окружности имеется

Обновлено: 24.01.2025

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

Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).

Окружность с центром в начале координат описывается уравнением:

X 2 + Y 2 = R 2

Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра P_i(X_i, Y_i), ближайшую к истинной окружности, так чтобы ошибка:

была минимальной. Причем, как и в алгоритме Брезенхема для генерации отрезков, выбор ближайшей точки выполняется с помощью анализа значений управляющих переменных, для вычисления которых не требуется вещественной арифметики. Для выбора очередной точки достаточно проанализировать знаки.

Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.

Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.

Рис. 1: Варианты расположения очередного пиксела окружности

При генерации окружности по часовой стрелке после занесения точки (X_i, Y_i) следующая точка может быть (см. рис. 0.1а) либо Pg = (X_i+1, Y_i) - перемещение по горизонтали, либо Pd = (X_i+1, Y_i-1) - перемещение по диагонали, либо Pv = (X_i, Y_i-1) - перемещение по вертикали.

Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:

|Dg| =| (X+1) 2 +Y 2 -R 2 |
|Dd|=| (X+1) 2 +(Y-1) 2 -R 2 |
|Dv|=| X 2 +(Y-1) 2 -R 2 |

Выбирается и заносится та точка, для которой это значение минимально.

Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.

Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный - Pg или диагональный - Pd.

Для определения того, какой пиксел выбрать Pg или Pd составим разность:

di = |Dg| - |Dd| = |(X+1) 2 + Y 2 - R 2 | - |(X+1) 2 + (Y-1) 2 - R 2 |
И будем выбирать точку Pg при di <= 0, в противном случае выберем Pd.

Рассмотрим вычисление di для разных вариантов.

Для вариантов 2 и 3:

Dg >= 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.

di = (X+1) 2 + Y 2 - R 2 + (X+1) 2 + (Y-1) 2 - R 2 ;
Добавив и вычтя (Y-1) 2 получим:

di = 2 ·[(X+1) 2 + (Y-1) 2 - R 2 ] + 2·Y - 1
В квадратных скобках стоит Dd, так что

Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.

Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.

Для определения того, какую пиксел выбрать Pd или Pv составим разность:

si = |Dd| - |Dv| = |(X+1) 2 + (Y-1) 2 - R 2 | - |X 2 + (Y-1) 2 - R 2 |
Если si <= 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.

Рассмотрим вычисление si для разных вариантов.

Для вариантов 5 и 6:

Dd > 0 и Dv <= 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.

si = (X+1) 2 + (Y-1) 2 - R 2 + X 2 + (Y-1) 2 - R 2 ;
Добавив и вычтя (X+1) 2 получим:

si = 2 ·[(X+1) 2 + (Y-1) 2 - R 2 ] - 2·X - 1
В квадратных скобках стоит Dd, так что

Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.

С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si <= 0 также выбираем диагональный пиксел.

di <= 0 - выбор горизонтального пиксела Pg

di > 0 - выбор диагонального пиксела Pd

si <= 0 - выбор диагонального пиксела Pd

si > 0 - выбор вертикального пиксела Pv

выбор диагонального пиксела Pd.

Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.

Правильные ответы выделены зелёным цветом.
Все ответы: Излагаются методы, алгоритмы и технические средства компьютерной графики. В основу изложения положены наиболее распространенные алгоритмы двумерной и трехмерной графики. Уделяется внимание также вычислительной геометрии и оценкам сложности алгоритмов.

Конечным результатом для средств компьютерной графики является:

(3) наблюдатель находится в одной точке с источником света

Чувствительность глаза к цветам (в порядке убывания) выглядит так:

Какое из перечисленных свойств не является характерным для базисного набора графических примитивов?

(1) все геометрические построения можно выполнить на основе примитивов

(2) ни один из примитивов не должен строиться через другие

Если коды концов отрезка в алгоритме Сазерленда-Коэна равны 1000 и 0100, то сколько сторон клиппирующего окна он пересекает?

В алгоритме Робертса обобщенная матрица описания многогранника, состоящего из вершин и граней, - это:

(1) матрица размерностью , построенная из координат вершин многогранника

(2) матрица размерностью , задающая связи между вершинами многогранника

(3) матрица размерностью , вектор-столбцы которой есть коэффициенты канонических уравнений плоскостей, в которых лежат грани многогранника

(4) матрица размерностью , вектор-столбцы которой являются нормалями к граням

(1) изображение, построенное из коротких отрезков прямой

(3) изображение на матрице дискретных прямоугольных элементов

Однородно закрашенная область будет казаться более яркой на:

Проектирование с помощью средств компьютерной графики - это:

(1) проектно-конструкторские работы в области архитектуры, строительства

На первом шаге алгоритма Аппеля строится матрица элементы которой показывают:

(1) какие из элементов сцены экранируют другие от наблюдателя

(3) какие из проекционных многоугольников отбрасывают тень на другие

(1) двумерный график, являющийся международным стандартом определения и измерения цвета

(2) график функции

(3) график, связывающий чувствительность глаза и длину волны

Выражение - это

В число примитивов полигональных моделей не входит:

Границы окна заданы уравнениями . Отрезок задан параметрическими уравнениями x=x_0+tl_x, \quad y=y_+0+tl_y, \quad t\in[0,1] При каком условии он обязательно пересечет прямую, содержащую верхнюю границу окна (ее уравнение )?

(1)

(2)

(3)

В алгоритме Робертса для определения того, имеют ли три грани общую вершину, используется следующий метод:

(1) строятся параметрические уравнения прямых, по которым пересекаются соответствующие плоскости, а затем отыскивается точка их пересечения

(2) строится матрица Q= \begin a_1 & a_2 & a_3 & 0 \\ b_1 & b_2 & b_3 & 0 \\ c_1 & c_2 & c_3 & 0 \\ d_1 & d_2 & d_3 & 1 \end ; если для нее существует обратная матрица , то грани имеют общую вершину и ее координаты находятся из уравнения

(3) строится параметрическое уравнение прямой пересечения двух плоскостей и отыскивается точка пересечения этой прямой с третьей плоскостью

При построении матрицы проекции на произвольную плоскость в однородных координатах используются следующие элементарные операции:

(1) сдвиг, совмещающий начало координат с его проекцией на эту плоскость

(3) сдвиг по оси на расстояние, при котором начало координат окажется на плоскости

При удалении объектов от центра проекции их изображение на картинной плоскости:

(Правильный ответ) уменьшается
увеличивается
перекашивается

Структура какого цветового пространства основана на теории, что цвет не может быть одновременно зеленым и красным или желтым и синим?

Двоичное разбиение пространства используется:

при изображении гладких поверхностей
(Правильный ответ) при изображении многогранников
(Правильный ответ) при изображении сцен, содержащих объекты, для каждого из которых уже имеется алгоритм вывода на экран

Если найдены барицентрические координаты точки внутри треугольника с вершинами , то как выглядит формула линейной интерполяции на треугольнике?

Плоскость задана уравнением , луч — уравнениями . Какая из следующих групп условий необходима для того, чтобы луч пересек плоскость?

В алгоритме клиппирования многоугольника обход вершин всегда осуществляется:

по часовой стрелке
против часовой стрелки
(Правильный ответ) направление не важно, но обход должен быть последовательным

В каком случае при использовании метода деления отрезка пополам на первом итерационном шаге дроблению будут подвергаться два отрезка?

когда исходный отрезок — полностью видимый
когда один конец отрезка лежит внутри окна
(Правильный ответ) когда отрезок имеет две точки пересечения с границами окна

Какие из следующих алгоритмов свето-теневого анализа работают в объектном пространстве?

(Правильный ответ) модифицированный алгоритм Вейлера-Азертона
алгоритм Аппеля
метод теневого буфера

Укажите плоскость, на которую осуществляется проекция с помощью следующей матрицы:

Если векторное произведение двух векторов ненулевой длины равно нулевому вектору, то эти два вектора:

(Правильный ответ) коллинеарны
взаимно перпендикулярны
компланарны

Кто из перечисленных специалистов разрабатывал алгоритмы закрашивания?

(Правильный ответ) А. Гуро
Э. Кэтмул
Дж. Варнок

Какие три цвета являются базовыми в восприятии глазом человека?

оранжевый, фиолетовый, зеленый
голубой, малиновый, желтый
(Правильный ответ) красный, зеленый, синий

Картинная плоскость — это:

плоскость, на которой стоят изображаемые предметы
(Правильный ответ) плоскость, на которой формируется видимый образ посредством проекции
плоскость в системе координат наблюдателя

Какая из следующих формул является формулой линейной интерполяции функции одной переменной ( — значения аргумента, — значения функции)?

Какой из следующих наборов данных однозначно определяет плоскость?

(Правильный ответ) три точки в пространстве не лежащие на одной прямой
точка, принадлежащая плоскости, и расстояние от плоскости до начала координат
четыре точки в пространстве

В каком случае луч пересекает сферу в двух точках (задана сфера с центром в точке и радиусом )?

В алгоритме Робертса для определения того, какая часть видимого ребра многогранника экранируется другими многогранниками, используется:

уравнение плоскости, проходящей через данное ребро и точку положения наблюдателя, и параметрическое уравнение ребра
(Правильный ответ) параметрическое уравнение ребра и параметрическое уравнение луча, идущего от наблюдателя в произвольную точку ребра
уравнения плоскостей, содержащих данное ребро и параметрическое уравнение луча, который идет от наблюдателя в произвольную точку ребра

Достоинством проекции Меркатора является то, что она:

сохраняет относительные расстояния между точками
(Правильный ответ) является конформной
сохраняет относительные масштабы материков

Какие законы используются для смешения цветов с применением координат МКО?

Менделя
Ньютона
(Правильный ответ) Грассмана

Технической основой возникновения компьютерной графики явилось:

использование в компьютере магнитной ленты как носителя информации
увеличение производительности компьютеров
(Правильный ответ) использование дисплея как устройства вывода

Векторы называются коллинеарными, если:

(Правильный ответ) они лежат на параллельных прямых
они имеют равную длину
они лежат на перпендикулярных прямых

В алгоритме Брезенхема растровой развертки окружности основные построения производятся для:

четверти окружности
половины окружности
(Правильный ответ) одной восьмой части окружности

Метод художника основан на:

предварительном выявлении частей сцены, которые являются невидимыми и которые изображать не следует
(Правильный ответ) упорядочении частей изображения по глубине и изображении всех их в порядке увеличения глубины
разбиении сцены на отдельные части, упорядочении их по глубине и изображении только ближайших к наблюдателю

Алгоритм отсечения отрезка выпуклым многоугольником начинается:

с определения, не проходит ли он через вершину многоугольника
(Правильный ответ) с анализа расположения концов отрезка по отношению к окну
с определения, является ли он параллельным одной из сторон многоугольника

К центральным проекциям относятся:

аксонометрическая
(Правильный ответ) перспективная с двумя точками схода
изометрическая
косоугольная

Границы окна заданы уравнениями . Отрезок задан параметрическими уравнениями

При каком условии он обязательно пересечет прямую, содержащую нижнюю границу окна (ее уравнение )?

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

Алгоритм Брезенхема растровой дискретизации отрезка

$\deg$

При построении растрового образа отрезка необходимо, прежде всего, установить критерии "хорошей" аппроксимации. Первое требование состоит в том, что отрезок должен начинаться и кончаться в заданных точках и при этом выглядеть сплошным и прямым (при достаточно высоком разрешении дисплея этого можно добиться). Кроме того, яркость вдоль отрезка должна быть одинаковой и не зависеть от наклона отрезка и его длины. Это требование выполнить сложнее, поскольку горизонтальные и вертикальные отрезки всегда будут ярче наклонных, а постоянная яркость вдоль отрезка опять же достигается на вертикальных, горизонтальных и наклоненных под углом в 45 линиях. И, наконец, алгоритм должен работать быстро. Для этого необходимо по возможности исключить операции с вещественными числами. С целью ускорения работы алгоритма можно также реализовать его на аппаратном уровне.

В большинстве алгоритмов используется пошаговый метод изображения, т.е. для нахождения координат очередной точки растрового образа наращивается значение одной из координат на единицу растра и вычисляется приращение другой координаты.

Задача состоит в построении отрезка, соединяющего на экране точки с координатами (будем считать, что ). Для построения отрезка прямой на плоскости с вещественными координатами можно воспользоваться уравнением прямой, проходящей через две заданные точки, которое имеет вид

$j=j_1+k(i-i_1), \quad k=(j_2-j_1)/(i_2-i_1).$

Теперь, считая, что - координаты текущей точки растрового образа, а - точное значение координаты точки отрезка, можно построить следующую точку:

Следует заметить, что целочисленная координата изменится только в том случае, если y превысит величину ( есть ближайшее к целое число, полученное в результате операции округления). Приведенный пример включает операции с вещественными числами, которые выполняются существенно медленнее, чем соответствующие целочисленные операции, а при построении растрового образа отрезка желателен алгоритм, по возможности обращающийся только к целочисленной арифметике. Кроме того, алгоритм должен работать при любом взаимном расположении концов отрезка.

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

Рис. 8.2. Связь углового коэффициента с выбором пикселя

На рис. 8.2 это иллюстрируется для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент , то при выходе из точки пересечение с прямой будет ближе к прямой , чем к прямой . Следовательно, точка растра лучше аппроксимирует прохождение отрезка, чем точка . При верно обратное.

На рис. 8.3 показано, каким образом строятся точки растра для отрезка с тангенсом угла наклона , а на рис. 8.4 - график смещения. В начале построения смещение полагается равным , а затем на каждом шаге оно наращивается на величину , и если при этом вертикальная координата точки растра увеличивается на единицу, то смещение в свою очередь уменьшается на единицу.

На рис. 8.5 приведена блок-схема алгоритма для случая . Нетрудно понять, как от этого алгоритма перейти к целочисленному: достаточно вместо величины смещения перейти к величине =2\Delta i\cdot e" />
.

Рис. 8.3. Пиксели, принадлежащие развертке отрезка

Приведем общий алгоритм Брезенхема, который учитывает все возможные случаи направления отрезка, рассматриваемого как вектор на координатной плоскости (на рис. 8.6 выделены четыре области и указаны особенности алгоритма в каждой из них).

В описании алгоритма используются следующие функции:

Предполагается, что концы отрезка не совпадают и что все используемые переменные являются целыми.

Рис. 8.5. Блок-схема одной ветви алгоритма Брезенхема

Алгоритмы Брезенхема растровой дискретизации окружности и эллипса

Алгоритм изображения окружности несколько сложнее, чем построение отрезка. Мы рассмотрим его для случая окружности радиуса с центром в начале координат. Перенесение его на случай произвольного центра не составляет труда. При построении растровой развертки окружности можно воспользоваться ее симметрией относительно координатных осей и прямых . Необходимо сгенерировать лишь одну восьмую часть окружности, а остальные ее части можно получить путем отображений симметрии. За основу можно взять часть окружности от 0 до 45 в направлении по часовой стрелке с исходной точкой построения . В этом случае координата окружности является монотонно убывающей функцией координаты .

Рис. 8.7. Ближайший пиксель при движении по окружности

При выбранном направлении движения по окружности имеется только три возможности для расположения ближайшего пикселя: на единицу вправо, на единицу вниз и по диагонали вниз (рис. 8.7). Выбор варианта можно осуществить, вычислив расстояния до этих точек и выбрав минимальное из них:

$\begin d_h=|s_h|, \quad d_v=|s_v|, \quad d_d=|s_d|, \\ s_h=(x+1)^2+y^2-r^2, \quad s_v=x^2+(y-1)^2-r^2, \quad\\ s_d=(x+1)^2+(y-1)^2-r^2. \end$

Алгоритм можно упростить, перейдя к анализу знаков величин . При диагональная точка лежит внутри окружности, поэтому ближайшими точками могут быть только диагональная и правая. Теперь достаточно проанализировать знак выражения . Если , выбираем горизонтальный шаг, в противном случае - диагональный. Если же , то определяем знак , и если , выбираем диагональный шаг, в противном случае - вертикальный. Затем вычисляется новое значение , причем желательно минимизировать вычисления не только этой величины, но и величин на каждом шаге алгоритма. Путем несложных преобразований можно получить для первого шага алгоритма, что .

После перехода в точку по диагонали новое значение вычисляется по формуле , при горизонтальном переходе , при вертикальном - .

Таким образом, алгоритм рисования этой части окружности можно считать полностью описанным (блок-схема его приведена нарис. 8.8). Все оставшиеся ее части строятся параллельно: после получения очередной точки можно инициализировать еще семь точек с координатами .

Для построения растровой развертки эллипса с осями, параллельными осям координат, и радиусами воспользуемся каноническим уравнением

$\frac<x^2> +\frac=1,$

$f(x,y)\equiv b^2 x^2+a^2 y^2 -a^2 b^2 =0.$

В отличие от окружности, для которой было достаточно построить одну восьмую ее часть, а затем воспользоваться свойствами симметрии, эллипс имеет только две оси симметрии, поэтому придется строить одну четверть всей фигуры. За основу возьмем дугу, лежащую между точками и в первом квадранте координатной плоскости.

Рис. 8.8. Блок-схема построения восьмой части окружности

В каждой точке эллипса существует вектор нормали, задаваемый градиентом функции . Дугу разобьем на две части: первая - с углом между нормалью и горизонтальной осью больше 45 (тангенс больше 1) и вторая - с углом, меньшим 45 (рис. 8.9). Движение вдоль дуги будем осуществлять в направлении по часовой стрелке, начиная с точки . Вдоль всей дуги координата является монотонно убывающей функцией от , но в первой части она убывает медленнее, чем растет аргумент, а во второй - быстрее. Поэтому при построении растрового образа в первой части будем увеличивать на единицу и искать соответствующее значение , а во второй - сначала уменьшать значение на единицу и определять соответствующее значение .

Направление нормали соответствует вектору

$grad(x,y)= \left( \frac<\partial f> <\partial x>,\frac<\partial f> <\partial y>\right) =(2b^2 x, 2a^2 y).$
Отсюда находим тангенс угла наклона вектора нормали: . Приравнивая его единице, получаем, что координаты точки деления дуги на вышеуказанные части удовлетворяют равенству . Поэтому критерием того, что мы переходим ко второй области в целочисленных координатах, будет соотношение , или, переходя к целочисленным операциям, .
Рис. 8.10. Схема перехода в первой и второй областях дуги эллипса

При перемещении вдоль первого участка дуги мы из каждой точки переходим либо по горизонтали, либо по диагонали, и критерий такого перехода напоминает тот, который использовался при построении растрового образа окружности. Находясь в точке , мы будем вычислять значение . Если это значение меньше нуля, то дополнительная точка лежит внутри эллипса, следовательно, ближайшая точка растра есть , в противном случае это точка (рис. 8.10а).

$\Delta=f(x+\frac12,y-1)$

На втором участке дуги возможен переход либо по диагонали, либо по вертикали, поэтому здесь сначала значение координаты y уменьшается на единицу, затем вычисляется и направление перехода выбирается аналогично предыдущему случаю (рис. 8.10б).

$\Delta$

Остается оптимизировать вычисление параметра , умножив его на 4 и представив в виде функции координат точки. Тогда для первой половины дуги имеем

$\begin \widetilde(x,y)\equiv 4\Delta(x,y)=4b^2(x+1)^2+a^2(2y-1)^2-4a^2 b^2, \\ \widetilde(x+1,y)=\widetilde(x,y)+4b^2(2x+3), \\ \widetilde(x+1,y-1)=\widetilde(x,y)+4b^2(2x+3)-8a^2(y-1). \end$

$\begin \widetilde(x,y)\equiv 4\Delta(x,y)=b^2(2x+1)^2+4a^2(y-1)^2-4a^2 b^2, \\ \widetilde(x+1,y)=\widetilde(x,y)+8b^2(x+1), \\ \widetilde(x+1,y-1)=\widetilde(x,y)+8b^2(x+1)-4a^2(2y+3). \end$

Все оставшиеся дуги эллипса строятся параллельно: после получения очередной точки , можно инициализировать еще три точки с координатами . Блок-схему не приводим ввиду прозрачности алгоритма.

Алгоритмы заполнения областей

Для заполнения областей , ограниченных замкнутой линией, применяются два основных подхода: затравочное заполнение и растровая развертка.

Методы первого типа исходят из того, что задана некоторая точка (затравка) внутри контура и задан критерий принадлежности точки границе области (например, задан цвет границы). В алгоритмах ищут точки, соседние с затравочной и расположенные внутри контура. Если обнаружена соседняя точка, принадлежащая внутренней области контура, то она становится затравочной и поиск продолжается рекурсивно.

Методы растровой развертки основаны на сканировании строк растра и определении, лежит ли точка внутри заданного контура области. Сканирование осуществляется чаще всего "сверху вниз", а алгоритм определения принадлежности точки заданной области зависит от вида ее границы.

Сначала рассмотрим простой алгоритм заполнения с затравкой с использованием стека. Под стеком в данном случае мы будем понимать массив, в который можно последовательно помещать значения и последовательно извлекать, причем извлекаются элементы не в порядке поступления, а наоборот: по принципу "первым пришел - последним ушел" ("first in - last out"). Алгоритм заполнения выглядит следующим образом:

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

Методы растровой развертки рассмотрим сначала в применении к заполнению многоугольников. Простейший метод построения состоит в том, чтобы для каждого пикселя растра проверить его принадлежность внутренности многоугольника. Но такой перебор слишком неэкономичен, поскольку фигура может занимать лишь незначительную часть экрана, а геометрический поиск - задача трудоемкая, сопряженная с длинными вычислениями. Алгоритм станет более эффективным, если предварительно выявить минимальный прямоугольник, в который погружен контур многоугольника, но и этого может оказаться недостаточно.

В случае, когда многоугольник, ограничивающий область, задан списком вершин и ребер (ребро определяется как пара вершин), можно предложить еще более экономный метод. Для каждой сканирующей строки определяются точки пересечения с ребрами многогранника, которые затем упорядочиваются по координате . Определение того, какой интервал между парами пересечений есть внутренний для многогранника, а какой нет, является достаточно простой логической задачей. При этом если сканирующая строка проходит через вершину многогранника, то это пересечение должно быть учтено дважды в случае, когда вершина является точкой локального минимума или максимума. Для поиска пересечений сканирующей строки с ребрами можно использовать алгоритм Брезенхема построения растрового образа отрезка.

В заключение в качестве примера приведем алгоритм закраски внутренней области треугольника, основанный на составлении полного упорядоченного списка всех отрезков, составляющих этот треугольник. Для записи горизонтальных координат концов этих отрезков будем использовать два массива " />
и " />
размерностью, равной числу пикселей растра по вертикали (рис. 8.11).

Построение начинается с инициализации массивов " />
и " />
: массив " />
заполняется нулями, а массив " />
- числом , равным числу пикселей растра по горизонтали. Затем определяем значения ,J_" />
, ограничивающие треугольник в вертикальном направлении. Теперь, используя модифицированный алгоритм Брезенхема, занесем границы отрезков в массивы " />
и " />
. Для этого всякий раз при переходе к очередному пикселю при формировании отрезка вместо его инициализации будем сравнивать его координату с содержимым -й ячейки массивов. Если [j]> i" />
, то записываем координату в массив " />
. Аналогично при условии [j]< i" />
координату записываем в массив " />
.

$\<(X_<min[j],j> Если теперь последовательно применить алгоритм Брезенхема ко всем трем сторонам треугольника, то мы получим нужным образом заполненные массивы границ. Остается только проинициализировать пиксели внутри отрезков ),\;(X_[j],j)\>$
.

Этот алгоритм можно легко распространить на случай произвольного выпуклого многоугольника.

Читайте также: