рабочий нерекурсивный floodfill алгоритм записан в C?

Вы можете преобразовать любой рекурсивный алгоритм в итеративный, создав явный стек или очередь и загрузив в него работу / сняв ее.

Все, что вам нужно, это выбрать хороший, компактное представление о предстоящих работах. Худший случай: создайте struct , содержащую аргументы, которые вы обычно передаете рекурсивной версии ...

Быстрый поиск в Google приводит к статье в Википедии о Flood Fill , которая включает реализации псевдокода, которые не являются рекурсивными. Ниже приведен код, который может помочь вам начать работу, базовая реализация очереди на 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 */
            ...
        }
    }
}

Нет ли где-нибудь доказательства того, что все рекурсивные функции могут быть реализованы как итеративная функция с использованием локальных данных для имитации стека? Вы, вероятно, могли бы использовать std :: vector для создания поведения алгоритма, подобного стеку, без взрыва стека, поскольку он будет использовать кучу.

РЕДАКТИРОВАТЬ: Я заметил, что вы используете C, поэтому вместо std :: vector вы могли просто реализуйте аналогичное поведение с помощью перераспределения, поскольку вам нужно добавить больше элементов в ваш локальный «стек» любой структуры данных, которую вы бы использовали.

Просто реализуйте стек пар int с массивом некоторого фиксированного размера (например, размер изображения в пикселях или квадратный корень из этого) для стека и отслеживайте вершину с int.

Вот некоторый код C #, который реализует floodfill нерекурсивно:

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));
        }
    }
}

У меня есть нерекурсивная заливка, но я не буду публиковать ее, потому что это решение домашнего задания. Но вот подсказка: поиск в глубину, который является естественным алгоритмом, использует намного больше вспомогательного пространства, чем поиск в ширину. Вот что я написал в то время (подходяще вычеркнутый):

Я не смею пробовать поиск в глубину с помощью простой рекурсии; глубина рекурсии ограничена только УДАЛЕНО, и мои эксперименты показывают, что ПРОБЛЕМА УДАЛЕНО, тем не менее, может потребовать глубины стека более миллиона. Поэтому я помещаю стек во вспомогательную структуру данных. Использование явного стека на самом деле также упрощает попытку поиска в ширину, и оказывается, что поиск в ширину может использовать в сорок раз меньше места, чем поиск в глубину.

Для своей структуры данных я использовал Seq_T из Интерфейсы и реализации C Дэйва Хэнсона ; для перехода с «в глубину» на «сначала в ширину» требуется изменить только один вызов функции.

Мы заметили, что наша реализация floodfill на трехмерных томах потребляет много памяти; поэтому мы изменили код следующими способами (произошло значительное улучшение):

1. Создайте сферу радиуса = 10 вокс вокруг начальной точки и пометьте все воксели в пределах этого радиуса как «для посещения»

2. Если текущий воксель> порога, вставьте 1.

3. Перейти к соседям [+1, -1, 0] (также убедитесь, что ни один воксель не посещает повторно), если neighbour.getVoxVal = 0 (значение инициализации для целевого объема), затем он попадает на границу сферы, вставьте координаты в другую стопку. (это будет отправной точкой для нашей следующей сферы)

4. radius = radius + 10 (voxels)

Таким образом, в какой-то момент наша заливка работает над концентрической сферой и заполняет все, что является частью весь том, и, как я уже сказал, это резко снизило потребление памяти, но я все еще ищу реализацию / идею, которая была бы лучше.