Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 225

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 219 220 221 222 223 224 < 225 > 226 227 228 229 230 231 .. 316 >> Следующая

§11.2. ЗАКРАШИВАНИЕ ЗАМКНУТЫХ ОБЛАСТЕЙ
ервая задача, на примере которой мо но показать продуктивность применения методов, основанных на рекурсии относится к области, где они исключительно широко применяются: машинной графике. При оперировании с изобра ениями зачасту возникает потребность закраивать части экрана, которе содерательно соответству т областям плоскости, ограниченнм замкнутыми кривыми. Необходимость различать область как объект представления, с которым работает пользователь, и область как часть экрана обусловлена тем, что на уровне пользовательского представления существуют понятия непрерывной кривой, замкнутости, тогда как экранное представле-
642
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
ние — это просто набор точек растра, называемых пикселями, которые различаются местоположением на экране и цветом.
Экранная область представляет собой связную группу пикселей, т. е. таку , в которой меду лбыми двумя пикселями мо но найти путь, целиком леаий в данной области. Соответственно, пуь — последовательность пикселей ni, таких, что пі и ni+1 — соседние. Области выделяются либо общим цветом своих пикселей, и тогда они называются внутренне определенными, либо цветом границы — линии, составленной из одноцветных соседних пикселей, и тогда они называются гранично определенными. Чтобы эти определения стали корректнми, необходимо указать, как понимается термин "соседние пиксели". Различаются 4-связное соседство и 8-связное соседство. В первом случае соседними считаются такие пиксели, у которых либо горизонтальная, либо вертикальная координата отличаются на единицу, во втором — такие, у которх обе координаты различа тся не более чем на 1 (допускается диагональное соседство).
В условиях приведенных определений задача закраски области ставится следующим образом. Дана замкнутая область и известны координаты какого-либо ее пикселя. Требуется, чтобы все пиксели области и только они оказались закраен одним цветом. ополнительным условием для данной задачи является то, что не делается никаких предполо ений относительно форм закраиваемой области.
Стратегия закраски внутренне определенной области, котору мо но предложить для решения задачи, заключается в следующем. Для каждого пикселя, начиная с известного, проверяется его цвет. Если цвет старый, он заменяется на новый и делается поптка запустить этот алгоритм рекурсивно для кадого из соседей. ля гранично определенных областей выбор этих е действий осуествляется по результату проверки несовпадения цвета пикселя с граничным цветом, дополненному отказом от перехода к соседу, если очередной пиксель оказался у е перекраенным. онятно, что запуск алгоритма для соседей ну но осуествлять четыре раза в случае 4-связного и восемь раз для 8-связного соседства.
и е приводится процедура закраски внутренне определенной области при 4-связном соседстве. Остальные варианты предлагается запрограммировать читател самостоятельно в качестве упранения. Чтобы не привязываться к какой-либо графической библиотеке, в представленном алгоритме вместо конкретных функции вявления и процедур задания цвета пикселя
11.2. ЗАКРАШИВАНИЕ ЗАМКНУТЫХ ОБЛАСТЕЙ
643
указываются условные2 имена: ЧитатьЦветПикселя и ПисатьЦветПикселя.
При использовании приводимой процедуры в конкретных условиях необходимо, во-первых, позаботиться о подключении соответствующей библиотеки к программе, во-вторх, заменить эти имена.
{ Pascal}
procedure FloodFill4(x,y, { координаты внутренней точки} OldColor, { цвет области до закраски}
NewColor { требуемый цвет области}
: Integer);
begin
if ЧитатьЦветПикселя (x, y ) = OldColor then begin
ПисатьЦветПикселя ( x, y, NewColor );
{ изменение цвета текуего пикселя } FloodFill4 (x, y - 1, OldColor, NewColor);
{переход к верхнему соседу } FloodFill4 (x, y + 1, OldColor, NewColor);
{переход к нижнему соседу } FloodFill4 ( x - 1, y, OldColor, NewColor );
{ переход к левому соседу } FloodFill4 ( x + 1, y, OldColor, NewColor );
{переход к правому соседу }
end
end;
/* C */
void FloodFiLL4 (
int x, y, //координаты внутренней точки
OldColor, //цвет области до закраски NewColor) //требуемый цвет области
{
if (ЧитатьЦветПикселя (x,y) == OldColor) { ПисатьЦветПикселя (x,y,NewColor); FloodFiLL4 (x, y-1, OldColor, NewColor);
//переход к верхнему соседу
Чтобы подчеркнуть их условность, они записаны на русском языке.
644
11. ,
FloodFiLL4 (x, y+1, OldColor, NewColor);
//переход к нижнему соседу FloodFiLL4 (x-1, y, OldColor, NewColor);
//переход к левому соседу FloodFiLL4 (x+1, y, OldColor, NewColor);
//переход к правому соседу
}
}
роцедура FloodFill4 достаточно проста и будет часто (но не всегда, см. упр. 1 ) работать правильно. Однако, хорошо ли она работает? Ответ на этот вопрос весьма поучителен. ри вызове ее для областей, содераих значительное количество точек, располо еннх по горизонталям и вертикалям, FloodFill4 будет взвать себя рекурсивно столько раз, сколько точек леит правее, левее, вше и ниже от текущей. К примеру, если правее текущей внутренней точки в области находится 500 точек, то глубина рекурсии, появляю-
Предыдущая << 1 .. 219 220 221 222 223 224 < 225 > 226 227 228 229 230 231 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100