Рекурсия

← →
Ketmar © (2006-08-28 00:12) [40]

конечно, алгоритм далёк от шибко оптимального, и на больших областях всё-же сожрёт весь стек. да и скоростью не блещет. зато мало кода и ясно. %-)

← →
RASkov (2006-08-28 00:36) [41]

> [40] Ketmar © (28.08.06 00:12)

Спасибо большое. Сейчас будем в очередной раз "попробывать"... Интересно твой зальет фигуру отличную от прямоугольника т.е. с впадинами и иже сними... И все же областя могут быть большими... скорость собственно не важно. Лишь бы стека хватило:) Согласен, код меньше, без указателей и без доп. массивов, поэтому мож чего и своего на этом примере сворганю....
Вот пишу ответ и читаю [39] Ketmar © (28.08.06 00:10)....чето сомнения какието не хорошие... да ладно сейчас проверю. Спасибо. Если что тема не закрыта.

← →
Ketmar © (2006-08-28 01:27) [42]

> [41] RASkov (28.08.06 00:36)
если я правильно понял задачу -- зальёт. форма фигуры не важна. %-)

← →
RASkov (2006-08-28 01:34) [43]

> [39] Ketmar © (28.08.06 00:10)

Сорри за сомнения... Супер. То что надо. Это был пятый способ, до этого 4 прцеДуры закомментированы (удалить надо срочно) в моем коде. Твой способ заполняет любой сложности фигуры... есть некоторые нюансы, при некоторых обстоятельствах происходит вытекание из дыр (про дыры см [10]) при некоторых нет... но это нормально. Для моего случая. Исправил, как считаю, ошибку:
// а вообще надо что-то делать? if (y < 0) or (y >= MAX_Y) or (map[y, x] = srcColor) or (map[y, x] = dstColor) then exit;

Здесь всегда происходит выход :) Ну конечно же Map[x,y]=srcColor...
Ну это мелочи жизни... Еще раз ОГРОМНОЕ СПАСИБО. Вот уж от кого кого а от тебя не ожидал:))) Имеею ввиду твою лень:))

> [36] Ketmar © (28.08.06 00:00)
> > [35] RASkov (27.08.06 23:52)
> ты будешь смеяться, но я сейчас даже код дам. %-)

Я смеюсь... только над собой. И офигиваю над твоим кодом... до ужаса просто и РАБОТАЕТ как надо... и да, я согласен с [40] Ketmar © (28.08.06 00:12)хотя... у меня глюков не вызвало...да и скорость нормальная. По всей видимости тема ЗАКРЫТА.

← →
Ketmar © (2006-08-28 01:45) [44]

> [43] RASkov (28.08.06 01:34)
ну да. ступил. %-) назову это тестом на сообразительность. %-)

а код я дал по причинам чисто ностальгическим. вспомнилось, почему-то, как сам в своё время долго думал над почти такой же задачей. %-)

а "вытекания" и прочее... на самом деле так и должно быть. потому что внутри фигуры распространение идёт по 8-ми направлениям, а на границах -- только по 4-м -- ортам. думаю, если ты понял код, то большого труда исправления не потребуют. %-)

← →
Vovan#1 (2006-08-28 01:54) [45]

2 RASkov:

Скачай по одному из адресов ниже пример использования заливки Кетмара и реализацию заливки, о которой говорил MBo, и скажи, что тебя в них не устраивает?
http://www.sendspace.com/file/2zw5rf
http://storeandserve.com/download/383361/Filler.rar.html
(P.S: Карту можно рисовать или загружать из картинки, а также увеличивать или уменьшать)

Реализации заливок (размеры карты W x H с нулевого индекса):

procedure AreaFill(x, y: Integer; dstColor: Integer); var srcColor: Integer; procedure SimpleAreaFill(xa, ya: Integer); var lx, rx: Integer; begin // а вообще надо что-то делать? if (ya < 0) or (ya >= H) or (map[xa, ya] = dstColor) then exit; // найдём границы текущей линии lx := xa; while (lx >= 0) and (map[lx, ya] = srcColor) do Dec(lx); rx := xa+1; while (rx < W) and (map[rx, ya] = srcColor) do Inc(rx); // покрасим for xa := lx+1 to rx-1 do Map[xa, ya] := dstColor; // а теперь всё то же самое для строк выше и ниже for xa := lx+1 to rx-1 do begin SimpleAreaFill(xa, ya-1); SimpleAreaFill(xa, ya+1); end; end; begin if (x < 0) or (x > W) or (y < 0) or (y > H) then exit; srcColor := Map[x, y]; if srcColor = dstColor then exit; SimpleAreaFill(x, y); end; procedure AreaFill2(x, y: Integer; dstColor: Integer); var srcColor: TColor; procedure FillColor(xa, ya: Integer); begin If Map[xa, ya] = srcColor then begin Map[xa, ya] := dstColor; If xa-1 >= 0 then FillColor(xa-1, ya); If ya-1 >= 0 then FillColor(xa, ya-1); If xa+1 < W then FillColor(xa+1, ya); If ya+1 < H then FillColor(xa, ya+1); end; end; begin srcColor := Map[x,y]; If srcColor = dstColor then Exit; If (x < 0) or (x > W) or (y < 0) or (y > H) then Exit; FillColor(x, y); end;

← →
Ketmar © (2006-08-28 01:58) [46]

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

← →
RASkov (2006-08-28 02:46) [47]

> [44] Ketmar © (28.08.06 01:45)
> а "вытекания" и прочее... на самом деле так и должно быть.
> потому что внутри фигуры распространение идёт по 8-ми направлениям,
> а на границах -- только по 4-м -- ортам. думаю, если ты
> понял код, то большого труда исправления не потребуют. %-
> )

Подправил, подрихтовал.. То что надо. Про "вытекание".... Оно как раз так и лучше что из таких дыр [10] не вытекает :)))

> [45] Vovan#1 (28.08.06 01:54)

Спасибо. Посмотрел (бегло)... нечто похожее и я пытаюсь(лся) сделать. Посмотрю получше. А я и не говорил что меня неустраивает код Кетмара, про код MBo уже писал...

Со страхом убрал +1 из rx := x+1; вроде ничего страшного не произошло...
для чего прибовляем 1? Может следует вернуть?

← →
RASkov (2006-08-28 03:11) [48]

> [45] Vovan#1 (28.08.06 01:54)

А ведь второй вариант похож на тот который я привел в [3] т.е. с него я и начинал но запутался и в тупик...:)) И ввиду того что это я придумал, я его закомментировал в первую очередь, и отложил...во дурак.:) Надо больше себе доверять....

> [47] RASkov (28.08.06 02:46)
> для чего прибовляем 1?
а зачем лишний раз проверять ячейку, которая уже проверена в предыдущем цикле? страшного ничего, просто лишняя итерация.

> [48] RASkov (28.08.06 03:11)
надо было с ручкой и бумажкой на маленьком массиве проверить. %-)

← →
RASkov (2006-08-28 12:58) [50]

> [49] Ketmar © (28.08.06 04:03)
> а зачем лишний раз проверять ячейку, которая уже проверена
> в предыдущем цикле? страшного ничего, просто лишняя итерация.

Согласен.. но при
if (y < 0)or(y >= MAX_Y)or(map[y,x]=dstColor) then exit;
впринципе да, мы ее только проверяем второй раз (не красим). Хотя и это не к чему... нужно вернуть.

> > [48] RASkov (28.08.06 03:11)
> надо было с ручкой и бумажкой на маленьком массиве проверить.
> %-)

Пробовал.... и на бумаге. Начал чуть-чуть не так... и в тупик. А размер массива собственно роли не играет. Здесь нужно всего то восемь клеток обработать исходя от центральной и так для каждой. Тут я и пропал.
Спасибо.

Рекурсия Найти похожие ветки