recursiva - un algoritmo de relleno no recursivo de trabajo escrito en C?
funcion recursiva de la serie fibonacci (10)
He estado tratando de encontrar un algoritmo de inundación de trabajo. De los muchos algoritmos que he probado, solo el ''relleno de línea recursiva'' se comporta exactamente como debería con la advertencia principal de que ocasionalmente sopla la pila. :(
He probado muchas implementaciones no recursivas que he encontrado y todas han sido excepcionalmente temperamentales: dejan brechas en lugares extraños o inundan toda el área (cuando deberían estar encerradas).
¿Alguien tiene un código fuente de trabajo de relleno de inundación NO-recursivo escrito en C (o c ++ que no sea demasiado OOP y puedo desenredar con suficiente facilidad)?
¿No hay una prueba en alguna parte de que todas las funciones recursivas puedan implementarse como una función iterativa utilizando datos locales para imitar una pila? Probablemente podría usar std :: vector para crear un comportamiento similar al de una pila del algoritmo sin hacer saltar la pila, ya que usará la pila.
EDITAR: Noté que está usando C, así que en lugar de std :: vector, podría implementar un comportamiento similar a través de realloc ya que necesita agregar más elementos a su "pila" local de cualquier estructura de datos que utilice.
A continuación se encuentra mi método iterativo c ++ basado en BFS para el problema del relleno de inundación:
// M is the input matrix, with every entry(pixel) have a color
// represented with an integer value.
// (x, y) row and column of seed point respectively
// k: The new color to fill the seed and its adjacent pixels
void floodFill(vector<vector<int>> &M, int x, int y, int k) {
queue<pair<int, int>> nodeQ;
nodeQ.push({x, y});
int oldCol = M[x][y];
while(!nodeQ.empty()) {
pair<int, int> currNode = nodeQ.front();
nodeQ.pop();
if(M[currNode.first][currNode.second] == oldCol) {
M[currNode.first][currNode.second] = k;
if(currNode.first > 0) nodeQ.push({currNode.first-1, currNode.second});
if(currNode.first < (M.size()-1)) nodeQ.push({currNode.first+1, currNode.second});
if(currNode.second > 0) nodeQ.push({currNode.first, currNode.second-1});
if(currNode.second < (M[0].size()-1)) nodeQ.push({currNode.first, currNode.second+1});
}
}
}
Aquí hay un código de C ++ que hace lo que quieres. Utiliza una cola, y es más eficiente en las inserciones en la cola.
connectedRegion(const Point& source, RegionType& region, const Color target)
{
Color src_color = color_of(source, region);
if (region.count(source) == 0 || src_color == target)
return;
std::queue<Point> analyze_queue;
analyze_queue.push(source);
while (!analyze_queue.empty())
{
if (color_of(analyze_queue.front()) != src_color)
{
analyze_queue.pop();
continue;
}
Point leftmost_pt = analyze_queue.front();
leftmost_pt.col -= 1;
analyze_queue.pop();
Point rightmost_pt = leftmost_pt;
rightmost_pt.col += 2;
while (color_of(leftmost_pt, region) == src_color)
--leftmost_pt.col;
while (color_of(rightmost_pt, region) == src_color)
++rightmost_pt.col;
bool check_above = true;
bool check_below = true;
Point pt = leftmost_pt;
++pt.col;
for (; pt.col < rightmost_pt.col; ++pt.col)
{
set_color(pt, region, target);
Point pt_above = pt;
--pt_above.row;
if (check_above)
{
if (color_of(pt_above, region) == src_color)
{
analyze_queue.push(pt_above);
check_above = false;
}
}
else // !check_above
{
check_above = (color_of(pt_above, region) != src_color);
}
Point pt_below = pt;
++pt_below.row;
if (check_below)
{
if (color_of(pt_below, region) == src_color)
{
analyze_queue.push(pt_below);
check_below = false;
}
}
else // !check_below
{
check_below = (color_of(pt_below, region) != src_color);
}
} // for
} // while queue not empty
return connected;
}
No sé si mi respuesta es perfectamente relevante para la pregunta que ha formulado, pero a continuación propongo mi versión C del algoritmo Flood-Fill, que no utiliza llamadas recursivas.
1-11-2017: NUEVA VERSIÓN; Probado exitosamente con dos trampas.
Utiliza solo una cola de las compensaciones de los nuevos puntos, funciona en la ventana: WinnOffs- (WinDimX, WinDimY) del búfer doble: * VBuffer (copia de la pantalla o imagen) y, opcionalmente, escribe una máscara del resultado del relleno de inundación (* ExtraVBuff). ExtraVBuff debe completarse con 0 antes de la llamada (si no necesita una máscara, puede configurar ExtraVBuff = NULL); Si lo usa después de la llamada, puede realizar un relleno de degradado u otros efectos de pintura. NewFloodFill funciona con 32 bits por píxel y es una función C. Reinventé este algoritmo en 1991 (escribí el suyo en Pascal), pero ahora funciona en C con 32 bits por píxel; Además, no utiliza ninguna función llamada, solo hace una división después de cada "pop" de la cola, y nunca desborda la cola, que, si tiene el tamaño correcto (aproximadamente 1/4 de los píxeles de la imagen), permite Siempre para rellenar correctamente cualquier área; Muestro antes de la función c (FFILL.C), después del programa de prueba (TEST.C):
#define IMAGE_WIDTH 1024
#define IMAGE_HEIGHT 768
#define IMAGE_SIZE IMAGE_WIDTH*IMAGE_HEIGHT
#define QUEUE_MAX IMAGE_SIZE/4
typedef int T_Queue[QUEUE_MAX];
typedef int T_Image[IMAGE_SIZE];
void NewFloodFill(int X,
int Y,
int Color,
int BuffDimX,
int WinOffS,
int WinDimX,
int WinDimY,
T_Image VBuffer,
T_Image ExtraVBuff,
T_Queue MyQueue)
/* Replaces all pixels adjacent to the first pixel and equal to this; */
/* if ExtraVBuff == NULL writes to *VBuffer (eg BUFFER of 786432 Pixel),*/
/* otherwise prepare a mask by writing on *ExtraVBuff (such BUFFER must */
/* always have the same size as *VBuffer (it must be initialized to 0)).*/
/* X,Y: Point coordinates'' of origin of the flood-fill. */
/* WinOffS: Writing start offset on *VBuffer and *ExtraVBuff. */
/* BuffDimX: Width, in number of Pixel (int), of each buffer. */
/* WinDimX: Width, in number of Pixel (int), of the window. */
/* Color: New color that replace all_Pixel == origin''s_point. */
/* WinDimY: Height, in number of Pixel (int), of the window. */
/* VBuffer: Pointer to the primary buffer. */
/* ExtraVBuff: Pointer to the mask buffer (can be = NULL). */
/* MyQueue: Pointer to the queue, containing the new-points'' offsets*/
{
int VBuffCurrOffs=WinOffS+X+Y*BuffDimX;
int PixelIn=VBuffer[VBuffCurrOffs];
int QueuePnt=0;
int *TempAddr=((ExtraVBuff) ? ExtraVBuff : VBuffer);
int TempOffs1;
int TempX1;
int TempX2;
char FLAG;
if (0<=X && X<WinDimX && 0<=Y && Y<WinDimY) do
{
/* Fill to left the current line */
TempX2=X;
while (X>=0 && PixelIn==VBuffer[VBuffCurrOffs])
{
TempAddr[VBuffCurrOffs--]=Color;
--X;
}
TempOffs1=VBuffCurrOffs+1;
TempX1=X+1;
/* Fill to right the current line */
VBuffCurrOffs+=TempX2-X;
X=TempX2;
while (X+1<WinDimX && PixelIn==VBuffer[VBuffCurrOffs+1])
{
++X;
TempAddr[++VBuffCurrOffs]=Color;
}
TempX2=X;
/* Backward scan of the previous line; puts new points offset in Queue[] */
if (Y>0)
{
FLAG=1;
VBuffCurrOffs-=BuffDimX;
while (X-->=TempX1)
{
if (PixelIn!=VBuffer[VBuffCurrOffs] ||
ExtraVBuff && Color==ExtraVBuff[VBuffCurrOffs])
FLAG=1;
else
if (FLAG)
{
FLAG=0;
if (QueuePnt<QUEUE_MAX)
MyQueue[QueuePnt++]=VBuffCurrOffs;
}
--VBuffCurrOffs;
}
}
/* Forward scan of the next line; puts new points offset in Queue[] */
if (Y<WinDimY-1)
{
FLAG=1;
VBuffCurrOffs=TempOffs1+BuffDimX;
X=TempX1;
while (X++<=TempX2)
{
if (PixelIn!=VBuffer[VBuffCurrOffs] ||
ExtraVBuff && Color==ExtraVBuff[VBuffCurrOffs])
FLAG=1;
else
if (FLAG)
{
FLAG=0;
if (QueuePnt<QUEUE_MAX)
MyQueue[QueuePnt++]=VBuffCurrOffs;
}
++VBuffCurrOffs;
}
}
/* Gets a new point offset from Queue[] */
if (--QueuePnt>=0)
{
VBuffCurrOffs=MyQueue[QueuePnt];
TempOffs1=VBuffCurrOffs-WinOffS;
X=TempOffs1%BuffDimX;
Y=TempOffs1/BuffDimX;
}
/* Repeat the main cycle until the Queue[] is not empty */
} while (QueuePnt>=0);
}
Aquí está el programa de prueba:
#include <stdio.h>
#include <malloc.h>
#include "ffill.c"
#define RED_COL 0xFFFF0000
#define WIN_LEFT 52
#define WIN_TOP 48
#define WIN_WIDTH 920
#define WIN_HEIGHT 672
#define START_LEFT 0
#define START_TOP 671
#define BMP_HEADER_SIZE 54
typedef char T_Image_Header[BMP_HEADER_SIZE];
void main(void)
{
T_Image_Header bmpheader;
T_Image *image;
T_Image *mask;
T_Queue *MyQueue;
FILE *stream;
char *filename1="ffill1.bmp";
char *filename2="ffill2.bmp";
char *filename3="ffill3.bmp";
int bwritten;
int bread;
image=malloc(sizeof(*image));
mask=malloc(sizeof(*mask));
MyQueue=malloc(sizeof(*MyQueue));
stream=fopen(filename1,"rb");
bread=fread(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bread=fread((char *)image, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
memset(mask,0,IMAGE_SIZE<<2);
NewFloodFill(START_LEFT,
START_TOP,
RED_COL,
IMAGE_WIDTH,
IMAGE_WIDTH*WIN_TOP+WIN_LEFT,
WIN_WIDTH,
WIN_HEIGHT,
*image,
NULL,
*MyQueue);
stream=fopen(filename2,"wb+");
bwritten=fwrite(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bwritten=fwrite((char *)image, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
stream=fopen(filename3,"wb+");
bwritten=fwrite(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bwritten=fwrite((char *)mask, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
free(MyQueue);
free(mask);
free(image);
}
He utilizado, para la entrada del programa de prueba que se muestra, la siguiente imagen .BMP sin comprimir de Windows (ffill1.bmp):
Rellenado, según el programa de prueba que se muestra a continuación (ffill2.bmp):
Usando "máscara" en lugar de NULL, el mapa de bits de salida es (ffill3.bmp):
Notamos que nuestra implementación de inundación en volúmenes 3D consumía mucha memoria; así que modificamos el código de las siguientes maneras (hubo una gran mejora):
Cree una esfera de radio = 10 voxs alrededor del punto de inicio y marque todos los voxels dentro de ese radio como "para ser visitado"
Si el voxel actual> umbral, inserte 1.
Diríjase a los vecinos [+1, -1, 0] (también verifique que uno no vuelva a visitar ningún vóxel), si el neighbour.getVoxVal = 0 (el valor de inicialización para el volumen objetivo), entonces cae en el límite de La esfera, inserta las coordenadas en una pila diferente. (este sería el punto de partida para nuestra próxima esfera)
radio = radio + 10 (voxels)
Así que, en un momento, nuestra inundación está trabajando en una esfera concéntrica y llenando las cosas, que es una parte de todo el volumen, y como dije, esto ha reducido el consumo de memoria de manera drástica, pero todavía estoy buscando una implementación / idea. eso estaría mejor.
Puede convertir cualquier algoritmo recursivo a iterativo creando una pila o cola explícita y cargando el trabajo en él o quitándolo.
Todo lo que necesita es elegir una representación agradable y compacta del trabajo a realizar. Peor caso: cree una struct que struct los argumentos que normalmente pasaría a la versión recursiva ...
Puede convertir rápidamente un relleno de inundación recursivo en un pseudo-recursivo de alto rendimiento ... No edite las líneas, solo agregue nuevas líneas: coloque la función recursiva en un bucle XY para agregar estructura. registre los vecinos encontrados en una "matriz de vecinos encontrados" en lugar de la memoria, por lo que comenzará a empaquetar el árbol de estilo 4-16-64 de la recursión en una matriz XY. el uso de memoria va de 1 gygabyte a 2 megabytes. También use una matriz 2D llamada "matriz de vecinos rellenos" ... aborte la función para los píxeles marcados como rellenados en la "matriz de vecinos vecinos", esto utiliza 2 instrucciones por cada duplicado, 20 instrucciones por cada operación de relleno, y se llena de manera iterativa Hacia la izquierda y hacia arriba como dominó, increíblemente rápido.
1024x1024 usa aproximadamente 1 millón * 20 instrucciones, que son 0.1 segundos para un solo núcleo.
Logro 9 millones de píxeles llenos por segundo en un i7 de esta manera, tengo un video como prueba y una página de blog con explicaciones de código y teoría:
www.youtube.com/watch?v=4hQ1wA4Sl4c
Y aquí hay una página en la que intenté explicar cómo funciona. http://unity3dmc.blogspot.com/2017/02/ultimate-3d-floodfill-scanline.html?m=1
Y el código.
Las recursiones serían las más rápidas si pudieran mantenerse organizadas.
Si recurre a través de una cuadrícula de datos (imagen), también puede almacenar el procesamiento de las recursiones en formato de cuadrícula, ya que los pasos procesados representan píxeles de la cuadrícula, en lugar de explotar los resultados en un formato de árbol.
Simplemente implemente una pila de pares int con una matriz de algún tamaño fijo (por ejemplo, el tamaño de la imagen en píxeles o la raíz cuadrada de eso, por ejemplo) para la pila y rastree la parte superior con un int.
Aquí hay un código C # que implementa el llenado por inundación de manera no recursiva:
private static void Floodfill(byte[,] vals, Point q, byte SEED_COLOR, byte COLOR)
{
int h = vals.GetLength(0);
int w = vals.GetLength(1);
if (q.Y < 0 || q.Y > h - 1 || q.X < 0 || q.X > w - 1)
return;
Stack<Point> stack = new Stack<Point>();
stack.Push(q);
while (stack.Count > 0)
{
Point p = stack.Pop();
int x = p.X;
int y = p.Y;
if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
continue;
byte val = vals[y, x];
if (val == SEED_COLOR)
{
vals[y, x] = COLOR;
stack.Push(new Point(x + 1, y));
stack.Push(new Point(x - 1, y));
stack.Push(new Point(x, y + 1));
stack.Push(new Point(x, y - 1));
}
}
}
Tengo un relleno de inundación no recursivo, pero no lo publicaré porque es la solución para una tarea. Pero aquí hay una pista: la búsqueda en profundidad, que es el algoritmo natural, usa mucho más espacio auxiliar que una búsqueda en primer lugar. Esto es lo que escribí en ese momento (adecuadamente expurgado):
No me atrevo a intentar la búsqueda en profundidad por simple recursión; la profundidad de la recursión está limitada solo por REDACTADO, y mis experimentos muestran que un PROBLEMA REDACTADO podría requerir una profundidad de pila de más de un millón. Así que puse la pila en una estructura de datos auxiliar. El uso de una pila explícita en realidad también facilita la búsqueda en la amplitud, y resulta que la búsqueda en la primera amplitud puede usar cuarenta veces menos espacio que la búsqueda en profundidad.
Para mi estructura de datos utilicé el Seq_T de las interfaces e implementaciones C de Dave Hanson; cambiar de profundidad primero a amplitud primero requiere cambiar solo una llamada de función.
Una búsqueda rápida en Google muestra el artículo de Wikipedia sobre Flood Fill, que incluye implementaciones de pseudocódigo que no son recursivas. A continuación se muestra un código que podría ayudarlo a comenzar, una implementación básica de la cola en C:
typedef struct queue_ { struct queue_ *next; } queue_t;
typedef struct ffnode_ { queue_t node; int x, y; } ffnode_t;
/* returns the new head of the queue after adding node to the queue */
queue_t* enqueue(queue_t *queue, queue_t *node) {
if (node) {
node->next = queue;
return node;
}
return NULL;
}
/* returns the head of the queue and modifies queue to be the new head */
queue_t* dequeue(queue_t **queue) {
if (queue) {
queue_t *node = (*queue);
(*queue) = node->next;
node->next = NULL;
return node;
}
return NULL;
}
ffnode_t* new_ffnode(int x, int y) {
ffnode_t *node = (ffnode_t*)malloc(sizeof(ffnode_t));
node->x = x; node->y = y;
node->node.next = NULL;
return node;
}
void flood_fill(image_t *image, int startx, int starty,
color_t target, color_t replacement) {
queue_t *head = NULL;
ffnode_t *node = NULL;
if (!is_color(image, startx, starty, target)) return;
node = new_ffnode(startx, starty);
for ( ; node != NULL; node = (ffnode_t*)dequeue(&head)) {
if (is_color(image, node->x, node->y, target)) {
ffnode_t *west = node, *east = node;
recolor(image, node->x, node->y, replacement);
/* 1. move w to the west until the color of the node to the west
no longer matches target */
...
}
}
}