| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Рекурсия
RASkov © (2006-08-23 03:50:00)Подскажите как осуществляется заливка... Ну например есть Битмап на его канве нарисовали круг тыкнули в области круга мышой и круг залился специально определенным цветом. Это только пример. Мне собственно нужно нечто похожее. Есть двумерный массив (т.е. теже самые пикселы канвы Битмапа) если этот массив спроецировать на Битмап то там тоже может быть замкнутая фигура (из чисел) и вот если указать координаты в области такой фигуры то нужно всю эту область заполнить определенным значеним. Вот дополнительное инфо
var Map: array [0..100] of array [0..100] of Integer;
procedure Fill(const X, Y, NFrom, NTo: Integer);
begin
?????????
end;
вызов Fill(35, 45, 3, 5);
3 - это значени в Map[35][45]
5 - на это нужно заменить все 3 исходя от данной координаты(35,45) и по сторонам пока не встретится либо граница либо отличное от 3
Процедуру и вызов написал только для того что бы было лучше понять. Может и не правильно (скорее всего) описал ее, т.к. она наверняка должна быть рекурсивной или в ней (в процедуре Fill) сделать рекурсивную подпрограмму. Не понимаю как вообще оформить рекурсию.
RASkov (2006-08-28 12:58:00) [1]> [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)
> надо было с ручкой и бумажкой на маленьком массиве проверить.
> %-)
Пробовал.... и на бумаге. Начал чуть-чуть не так... и в тупик. А размер массива собственно роли не играет. Здесь нужно всего то восемь клеток обработать исходя от центральной и так для каждой. Тут я и пропал.
Спасибо.
Ketmar (2006-08-28 04:03:00) [2]> [47] RASkov (28.08.06 02:46)
> для чего прибовляем 1?
а зачем лишний раз проверять ячейку, которая уже проверена в предыдущем цикле? страшного ничего, просто лишняя итерация.
> [48] RASkov (28.08.06 03:11)
надо было с ручкой и бумажкой на маленьком массиве проверить. %-)
RASkov (2006-08-28 03:11:00) [3]> [45] Vovan#1 (28.08.06 01:54)
А ведь второй вариант похож на тот который я привел в [3] т.е. с него я и начинал но запутался и в тупик...:)) И ввиду того что это я придумал, я его закомментировал в первую очередь, и отложил...во дурак.:) Надо больше себе доверять....
RASkov (2006-08-28 02:46:00) [4]> [44] Ketmar © (28.08.06 01:45)
> а "вытекания" и прочее... на самом деле так и должно быть.
> потому что внутри фигуры распространение идёт по 8-ми направлениям,
> а на границах -- только по 4-м -- ортам. думаю, если ты
> понял код, то большого труда исправления не потребуют. %-
> )
Подправил, подрихтовал.. То что надо. Про "вытекание".... Оно как раз так и лучше что из таких дыр [10] не вытекает :)))
> [45] Vovan#1 (28.08.06 01:54)
Спасибо. Посмотрел (бегло)... нечто похожее и я пытаюсь(лся) сделать. Посмотрю получше. А я и не говорил что меня неустраивает код Кетмара, про код MBo уже писал...
Со страхом убрал +1 из rx := x+1; вроде ничего страшного не произошло...
для чего прибовляем 1? Может следует вернуть?
Ketmar (2006-08-28 01:58:00) [5]собственно, второй вариант -- это почти то же самое, что дал я. только у меня чуть-чуть быстрее. ненамного. %-) и несколько менее корректно обрабатываются границы.
Vovan#1 (2006-08-28 01:54:00) [6]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:45:00) [7]> [43] RASkov (28.08.06 01:34)
ну да. ступил. %-) назову это тестом на сообразительность. %-)
а код я дал по причинам чисто ностальгическим. вспомнилось, почему-то, как сам в своё время долго думал над почти такой же задачей. %-)
а "вытекания" и прочее... на самом деле так и должно быть. потому что внутри фигуры распространение идёт по 8-ми направлениям, а на границах -- только по 4-м -- ортам. думаю, если ты понял код, то большого труда исправления не потребуют. %-)
RASkov (2006-08-28 01:34:00) [8]> [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:27:00) [9]> [41] RASkov (28.08.06 00:36)
если я правильно понял задачу -- зальёт. форма фигуры не важна. %-)
RASkov (2006-08-28 00:36:00) [10]> [40] Ketmar © (28.08.06 00:12)
Спасибо большое. Сейчас будем в очередной раз "попробывать"... Интересно твой зальет фигуру отличную от прямоугольника т.е. с впадинами и иже сними... И все же областя могут быть большими... скорость собственно не важно. Лишь бы стека хватило:) Согласен, код меньше, без указателей и без доп. массивов, поэтому мож чего и своего на этом примере сворганю....
Вот пишу ответ и читаю [39] Ketmar © (28.08.06 00:10)....чето сомнения какието не хорошие... да ладно сейчас проверю. Спасибо. Если что тема не закрыта.
Ketmar (2006-08-28 00:12:00) [11]конечно, алгоритм далёк от шибко оптимального, и на больших областях всё-же сожрёт весь стек. да и скоростью не блещет. зато мало кода и ясно. %-)
Ketmar (2006-08-28 00:10:00) [12]
procedure AreaFill (x, y: Integer; dstColor: Integer);
var
srcColor: Integer;
procedure SimpleAreaFill (x, y: Integer);
var
lx, rx: Integer;
begin
// а вообще надо что-то делать?
if (y < 0) or (y >= MAX_Y) or
(map[y, x] = srcColor) or (map[y, x] = dstColor) then exit;
// найдём границы текущей линии
lx := x; while (lx >= 0) and (map[y, lx] = srcColor) do Dec(lx);
rx := x+1; while (rx < MAX_X) and (map[y, rx] = srcColor) do Inc(rx);
// покрасим
for x := lx+1 to rx-1 do map[y, x] := dstColor;
// а теперь всё то же самое для строк выше и ниже
for x := lx+1 to rx-1 do
begin
SimpleAreaFill(x, y-1);
SimpleAreaFill(x, y+1);
end;
end;
begin
if (x < 0) or (x >= MAX_X) or (y < 0) or (y >= MAX_Y) then exit;
srcColor := map[y, x];
if srcColor = dstColor then exit;
SimpleAreaFill(x, y);
end;
думаю, догадаешься, что MAX_X и MAX_Y -- это размеры. что там у тебя в индексах первое -- x или y -- тоже реши сам.
RASkov (2006-08-28 00:01:00) [13]> [36] Ketmar © (28.08.06 00:00)
Я в шоке........
RASkov (2006-08-28 00:00:00) [14]> [33] Ketmar © (27.08.06 23:50)
SetLength(Map, Cols, Rows);
Границы:
значение отличное от Map[3,3] включая значение которым нужно залить, Физические: 0, Cols, Rows.
Ketmar (2006-08-28 00:00:00) [15]> [35] RASkov (27.08.06 23:52)
ты будешь смеяться, но я сейчас даже код дам. %-)
RASkov (2006-08-27 23:52:00) [16]> [33] Ketmar © (27.08.06 23:50)
Не ожидал:))
попробуем проще. "граница" -- это всё, что не является значением Map[3, 3]. так?
Да, так. И еще конечно же реальные границы т.е. границы массива.
RASkov (2006-08-27 23:51:00) [17]В данном примере залили зеленый красным, т.е. поменяли значения в массиве имеющие значение 3 с учетом границ грубо это 2 (синего цвета рамка), 4 и 0 (красный и черный) - имеющиеся в "рамке" из синих.... ух сам путаюсь и Вас запутываю..
Ketmar © знаю что ты не напишешь (тебе лень) и земля у тебя не круглая.... всеравно спасибо тебе. %) Надеюсь понятна логика стала или от лени нет? Всетаки читать мою писанину - это терпенья скоко надо.
Ketmar (2006-08-27 23:50:00) [18]> [31] RASkov (27.08.06 23:38)
попробуем проще. "граница" -- это всё, что не является значением Map[3, 3]. так?
RASkov (2006-08-27 23:42:00) [19]Ну да случилось у номеров столбцов пробел уплыл вначале...
и жирные нимного стали толще :)))
Уж... понятно чтоли?
Ну помогите решить долбаную задачку (проблему для меня).
[29]?????????
RASkov (2006-08-27 23:38:00) [20]> [30] Ketmar © (27.08.06 21:51)
А Вы внимательно прочитали [9]? 3 и 5 взял от фонаря...так к примеру...
Логика в том, что если в момент входа в процедуру, в ячейки с которой надо начать заливку определенным значением, находится отличное значение от того чем нужно залить, то залить все ячейки имеющие значения равные тому которое было при входе в процедуру заливки в ячейки с учетом границ. Вот так может станет ясней... уже незнаю как объяснить:
ч - черный значение например 1
с - синий значение например 2
з - зеленый значение например 3
к - красный значение например 4
цифры номера столбцов и строк т.е. в данном случае SetLength(Map, 10, 7);
0123456789
0чччччччччч
1ччччзззччч
2 сссссссссс
3 сзззззззз с
4 сккккк ччч с
5 сссссссссс
6ккккззссчч
выбрали ячейку Map[3,3] (находится в "фигуре" данном случае прямоугольник из 2 (синий) это границы и за них не выходим так же границей является и значение 0 (черный) внутри фигуры) в ней значение 3 (зеленый) нужно заменить на 4 (красный)
Вызываем Fill(3,3,4);
в процедуре проверяем значение Map[3,3] равно 3 и не равно 4
значит нужно заполнить значениями 4 массив Map в диапазоне где находится значение 3 с учетом границ получаем вот такое:
0123456789
0чччччччччч
1чччч зззччч //здесь остаются не тронутыми
2 сссссссссс
3 скккккккк с
4 сккккк ччч с
5 сссссссссс
6кккк ззссчч // здесь тоже не трогаем
ух... если с форматированием косяк будет... старался чтоб не было если что подправлю.
| |
Страницы: 