如何用javascript填充画布中的所有空白区域？ （递归函数）

Question

我尝试创建一个递归函数来填充画布的所有空白空间，直到边缘或已经填充了其他颜色。

function createFillingPoint() {
  let x = points[0][0],
    y = points[0][1];
  var pattern = ctx.getImageData(x, y, 1, 1).data;
  var colorToChange = rgbToHex(pattern);
  ctx.fillRect(x, y, 1, 1);
  colorFillRec(x + 1, y, width.value, height.value, colorToChange);
  colorFillRec(x - 1, y, width.value, height.value, colorToChange);
  colorFillRec(x, y + 1, width.value, height.value, colorToChange);
  colorFillRec(x, y - 1, width.value, height.value, colorToChange);
}

基本上，该函数创建第一个点并给出该函数必须更改的原始颜色。

function colorFillRec(x, y, w, h, colorToChange) {
  if (
    x > w ||
    x < 0 ||
    y > h ||
    y < 0 ||
    rgbToHex(ctx.getImageData(x, y, 1, 1).data) != colorToChange
  )
    return;
  ctx.fillRect(x, y, 1, 1);
  colorFillRec(x + 1, y, w, h, colorToChange);
  colorFillRec(x - 1, y, w, h, colorToChange);
  colorFillRec(x, y + 1, w, h, colorToChange);
  colorFillRec(x, y - 1, w, h, colorToChange);
}

这个函数是递归函数。这两个函数都会检查像素的颜色，如果它与原始颜色不同，则函数停止。

我尝试运行该函数，但收到“超出最大调用堆栈大小”错误... 我试图找到一种新的方法来获得正确的结果（使用另一个递归或非递归函数），但我做不到。

Answer 1

您可以使用显式堆栈而不是调用堆栈。另外，对于整个画布区域只调用一次

getImageData

，然后操作图像数据，最后调用

putImageData

来更新画布，会更高效。

这是一个演示：

function setup(ctx) { // Make some drawing to use for this demo
    function rect(x, y, w, h, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.rect(x, y, w, h);
        ctx.fill();
    }

    function circle(x, y, r, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.arc(x, y, r, 0, Math.PI * 2);
        ctx.fill();    
    }

    rect(0, 0, 600, 180, "pink");
    rect(100, 20, 200, 40, "red");
    rect(50, 40, 100, 30, "blue");
    circle(160, 95, 30, "green");
    rect(170, 30, 5, 80, "pink");
    rect(190, 25, 100, 10, "white");
    circle(150, 110, 10, "white");
}

// The main algorithm
function floodFill(ctx, x, y, r, g, b, a=255) {

    function match(i, source) {
        for (let j = 0; j < 4; j++) {
            if (img.data[i + j] !== source[j]) return false;
        }
        return true;
    }
    
    function set(i, target) {
        for (let j = 0; j < 4; j++) {
            img.data[i + j] = target[j];
        }
    }
    
    const {width, height} = ctx.canvas;
    const img = ctx.getImageData(0, 0, width, height);
    const start = (y * width + x) * 4;
    const line = width * 4;
    const max = line * height;
    
    const source = [...img.data.slice(start, start+4)];
    const target = [r, g, b, a];
    
    // Don't do anything if the start pixel already has the target color
    if (source.every((val, i) => val === target[i])) return;
    
    // Use an explicit stack
    const stack = [start];
    while (stack.length) {
        const i = stack.pop();
        if (!match(i, source)) continue;
        set(i, target);
        if (i < max - line)      stack.push(i + line);
        if (i >= line)           stack.push(i - line);
        if (i % line < line - 4) stack.push(i + 4);
        if (i % line >= 4)       stack.push(i - 4);
    }
    ctx.putImageData(img, 0, 0);
}

const ctx = document.querySelector("canvas").getContext("2d");
setup(ctx);
// After 2 seconds, perform the flood-fill
setTimeout(function () {
    floodFill(ctx, 0, 0, 120, 80, 0, 255); // (0, 0) -> brown
}, 2000);

<canvas width="600" height="180"></canvas>

此演示制作了一个示例绘图，然后从点 (0, 0) 开始进行洪水填充，这意味着它将找到与 (0, 0) 颜色相同的连接像素，并将它们设为棕色。

需要注意的是，画布的默认颜色是黑色，但具有完全透明度，即 alpha 等于 0。因此您可能会错误地认为它是纯白色（在白色背景上时）。在具有默认值 (rgba = 0,0,0,0) 的像素上启动洪水填充，只会填充具有相同 rgba 代码的像素，而不是设置为白色的像素 (255,255,255,255)。