如何在JavaScript中对HTML画布进行泛洪填充？ [英] How do I do flood fill on the HTML canvas in JavaScript?
问题描述
如下面链接中所附的是我的画布的截图（外框是画布）。内框是灰色框，线是画布中绘制的线。如何使用特定颜色创建填充整个画布（内灰框和线条除外）的泛色填充功能？
As attached in the link below is a screenshot of my canvas (outer box is the canvas). The inner box is a grey box and the line is a line drawn in the canvas. How do I create a flood fill function that fills the entire canvas (except the inner grey box as well as the line) with a specific color?
该函数应接受三个仅变量，xy和颜色，如下所示，但我不知道如何继续：
The function should accept three variables only, x y and color, as seen below, but I'm not sure how to continue:
floodFill(x, y, color) {
this.canvasColor[x][y] = color;
this.floodFill(x-1, y, color);
this.floodFill(x+1, y, color);
this.floodFill(x, y-1, color);
this.floodFill(x, y+1, color);
}
推荐答案
要创建洪水填充，您需要能够查看已经存在的像素，并检查它们不是你开始使用的颜色，所以就像这样。
To create a flood fill you need to be able to look at the pixels that are there already and check they aren't the color you started with so something like this.
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, [255, 0, 0, 255]);
function getPixel(imageData, x, y) {
if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
return [-1, -1, -1, -1]; // impossible color
} else {
const offset = (y * imageData.width + x) * 4;
return imageData.data.slice(offset, offset + 4);
}
}
function setPixel(imageData, x, y, color) {
const offset = (y * imageData.width + x) * 4;
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[0];
}
function colorsMatch(a, b) {
return a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
}
function floodFill(ctx, x, y, fillColor) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// get the color we're filling
const targetColor = getPixel(imageData, x, y);
// check we are actually filling a different color
if (!colorsMatch(targetColor, fillColor)) {
fillPixel(imageData, x, y, targetColor, fillColor);
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}
function fillPixel(imageData, x, y, targetColor, fillColor) {
const currentColor = getPixel(imageData, x, y);
if (colorsMatch(currentColor, targetColor)) {
setPixel(imageData, x, y, fillColor);
fillPixel(imageData, x + 1, y, targetColor, fillColor);
fillPixel(imageData, x - 1, y, targetColor, fillColor);
fillPixel(imageData, x, y + 1, targetColor, fillColor);
fillPixel(imageData, x, y - 1, targetColor, fillColor);
}
}
<canvas></canvas>
此代码至少存在2个问题。
There's at least 2 problems with this code though.
-
这是非常递归的。
It's deeply recursive.
所以你可能用完了堆栈空间
So you might run out of stack space
这很慢。
不知道它是否太慢但是浏览器中的JavaScript主要是单线程的，所以当这段代码运行时，浏览器被冻结了。对于大型画布，冻结时间可能会使页面变得非常慢，如果冻结时间过长，浏览器会询问用户是否要杀死页面。
No idea if it's too slow but JavaScript in the browser is mostly single threaded so while this code is running the browser is frozen. For a large canvas that frozen time might make the page really slow and if it's frozen too long the browser will ask if the user wants to kill the page.
耗尽堆栈空间的解决方案是实现我们自己的堆栈。例如，我们可以保留一系列我们想要查看的位置，而不是递归调用 fillPixel 。我们将4个位置添加到该数组，然后从数组中弹出，直到它为空
The solution to running out of stack space is to implement our own stack. For example instead of recursively calling fillPixel we could keep an array of positions we want to look at. We'd add the 4 positions to that array and then pop things off the array until it's empty
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, [255, 0, 0, 255]);
function getPixel(imageData, x, y) {
if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
return [-1, -1, -1, -1]; // impossible color
} else {
const offset = (y * imageData.width + x) * 4;
return imageData.data.slice(offset, offset + 4);
}
}
function setPixel(imageData, x, y, color) {
const offset = (y * imageData.width + x) * 4;
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[0];
}
function colorsMatch(a, b) {
return a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
}
function floodFill(ctx, x, y, fillColor) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// get the color we're filling
const targetColor = getPixel(imageData, x, y);
// check we are actually filling a different color
if (!colorsMatch(targetColor, fillColor)) {
const pixelsToCheck = [x, y];
while (pixelsToCheck.length > 0) {
const y = pixelsToCheck.pop();
const x = pixelsToCheck.pop();
const currentColor = getPixel(imageData, x, y);
if (colorsMatch(currentColor, targetColor)) {
setPixel(imageData, x, y, fillColor);
pixelsToCheck.push(x + 1, y);
pixelsToCheck.push(x - 1, y);
pixelsToCheck.push(x, y + 1);
pixelsToCheck.push(x, y - 1);
}
}
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}
<canvas></canvas>
它太慢的解决办法是让它一次运行一点或将其移动到工人身上。虽然这是一个例子，但我觉得在同一个答案中显示的内容有点太多了。我在4096x4096画布上测试了上面的代码，并且在我的机器上填充空白画布需要16秒，所以是的，它可以说太慢但是把它放在一个工人中会带来新的问题，即结果将是异步的，所以即使浏览器也是如此不会冻结你可能想要阻止用户做什么直到它完成。
The solution to it being too slow is either to make it run a little at a time OR to move it to a worker. I think that's a little too much to show in the same answer though here's an example. I tested the code above on a 4096x4096 canvas and it took 16 seconds to fill a blank canvas on my machine so yes it's arguably too slow but putting it in a worker brings new problems which is that the result will be asynchronous so even though the browser wouldn't freeze you'd probably want to prevent the user from doing something until it finishes.
另一个问题是你会看到这些线是抗锯齿的，所以填充一个纯色填充关闭线，但不是一直到它。要解决此问题，您可以更改 colorsMatch 以检查足够接近，但是如果 targetColor 和 fillColor 也足够接近它将继续尝试填充自己。你可以通过制作另一个数组，每个像素一个字节或一位来跟踪你已经准备好检查的地方来解决这个问题。
Another issue is you'll see the lines are antialiased and so filling with a solid color fills close the the line but not all the way up to it. To fix that you can change colorsMatch to check for close enough but then you have a new problem that if targetColor and fillColor are also close enough it will keep trying to fill itself. You could solve that by making another array, one byte or one bit per pixel to track places you've ready checked.
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, [255, 0, 0, 255], 128);
function getPixel(imageData, x, y) {
if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
return [-1, -1, -1, -1]; // impossible color
} else {
const offset = (y * imageData.width + x) * 4;
return imageData.data.slice(offset, offset + 4);
}
}
function setPixel(imageData, x, y, color) {
const offset = (y * imageData.width + x) * 4;
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[0];
}
function colorsMatch(a, b, rangeSq) {
const dr = a[0] - b[0];
const dg = a[1] - b[1];
const db = a[2] - b[2];
const da = a[3] - b[3];
return dr * dr + dg * dg + db * db + da * da < rangeSq;
}
function floodFill(ctx, x, y, fillColor, range = 1) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// flags for if we visited a pixel already
const visited = new Uint8Array(imageData.width, imageData.height);
// get the color we're filling
const targetColor = getPixel(imageData, x, y);
// check we are actually filling a different color
if (!colorsMatch(targetColor, fillColor)) {
const rangeSq = range * range;
const pixelsToCheck = [x, y];
while (pixelsToCheck.length > 0) {
const y = pixelsToCheck.pop();
const x = pixelsToCheck.pop();
const currentColor = getPixel(imageData, x, y);
if (!visited[y * imageData.width + x] &&
colorsMatch(currentColor, targetColor, rangeSq)) {
setPixel(imageData, x, y, fillColor);
visited[y * imageData.width + x] = 1; // mark we were here already
pixelsToCheck.push(x + 1, y);
pixelsToCheck.push(x - 1, y);
pixelsToCheck.push(x, y + 1);
pixelsToCheck.push(x, y - 1);
}
}
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}
<canvas></canvas>
请注意此版本的 colorsMatch 正在使用的是一种天真。转换为HSV或其他东西可能更好，或者你想通过alpha加权。我不知道匹配颜色有什么好的指标。
Note that this version of colorsMatch is using is kind of naieve. It might be better to convert to HSV or something or maybe you want to weight by alpha. I don't know what a good metric is for matching colors.
另一种加快速度的方法当然只是优化代码。 Kaiido指出了一个明显的加速，即在像素上使用 Uint32Array 视图。这样查找像素并设置像素只需要一个32位的值来读取或写入。 只是这一改变使它大约快4倍。尽管如此，填充4096x4096画布仍需要4秒钟。可能还有其他优化，而不是调用 getPixels 使内联但不要在我们的像素列表上推一个新像素来检查它们是否超出范围。它可能加速10％（不知道），但不会让它足够快以达到交互速度。
Another way to speed things up is of course to just optimize the code. Kaiido pointed out an obvious speedup which is to use a Uint32Array view on the pixels. That way looking up a pixel and setting a pixel there's just one 32bit value to read or write. Just that change makes it about 4x faster. It still takes 4 seconds to fill a 4096x4096 canvas though. There might be other optimization like instead of calling getPixels make that inline but don't push a new pixel on our list of pixels to check if they are out of range. It might be 10% speed up (no idea) but won't make it fast enough to be an interactive speed.
还有其他加速比如检查行行是缓存友好的时间，你可以计算一次行的偏移量，并在检查整行时使用它，现在对于每个像素，我们必须多次计算偏移量。
There are other speedups like checking across a row at a time since rows are cache friendly and you can compute the offset to a row once and use that while checking the entire row where as now for every pixel we have to compute the offset multiple times.
这些会使algorthim复杂化，所以最好留给你弄清楚。
Those will complicate the algorthim so they are best left for you to figure out.
这篇关于如何在JavaScript中对HTML画布进行泛洪填充？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
