Заполнение многоугольника В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана. Существует две разновидности заполнения: первая, связанная как с интерактивной работой, так и с программным синтезом изображения, служит для заполнения внутренней части многоугольника, заданного координатами его вершин. вторая, связанная в первую очередь с интерактивной работой, служит для заливки области, которая либо очерчена границей с кодом пиксела, отличающимся от кодов любых пикселов внутри области, либо закрашена пикселами с заданным кодом; В данном разделе рассмотрим алгоритм заполнения многоугольника. В следующем разделе будут рассмотрены алгоритмы заливки области. Простейший способ заполнения многоугольника, заданного координатами вершин, заключается в определении принадлежит ли текущий пиксел внутренней части многоугольника. Если принадлежит, то пиксел заносится. Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360?,если вне - 0? (рис. ). Рис. 0.4.1: Определение принадлежности пиксела многоугольнику Вычисление принадлежности должно производиться для всех пикселов экрана и так как большинство пикселов скорее всего вне многоугольников, то данный способ слишком расточителен. Объем лишних вычислений в некоторых случаях можно сократить использованием прямоугольной оболочки - минимального прямоугольника, объемлющего интересующий объект, но все равно вычислений будет много. Другой метод определения принадлежности точки внутренней части многоугольника будет рассмотрен ниже при изучении отсечения отрезков по алгоритму Кируса-Бека. Построчное заполнение Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Yi, Yi+1, Yi+2 на рис. ). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки. Рис. 0.4.2: Построчная закраска многоугольника Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Yi и Yi+1 на рис. 0.2). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра: Xi+1 = Xi + 1/k (тангенс угла наклона ребра - k = dy/dx, так как dy = 1, то 1/k = dx). Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина. Учет когерентности строк и ребер позволяет построить для заполнения многоугольников различные высокоэффективные алгоритмы построчного сканирования. Для каждой строки сканирования рассматриваются только те ребра, которые пересекают строку. Они задаются списком активных ребер (САР). При переходе к следующей строке для пересекаемых ребер перевычисляются X-координаты пересечений. При появлении в строке сканирования вершин производится перестройка САР. Ребра, которые перестали пересекаться, удаляются из САР, а все новые ребра, пересекаемые строкой заносятся в него. Общая схема алгоритма, динамически формирующего список активных ребер и заполняющего многоугольник снизу-вверх, следующая: Подготовить служебные целочисленные массивы Y-координат вершин и номеров вершин. Совместно отсортировать Y-координаты по возрастанию и массив номеров вершин для того, чтобы можно было определить исходный номер вершины. Определить пределы заполнения по оси Y - Y_мin и Y_max. Стартуя с текущим значением Y_tek = Y_min, исполнять пункты 4-9 до завершения раскраски. Определить число вершин, расположенных на строке Y_tek - текущей строке сканирования. Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя информацию о соседних вершинах. Для каждого ребра в список активных ребер заносятся: максимальное значение Y-координаты ребра, приращение X-координаты при увеличении Y на 1, начальное значение X-координаты. Если обнаруживаются горизонтальные ребра, то они просто закрашиваются и информация о них в список активных ребер не заносится. Если после этого обнаруживается, что список активных ребер пуст, то заполнение закончено. По списку активных ребер определяется Y_след - Y-координата ближайшей вершины. (Вплоть до Y_след можно не заботиться о модификации САР а только менять X-координаты пересечений строки сканирования с активными ребрами). В цикле от Y_tek до Y_след: выбрать из списка активных ребер и отсортировать X-координаты пересечений активных ребер со строкой сканирования; определить интервалы и выполнить закраску; перевычислить координаты пересечений для следующей строки сканирования. Проверить не достигли ли максимальной Y-координаты. Если достигли, то заливка закончена, иначе выполнить пункт . Очистить список активных ребер от ребер, закончившихся на строке Y_след и перейти к пункту 4. В Приложении 5 приведены две подпрограммы заполнения многоугольника - V_FP0 и V_FP1. Первая реализует данный (простейший) алгоритм. Эта программа вполне работоспособна, но генерирует двух и трехкратное занесение части пикселов. Это мало приемлемо для устройств вывода типа матричных или струйных принтеров. В отличие от V_FP0, в программе V_FP1 используется более сложный алгоритм формирования списка активных ребер, обеспечивающий практически полное отсутствие дублирований (рис. ). Рис. 0.4.3: Сравнение алгоритмов заполнения многоугольника Сортировка методом распределяющего подсчета Понятно, что одна из важнейших работ в алгоритме построчного сканирования - сортировка. В связи с заведомо ограниченной разрешающей способностью растровых дисплеев (не более 2048) иногда целесообразно использовать чрезвычайно эффективный алгоритм сортировки методом распределяющего подсчета. Для рассмотрения алгоритма предположим, что надо отсортировать числа, заданные в массиве с именем "Исходный_массив"; количество сортируемых чисел задается скаляром "Кол-во_чисел"; сортируемые числа J удовлетворяют условию: 0 ? J < Max_число. Для сортировки потребуются описания: int Max_число; /* Верхняя граница значений */ int *Повтор; /* Длина этого массива = Max_число */ int Кол_чисел; /* Кол-во сортируемых чисел */ int *Исходный_массив; /* Длина этого массива >= Кол_чисел */ int *Результат; /* Длина этого массива >= Кол_чисел */ int ii,jj, kk; /* Рабочие переменные */ Обнуляется служебный массив для подсчета числа повторений исходных кодов. for (ii=0; ii Сортируемый массив просматривается и вычисляется количество раз повторений каждого числа: for (ii= 0; ii < Кол_чисел; ++ii) { jj= Исходный_массив[ii]; Повтор[jj]= Повтор[jj] + 1; } Суммируется количество повторений каждого числа, так что значение Повтор[J] даст начальное расположение группы чисел, равных J, в отсортированном массиве: jj= 0; for (ii=0; ii jj= jj + Повтор[ii]; Повтор[ii]= jj; } Просматривается исходный массив и числа из него заносятся в массив результатов той же длины. Индекс занесения числа J в массив результатов равен значению J-го элемента массива Повтор. После занесения числа J значение Повтор[J] уменьшается на 1: for (ii= 0; ii < Кол_чисел; ++ii) { jj= Исходный_массив[ii]; kk= Повтор[jj]; Результат[kk]= jj; Повтор[jj]= Повтор[jj] - 1; } ЗАЛИВКА ОБЛАСТИ С ЗАТРАВКОЙ Как уже отмечалось, для приложений, связанных в основном с интерактивной работой, используются алгоритмы заполнения области с затравкой. При этом тем или иным образом задается заливаемая (перекрашиваемая) область, код пиксела, которым будет выполняться заливка и начальная точка в области, начиная с которой начнется заливка. По способу задания области делятся на два типа: гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселов границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселы внутренней части области налагаются два условия - они должны быть отличны от кода пикселов границы и кода пиксела перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселами с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться; внутренне-определенные, нарисованные одним определенным кодом пиксела. При заливке этот код заменяется на новый код закраски. В этом состоит основное отличие заливки области с затравкой от заполнения многоугольника. В последнем случае мы сразу имеем всю информацию о предельных размерах части экрана, занятой многоугольником. Поэтому определение принадлежности пиксела многоугольнику базируется на быстро работающих алгоритмах, использующих когерентность строк и ребер (см. предыдущий раздел). В алгоритмах же заливки области с затравкой нам вначале надо прочитать пиксел, затем определить принадлежит ли он области и если принадлежит, то перекрасить. Заливаемая область или ее граница - некоторое связное множество пикселов. По способам доступа к соседним пикселам области делятся на 4-х и 8-ми связные. В 4-х связных областях доступ к соседним пикселам осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пикселы области. Важно отметить, что для 4-х связной прямоугольной области граница 8-ми связна (рис. а) и наоборот у 8-ми связной области граница 4-х связна (см. рис. б). Поэтому заполнение 4-х связной области 8-ми связным алгоритмом может привести к "просачиванию" через границу и заливке пикселов в примыкающей области. В общем, 4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно. Так область на рис. а мы можем заполнить любым алгоритмом, а область на рис. б, состоящую из двух примыкающих 4-х связных областей можно заполнить только 8-ми связным алгоритмом. Рис. 0.5.1: Связность областей и их границ С использованием связности областей и стека можно построить простые алгоритмы закраски как внутренне, так и гранично-определенной области. В [] рассматриваются совсем короткие рекурсивные подпрограммы заливки. В [] - несколько более длинные итеративные подпрограммы. Простой алгоритм заливки Рассмотрим простой алгоритм заливки гранично-определенной 4-х связной области. В [] приведена рекурсивная реализация подпрограммы заливки 4-х связной гранично-определенной области: oid V_FAB4R (grn_pix, new_pix, x_isx, y_isx) int grn_pix, new_pix, x_isx, y_isx; { if (getpixel (x_isx, y_isx) ? grn_pix && getpixel (x_isx, y_isx) ? new_pix) { putpixel (x_isx, y_isx, new_pix); V_FAB4R (grn_pix, new_pix, x_isx+1, y_isx); V_FAB4R (grn_pix, new_pix, x_isx, y_isx+1); V_FAB4R (grn_pix, new_pix, x_isx-1, y_isx); V_FAB4R (grn_pix, new_pix, x_isx, y_isx-1); } } /* V_FAB4R */ Заливка выполняется следующим образом: определяется является ли пиксел граничным или уже закрашенным, если нет, то пиксел перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пиксела. Полный текст тестовой программы V_FAB4R с использованием этой подпрограммы приведен в Приложении 6. Понятно, что несмотря на простоту и изящество программы, рекурсивная реализация проигрывает итеративной в том, что требуется много памяти для упрятывания вложенных вызовов. В [] приведен итеративный алгоритм закраски 4-х связной гранично-определенной области. Логика работы алгоритма следующая: Поместить координаты затравки в стек Пока стек не пуст Извлечь координаты пиксела из стека. Перекрасить пиксел. Для всех четырех соседних пикселов проверить является ли он граничным или уже перекрашен. Если нет, то занести его координаты в стек. На рис.  а) показан выбранный порядок перебора соседних пикселов, а на рис.  б) соответствующий ему порядок закраски простой гранично-определенной области. a) Порядок перебора соседних пикселов б) Порядок заливки области Рис. 0.5.2: Заливка 4-х связной области итеративным алгоритмом Ясно, что такой алгоритм экономнее, так как в стек надо упрятывать только координаты. Рассмотренный алгоритм легко модифицировать для работы с 8-ми связными гранично-определенными областями или же для работы с внутренне-определенными. Программа V_FAB4, реализующая данный алгоритм, приведена в Приложении 6. Сравнительные прогоны тестовых программ V_FAB4R и V_FAB4 подтвердили соображения о неэкономности рекурсивного алгоритма: при стандартном окне стека в 64 K с помощью рекурсивной программы можно закрасить квадратик не более чем 57×57 пикселов. Итеративная же программа V_FAB4 при тех же условиях позволяет закрасить прямоугольник размером 110×110 истратив на массив координат 16382 байта. Как уже отмечалось, очевидный недостаток алгоритмов непосредственно использующих связность закрашиваемой области - большие затраты памяти на стек, так как на каждый закрашенный пиксел в стеке по максимуму будет занесена информация о еще трех соседних. Кроме того, информация о некоторых пикселах может записываться в стек многократно. Это приведет не только к перерасходу памяти, но и потере быстродействия за счет многократной раскраски одного и того же пиксела. Значительно более экономен далее рассмотренный построчный алгоритм заливки. Построчный алгоритм заливки с затравкой Использует пространственную когерентность: пикселы в строке меняются только на границах; при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел. Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пиксела [], что приводит к существенному уменьшению размера стека. Последовательность работы алгоритма для гранично определенной области следующая: Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ, соответственно. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек. То же самое проделывается для строки выше закрашиваемой. В Приложении 6 приведена процедура V_FAST, реализующая рассмотренный алгоритм. За счет несложной модификации служебных процедур запроса и записи строк изображения, данная процедура может заливать изображение, размещенное в файле. Вперед  >>>  1  2  3  4   8  Комментарии к статье  8 8  Обсудить в чате