INFONKO.RU

Алгоритмы растровой графики: алгоритмы заливки замкнутых фигур с границей заданного цвета, заливка многоугольников.

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

Важным понятием для растровой сетки является связность - возможность соединения двух пикселов растровой линией, т. e. последовательным набором пикселов. Возникает вопрос, когда пикселы (x1,y1) и (х2,у2) можно считать соседними.

Вводится два понятия связности:

4-связность: пикселы считаются соседними, если либо их x-координаты, либо их у-координаты отличаются на единицу:|x1-x2|+|y1-y2| 1

8-связность: пикселы считаются соседними, если их координаты x и y отличаются не более чем на единицу :|x1-x2| 1; |y1-y2| 1

Понятие 4-связности является более сильным: любые два 4-связных пиксела являются и 8-связными, но не наоборот. Алгоритм закраски многоуг.

Под многоугольником далее будем понимать фигуру, ограниченную на плоскости простой (непересекающейся) замкнутой ломаной. Сама ломаная задается координатами вершин Ai(xi,yi), i=1..n. Задача "закраски" многоуг. заключается в инициализации всех его внутр. точек. Наиболее простой, но и наиболее медленный алгоритм, решающий эту задачу состоит в том, чтобы проверить все точки плоскости на принадлежность многоуг-ку. Несколько ускорить этот алгоритм можно, если вместо проверки всех точек пл-ти проверять только точки минимального квадрата заключающего многоуг-к.Еще один вариант решения задачи, это алгоритм сканирования строк. Последовательно проходим все горизонт. линии пл-ти, и находим отрезки на прямой, внутренние для многоуг-ка. Для данного алгоритма достаточно искать только точки пересечения сканирующей линии с ребрами многоуг-ка. Для оптимизации алгоритма можно упорядочить ребра в порядке возрастания наибольшей из ординат концов. При перемещении сканирующей прямой сверху вниз проверке на пересечение подвергаются лишь те ребра, у которых значение макс. ординаты больше ординаты сканирующей прямой. Такой алгоритм пригоден для заполнения произвол. многоуг-ков. Но если мног-к выпуклый, то алгоритм можно упростить. Границу выпуклого многоуг-ка можно разбить на 2 ломаные "левую" и "правую" и, возможно, 2 ребра "верхнее" и "нижнее" так что каждая из боковых ломаных имеет ровно 1 пересечение с каждой сканирующей прямой. Далее, используя алгоритм Брезенхейма и одновременно генерируя растровое представление для ребер левой и правой части ломаных границ, получаем левый и правый пиксели границы многоуг-ка на каждой сканирующей горизонтальной прямой. Последовательно заполняя интервалы между этими пикселами для каждого значения ординаты от верхней строки развертки до нижней, получим растровое представление многоуг-ка.Алгоритм закраски произвол. области с затравкой.



Рассмотрим класс алгоритмов "закраски"-алгоритмы заполнения области с затравкой. В этих алгоритмах предполагается, что граница области задана на растр. пл-ти и указана одна из внутр. точек области, которая называется затравочной. Треб-ся заполнить определенным цветом связную компоненту области, содержащую затравочную точку. Данному классу алгоритмов можно сопоставить физическую интерпретацию, представить, что в затравочной точке помещен источник, заливающий всю область опред. цветом. Поэтому часто такие алгоритмы называют алгоритмами заливки. Допустим нам надо "закрасить" цветом IColor область, граница, которой имеет цвет BColor, и нам задана точка с координатами (x0,y0) в качестве затравочной.1Поместим затравочную точку на стек. 2Извлекаем координаты точки с вершины стека в переменные (x,y)

3Если Screen[x,y]=IColor, то Screen[x,y]=IColor 4Для всех соседних точек (xg,yg) повторить пункт 5 5Если Screen[xg,yg]BColor и Screen[xg,yg]IColor, то поместить точку (xg,yg) на стек. 6Если стек не пуст, то переходим к пункту 2.

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

2Извлекаем координаты точки с вершины стека в переменные (x,y)

3Заполняем максимально возможный интервал, в котором находится точка, вправо и влево вплоть до достижения граничных точек. 4Запоминаем крайнюю левую xl и крайнюю правую xr абсциссы заполненного интервала.

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

6Если стек не пуст, то переходим к пункту 2.


18.Найти экстремаль функционала

Запишем уравнение Эйлера

Подставим граничные условия

Билет 18



infonko.ru/rezhimnoe-i-operativnoe-obespechenie-otnositsya-k.html infonko.ru/rezhim-obrabotki-sili-i-momenti-sil-rezaniya.html infonko.ru/rezhim-pitaniya-pri-zanyatiyah-ozdorovitelnim-begom-i-hodboj.html infonko.ru/rezhim-raboti-asinhronnoj-mashini.html infonko.ru/rezhim-raboti-i-tehnicheskaya-proizvoditelnost.html infonko.ru/rezhim-raboti-predpriyatiya-i-fond-vremeni.html infonko.ru/rezhim-raboti-sinhronnogo-dvigatelya-pri-postoyannom-momente-i-peremennom-toke-vozbuzhdeniya.html infonko.ru/rezhim-raboti-sportivnih-sekcij.html infonko.ru/rezhim-regeneracii-informacii.html infonko.ru/rezhim-sluzhebnih-pomeshenij.html infonko.ru/rezhim-sozdat-sluzhebnuyu-zapisku-na-uregulirovanie-raznoglasij-po-razdelu-ii-pril-2.html infonko.ru/rezhim-svarki-listovogo-nastila.html infonko.ru/rezhim-ustanovit-nalichie-ili-otsutstvie-rashozhdenij-koreshok-akta.html infonko.ru/rezhim-vhozhdeniya-v-proceduru-prinyatiya-vozdushnih-vann-dlya-novichkov.html infonko.ru/rezhim-vstavki-i-zameni-simvolov.html infonko.ru/rezhisserskie-postanovochnie-priemi.html infonko.ru/rezhisserskij-zamisel-spektaklya-stepen-ego-obraznoj-konkretnosti.html infonko.ru/rezhisserskoe-i-plasticheskoe-reshenie-sceni-poedinka-v-tragedii-v-shekspira-gamlet.html infonko.ru/rezhisserskoe-i-plasticheskoe-reshenie-sceni-u-lauri-v-tragedii-a-s-pushkina-kamennij-gost.html infonko.ru/rezhissura-teatralizovannih-predstavlenij-i-prazdnikov.html