p5.js Flood Fill（存储桶工具）运行缓慢且异常

Question

因此，我编写了一个泛洪填充功能，其功能类似于绘画应用程序的存储桶工具：在封闭的形状内单击，它将填充颜色。

我有两个问题：

1. 性能-假设我的画布为600 * 600（370,000像素），并且在其中绘制了一个大圆圈，例如其中包含约100K像素，则可能需要40（!!!）秒才能完成填充圈！太疯狂了！10,000像素的平方平均平均需要0.4-0.5秒，但是（我猜），因为程序使用的数组的大小增长得如此之快，因此10倍的平方需要大约100倍的填充长度。

2. 填充物有些奇怪。我不太确定它是如何发生的，但始终会留下一些未填充的像素。一点也不多，但是真的很奇怪。

我的洪水填充功能使用4个辅助功能：获取和设置像素颜色，检查是否为要填充的颜色，并检查是否为之前已检查过的像素。这是所有功能：

getPixelColor = (x, y) => {
  let pixelColor = [];
  for (let i = 0; i < pixDens; ++i) {
    for (let j = 0; j < pixDens; ++j) {
      index = 4 * ((y * pixDens + j) * width * pixDens + (x * pixDens + i));
      pixelColor[0] = pixels[index];
      pixelColor[1] = pixels[index + 1];
      pixelColor[2] = pixels[index + 2];
      pixelColor[3] = pixels[index + 3];
    }
  }
  return pixelColor;
};

setPixelColor = (x, y, currentColor) => { //Remember to loadPixels() before using this function, and to updatePixels() after.
  for (let i = 0; i < pixDens; ++i) {
    for (let j = 0; j < pixDens; ++j) {
      index = 4 * ((y * pixDens + j) * width * pixDens + (x * pixDens + i));
      pixels[index] = currentColor[0];
      pixels[index + 1] = currentColor[1];
      pixels[index + 2] = currentColor[2];
      pixels[index + 3] = currentColor[3];
    }
  }
}

isDuplicate = (posHistory, vector) => {
  for (let i = 0; i < posHistory.length; ++i) {
    if (posHistory[i].x === vector.x && posHistory[i].y === vector.y) {
      return true;
    }
  }
  return false;
}

compareColors = (firstColor, secondColor) => {
  for (let i = 0; i < firstColor.length; ++i) {
    if (firstColor[i] !== secondColor[i]) {
      return false;
    }
  }
  return true;
}

floodFill = () => {
  loadPixels();
  let x = floor(mouseX);
  let y = floor(mouseY);
  let startingColor = getPixelColor(x, y);
  if (compareColors(startingColor, currentColor)) {
    return false;
  }
  let pos = [];
  pos.push(createVector(x, y));
  let posHistory = [];
  posHistory.push(createVector(x, y));
  while (pos.length > 0) {
    x = pos[0].x;
    y = pos[0].y;
    pos.shift();
    if (x <= width && x >= 0 && y <= height && y >= 0) {
      setPixelColor(x, y, currentColor);
      let xMinus = createVector(x - 1, y);
      if (!isDuplicate(posHistory, xMinus) && compareColors(getPixelColor(xMinus.x, xMinus.y), startingColor)) {
        pos.push(xMinus);
        posHistory.push(xMinus);
      }
      let xPlus = createVector(x + 1, y);
      if (!isDuplicate(posHistory, xPlus) && compareColors(getPixelColor(xPlus.x, xPlus.y), startingColor)) {
        pos.push(xPlus);
        posHistory.push(xPlus);
      }
      let yMinus = createVector(x, y - 1);
      if (!isDuplicate(posHistory, yMinus) && compareColors(getPixelColor(yMinus.x, yMinus.y), startingColor)) {
        pos.push(yMinus);
        posHistory.push(yMinus);
      }
      let yPlus = createVector(x, y + 1);
      if (!isDuplicate(posHistory, yPlus) && compareColors(getPixelColor(yPlus.x, yPlus.y), startingColor)) {
        pos.push(yPlus);
        posHistory.push(yPlus);
      }
    }
  }
  updatePixels();
}

如果有人可以帮助我解决功能问题，我将不胜感激。非常感谢！！

编辑：所以我更新了自己的洪水填充功能，并删除了我从未使用过的颜色数组。这个数组很大，几乎每次运行时都会调用一些push（）和shift（）方法。不幸的是，小形状的执行时间是99.9％（例如，填充10,000需要花费相同的0.5秒，但是大填充（例如100,000像素）现在花费大约30秒而不是40，所以这是正确的一步）方向。我猜RAM的使用量也下降了，因为它是一个很大的阵列，但是我没有测量它。它仍然留下未填充像素的问题仍然存在。

Answer 1

一点建议：

您实际上不必使用posHistory数组来确定是否设置颜色。如果当前像素的颜色与startingColor相同，则设置颜色，否则不设置。这将具有相同的效果。

posHistory数组在执行期间会越来越大。结果，仅要做确定是否填充单个像素的大量工作。我认为这可能是您的代码运行缓慢的原因。

至于“奇怪的事情”：

这在我之前也发生过。我认为这是因为未填充的像素与startingColor的颜色不同。假设您在白色背景上绘制黑色形状，那么您会期望在某处的黑白部分之间看到一些灰色像素（接近白色）。这些像素起到平滑形状的作用。