用 C 语言填充整数数组的简单泛洪填充算法

问：

在尝试了在 Fortran 90 中实现它之后，我转向了 C。我不确定这是我的实现还是实际的，但它没有按预期工作，并且倾向于填充整个数组，无论我以何种方式放置任何边框。我的目标是创建一个扩展。queueflood fill algorithmPython

下面是代码，它基于 的实现这个算法。
最初的目的是将 实现为动态数组并从 rosettacode 借用代码，但我也无法使其工作，所以我试图让它更像 的实现，尽管进行了细微的调整。scikit-imagequeuescikit-imageQueueWithHistory

queue.h

#ifndef QUEUE_H
#define QUEUE_H

typedef size_t DATA; /* type of data to store in queue */
typedef struct {
    DATA *buf;
    size_t head;
    size_t tail;
    size_t alloc;
} queue_t, *queue;

extern queue init_queue();
extern void free_queue(queue q);
extern void push_queue(queue q, DATA *n);
extern unsigned char pop_queue(queue q, DATA *n);

#endif /* QUEUE_H */

queue.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"


#define QUEUE_INIT_SIZE 64
#define QUEUE_THRESHOLD 512


static void _handle_memory_allocation_failure(const char *message, queue q) {
    fprintf(stderr, "Error: Failed to (re)allocate memory for %s\n", message);
    free_queue(q);  // Ensure proper cleanup
    exit(EXIT_FAILURE);
}

queue init_queue() {
    queue q = malloc(sizeof(queue_t));
    if (!q) {
        _handle_memory_allocation_failure("queue structure", NULL);
    }
    q->buf = malloc(sizeof(DATA) * (q->alloc = QUEUE_INIT_SIZE));
    if (!q->buf) {
        _handle_memory_allocation_failure("queue buffer", q);
    }
    q->head = q->tail = 0;
    return q;
}

void free_queue(queue q) {
    if (!q) return;
    free(q->buf);
    free(q);
}

static void _grow_queue(queue q) {
    q->alloc *= 2;
    DATA *new_buf = realloc(q->buf, sizeof(DATA) * q->alloc);
    if (!new_buf) {
        _handle_memory_allocation_failure("growing queue buffer", q);
    }
    q->buf = new_buf;
}

void push_queue(queue q, DATA *n) {
    if (q->alloc <= q->head) {
        _grow_queue(q);
    }
    q->buf[q->head++] = *n;
}

unsigned char pop_queue(queue q, DATA *n) {
    if (q->tail < q->head) {
        *n = q->buf[q->tail++];
        return 1;
    }
    return 0;
}

floodfill.h

#ifndef FLOODFILL_H
#define FLOODFILL_H

// Function declarations
int flood_fill(int* image, int* offsets, size_t n_offsets,
               size_t start_index, int new_value, size_t image_size);

#endif /* FLOODFILL_H */

floodfill.c

#include <stdlib.h>
#include <stdio.h>
#include "floodfill.h"
#include "queue.h"


// C implementation of floodfill algorithm

int flood_fill(int* image, int* offsets, size_t n_offsets,
               size_t start_index, int new_value, size_t image_size) {
    
    size_t current_index, neighbor_index;

    // Get the seed value (image value at start location)
    int seed_value = image[start_index];
    // Short circuit to avoid infinite loop
    if (seed_value == new_value) {
        return 0;
    }
    image[start_index] = new_value;
    // Initialize the queue and push start position
    queue q = init_queue();
    push_queue(q, &start_index);
    
    // Break loop if all queued positions were evaluated
    while (pop_queue(q, &current_index)) {
        // Look at all neighbors
        for (int i = 0; i < n_offsets; ++i) {
            neighbor_index = current_index + offsets[i];
            if (neighbor_index < image_size) {
                if (image[neighbor_index] == seed_value) {
                    // Process neighbor and push to queue
                    image[neighbor_index] = new_value;
                    push_queue(q, &neighbor_index);
                }
            }
        }
    }
    // Ensure memory is released
    free_queue(q);
    return 0;
}

上面的 C 代码封装在一个 Python 模块中，下面是调用 C 代码的 main 函数。它在模块 API 中调用。flood_fill

#define RAVEL_INDEX(tuple, h) ( \
    (int)PyLong_AsLong(PyTuple_GetItem(tuple, 0)) + \
    h * (int)PyLong_AsLong(PyTuple_GetItem(tuple, 1)) \
)
#define N_OFFSETS 8

static PyObject *algorithms_flood_fill(PyObject *self, PyObject *args) {
    PyObject *image_obj;
    PyObject *start_obj;
    int seed_value;
    if (!PyArg_ParseTuple(args, "O!O!i", &PyArray_Type, &image_obj,
                                         &PyTuple_Type, &start_obj,
                                         &seed_value)) {
        PyErr_SetString(PyExc_TypeError, "Error parsing input");
        return NULL;
    }
    PyArrayObject *image_array;
    image_array = (PyArrayObject*)PyArray_FROM_OTF(image_obj,
                                                   NPY_INT,
                                                   NPY_ARRAY_IN_FARRAY);
    if (image_array == NULL) {
        // Py_XDECREF(image_array);
        PyErr_SetString(PyExc_TypeError, "Couldn't parse the input array");
        return NULL;
    }
    int h = (int)PyArray_DIM(image_array, 0);
    int w = (int)PyArray_DIM(image_array, 1);
    intptr_t start_index = (intptr_t)RAVEL_INDEX(start_obj, h);
    // it should be safe to use PyArray_DATA as we ensured aligned contiguous Fortran array
    int *image = (int *)PyArray_DATA(image_array);
    size_t image_size = h * w;
    int offsets[N_OFFSETS] = {-(h+1), -h, -(h-1), -1, +1, h-1, h, h+1};
    flood_fill(image, offsets, N_OFFSETS, start_index, seed_value, image_size);
    Py_DECREF(image_array);
    Py_RETURN_NONE;
}

如果我给它一个初始化为 0 的 9x9 整数数组，中间有一行 1（行索引 4）、、，数组中的所有 0 都会被 3 替换，这不是预期的行为。int offsets[] = {-10, -9, -8, -1, 1, 8, 9, 10}size_t n_offsets = 8size_t start_index = 0int new_value = 3size_t image_size = 81

import numpy as np
from mymodule import flood_fill

a = np.zeros((9, 9), order='F', dtype=np.int32)
a[4, :] = 1

flood_fill(a, (0, 0), 3)

# output :
# array([[3, 3, 3, 3, 3, 3, 3, 3, 3],
#        [3, 3, 3, 3, 3, 3, 3, 3, 3],
#        [3, 3, 3, 3, 3, 3, 3, 3, 3],
#        [3, 3, 3, 3, 3, 3, 3, 3, 3],
#        [1, 1, 1, 1, 1, 1, 1, 1, 1],
#        [3, 3, 3, 3, 3, 3, 3, 3, 3],
#        [3, 3, 3, 3, 3, 3, 3, 3, 3],
#        [3, 3, 3, 3, 3, 3, 3, 3, 3],
#        [3, 3, 3, 3, 3, 3, 3, 3, 3]])

实现或逻辑本身是否有问题，或者 Python 包装器调用它的方式是否有问题可能导致此问题？queueflood fill algorithm