时间戳

首页 > 解决方案 > p5.j​​s Flood Fill（桶工具）工作缓慢而奇怪

javascript - p5.j​​s Flood Fill（桶工具）工作缓慢而奇怪

问题描述

所以我写了一个洪水填充函数，它就像一个绘画应用程序桶工具：你点击一个封闭的形状，它会用一种颜色填充。

我有两个问题：

  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 使用率也下降了，因为它是一个非常大的数组，但我没有测量它。它留下未填充像素的奇怪问题仍然存在。

标签： javascriptp5.jsflood-fill

解决方案

一个小建议：

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

数组在执行过程中posHistory会越来越大。因此，为了确定是否填充单个像素，必须做很多工作。我认为这可能是您的代码运行缓慢的原因。

至于“怪事”：

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

推荐阅读