如何使用HTML Canvas执行洪水填充？ [英] How can I perform flood fill with HTML Canvas?
本文介绍了如何使用HTML Canvas执行洪水填充？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
有没有人在javascript中使用HTML Canvas实现了一个泛洪填充算法？
Has anyone implemented a flood fill algorithm in javascript for use with HTML Canvas?
我的要求很简单：从一个点开始，边界颜色是大于在指定点处的颜色的特定增量的任何颜色。
My requirements are simple: flood with a single color starting from a single point, where the boundary color is any color greater than a certain delta of the color at the specified point.
var r1, r2; // red values
var g1, g2; // green values
var b1, b2; // blue values
var actualColorDelta = Math.sqrt((r1 - r2)*(r1 - r2) + (g1 - g2)*(g1 - g2) + (b1 - b2)*(b1 - b2))
function floodFill(canvas, x, y, fillColor, borderColorDelta) {
...
}
更新：
我写了自己的洪水填充实现，它是缓慢，但准确。大约37％的时间在两个低级数组函数中，它们是原型框架的一部分。它们被push和pop调用，我假设。大多数的剩余时间花费在主循环中。
I wrote my own implementation of flood fill, which follows. It is slow, but accurate. About 37% of the time is taken up in two low-level array functions that are part of the prototype framework. They are called by push and pop, I presume. Most of the rest of the time is spent in the main loop.
var ImageProcessing;
ImageProcessing = {
/* Convert HTML color (e.g. "#rrggbb" or "#rrggbbaa") to object with properties r, g, b, a.
* If no alpha value is given, 255 (0xff) will be assumed.
*/
toRGB: function (color) {
var r, g, b, a, html;
html = color;
// Parse out the RGBA values from the HTML Code
if (html.substring(0, 1) === "#")
{
html = html.substring(1);
}
if (html.length === 3 || html.length === 4)
{
r = html.substring(0, 1);
r = r + r;
g = html.substring(1, 2);
g = g + g;
b = html.substring(2, 3);
b = b + b;
if (html.length === 4) {
a = html.substring(3, 4);
a = a + a;
}
else {
a = "ff";
}
}
else if (html.length === 6 || html.length === 8)
{
r = html.substring(0, 2);
g = html.substring(2, 4);
b = html.substring(4, 6);
a = html.length === 6 ? "ff" : html.substring(6, 8);
}
// Convert from Hex (Hexidecimal) to Decimal
r = parseInt(r, 16);
g = parseInt(g, 16);
b = parseInt(b, 16);
a = parseInt(a, 16);
return {r: r, g: g, b: b, a: a};
},
/* Get the color at the given x,y location from the pixels array, assuming the array has a width and height as given.
* This interprets the 1-D array as a 2-D array.
*
* If useColor is defined, its values will be set. This saves on object creation.
*/
getColor: function (pixels, x, y, width, height, useColor) {
var redIndex = y * width * 4 + x * 4;
if (useColor === undefined) {
useColor = { r: pixels[redIndex], g: pixels[redIndex + 1], b: pixels[redIndex + 2], a: pixels[redIndex + 3] };
}
else {
useColor.r = pixels[redIndex];
useColor.g = pixels[redIndex + 1]
useColor.b = pixels[redIndex + 2];
useColor.a = pixels[redIndex + 3];
}
return useColor;
},
setColor: function (pixels, x, y, width, height, color) {
var redIndex = y * width * 4 + x * 4;
pixels[redIndex] = color.r;
pixels[redIndex + 1] = color.g,
pixels[redIndex + 2] = color.b;
pixels[redIndex + 3] = color.a;
},
/*
* fill: Flood a canvas with the given fill color.
*
* Returns a rectangle { x, y, width, height } that defines the maximum extent of the pixels that were changed.
*
* canvas .................... Canvas to modify.
* fillColor ................. RGBA Color to fill with.
* This may be a string ("#rrggbbaa") or an object of the form { r: red, g: green, b: blue, a: alpha }.
* x, y ...................... Coordinates of seed point to start flooding.
* bounds .................... Restrict flooding to this rectangular region of canvas.
* This object has these attributes: { x, y, width, height }.
* If undefined or null, use the whole of the canvas.
* stopFunction .............. Function that decides if a pixel is a boundary that should cause
* flooding to stop. If omitted, any pixel that differs from seedColor
* will cause flooding to stop. seedColor is the color under the seed point (x,y).
* Parameters: stopFunction(fillColor, seedColor, pixelColor).
* Returns true if flooding shoud stop.
* The colors are objects of the form { r: red, g: green, b: blue, a: alpha }
*/
fill: function (canvas, fillColor, x, y, bounds, stopFunction) {
// Supply default values if necessary.
var ctx, minChangedX, minChangedY, maxChangedX, maxChangedY, wasTested, shouldTest, imageData, pixels, currentX, currentY, currentColor, currentIndex, seedColor, tryX, tryY, tryIndex, boundsWidth, boundsHeight, pixelStart, fillRed, fillGreen, fillBlue, fillAlpha;
if (Object.isString(fillColor)) {
fillColor = ImageProcessing.toRGB(fillColor);
}
x = Math.round(x);
y = Math.round(y);
if (bounds === null || bounds === undefined) {
bounds = { x: 0, y: 0, width: canvas.width, height: canvas.height };
}
else {
bounds = { x: Math.round(bounds.x), y: Math.round(bounds.y), width: Math.round(bounds.y), height: Math.round(bounds.height) };
}
if (stopFunction === null || stopFunction === undefined) {
stopFunction = new function (fillColor, seedColor, pixelColor) {
return pixelColor.r != seedColor.r || pixelColor.g != seedColor.g || pixelColor.b != seedColor.b || pixelColor.a != seedColor.a;
}
}
minChangedX = maxChangedX = x - bounds.x;
minChangedY = maxChangedY = y - bounds.y;
boundsWidth = bounds.width;
boundsHeight = bounds.height;
// Initialize wasTested to false. As we check each pixel to decide if it should be painted with the new color,
// we will mark it with a true value at wasTested[row = y][column = x];
wasTested = new Array(boundsHeight * boundsWidth);
/*
$R(0, bounds.height - 1).each(function (row) {
var subArray = new Array(bounds.width);
wasTested[row] = subArray;
});
*/
// Start with a single point that we know we should test: (x, y).
// Convert (x,y) to image data coordinates by subtracting the bounds' origin.
currentX = x - bounds.x;
currentY = y - bounds.y;
currentIndex = currentY * boundsWidth + currentX;
shouldTest = [ currentIndex ];
ctx = canvas.getContext("2d");
//imageData = ctx.getImageData(bounds.x, bounds.y, bounds.width, bounds.height);
imageData = ImageProcessing.getImageData(ctx, bounds.x, bounds.y, bounds.width, bounds.height);
pixels = imageData.data;
seedColor = ImageProcessing.getColor(pixels, currentX, currentY, boundsWidth, boundsHeight);
currentColor = { r: 0, g: 0, b: 0, a: 1 };
fillRed = fillColor.r;
fillGreen = fillColor.g;
fillBlue = fillColor.b;
fillAlpha = fillColor.a;
while (shouldTest.length > 0) {
currentIndex = shouldTest.pop();
currentX = currentIndex % boundsWidth;
currentY = (currentIndex - currentX) / boundsWidth;
if (! wasTested[currentIndex]) {
wasTested[currentIndex] = true;
//currentColor = ImageProcessing.getColor(pixels, currentX, currentY, boundsWidth, boundsHeight, currentColor);
// Inline getColor for performance.
pixelStart = currentIndex * 4;
currentColor.r = pixels[pixelStart];
currentColor.g = pixels[pixelStart + 1]
currentColor.b = pixels[pixelStart + 2];
currentColor.a = pixels[pixelStart + 3];
if (! stopFunction(fillColor, seedColor, currentColor)) {
// Color the pixel with the fill color.
//ImageProcessing.setColor(pixels, currentX, currentY, boundsWidth, boundsHeight, fillColor);
// Inline setColor for performance
pixels[pixelStart] = fillRed;
pixels[pixelStart + 1] = fillGreen;
pixels[pixelStart + 2] = fillBlue;
pixels[pixelStart + 3] = fillAlpha;
if (minChangedX < currentX) { minChangedX = currentX; }
else if (maxChangedX > currentX) { maxChangedX = currentX; }
if (minChangedY < currentY) { minChangedY = currentY; }
else if (maxChangedY > currentY) { maxChangedY = currentY; }
// Add the adjacent four pixels to the list to be tested, unless they have already been tested.
tryX = currentX - 1;
tryY = currentY;
tryIndex = tryY * boundsWidth + tryX;
if (tryX >= 0 && ! wasTested[tryIndex]) {
shouldTest.push(tryIndex);
}
tryX = currentX;
tryY = currentY + 1;
tryIndex = tryY * boundsWidth + tryX;
if (tryY < boundsHeight && ! wasTested[tryIndex]) {
shouldTest.push(tryIndex);
}
tryX = currentX + 1;
tryY = currentY;
tryIndex = tryY * boundsWidth + tryX;
if (tryX < boundsWidth && ! wasTested[tryIndex]) {
shouldTest.push(tryIndex);
}
tryX = currentX;
tryY = currentY - 1;
tryIndex = tryY * boundsWidth + tryX;
if (tryY >= 0 && ! wasTested[tryIndex]) {
shouldTest.push(tryIndex);
}
}
}
}
//ctx.putImageData(imageData, bounds.x, bounds.y);
ImageProcessing.putImageData(ctx, imageData, bounds.x, bounds.y);
return { x: minChangedX + bounds.x, y: minChangedY + bounds.y, width: maxChangedX - minChangedX + 1, height: maxChangedY - minChangedY + 1 };
},
getImageData: function (ctx, x, y, w, h) {
return ctx.getImageData(x, y, w, h);
},
putImageData: function (ctx, data, x, y) {
ctx.putImageData(data, x, y);
}
};
BTW，当我调用这个，我使用自定义stopFunction：
BTW, when I call this, I use a custom stopFunction:
stopFill : function (fillColor, seedColor, pixelColor) {
// Ignore alpha difference for now.
return Math.abs(pixelColor.r - seedColor.r) > this.colorTolerance || Math.abs(pixelColor.g - seedColor.g) > this.colorTolerance || Math.abs(pixelColor.b - seedColor.b) > this.colorTolerance;
},
如果任何人都能看到提高此代码性能的方法，欣赏它。基本思想是：
1）种子颜色是在开始洪水时的初始颜色。
2）尝试四个相邻点：上，右，下和左一个像素。
3）如果point超出范围或已经访问过，请跳过它。
4）否则将点推到堆栈的有趣点。
5）从堆栈中弹出下一个有趣的点。
6）如果该点的颜色是停止颜色（在stopFunction中定义），则停止处理该点并跳到步骤5.
7）否则，跳到步骤2.
8）当没有更多有趣的点访问时，停止循环。
If anyone can see a way to improve performance of this code, I would appreciate it. The basic idea is: 1) Seed color is the initial color at the point to start flooding. 2) Try four adjacent points: up, right, down and left one pixel. 3) If point is out of range or has been visited already, skip it. 4) Otherwise push point onto to the stack of interesting points. 5) Pop the next interesting point off the stack. 6) If the color at that point is a stop color (as defined in the stopFunction) then stop processing that point and skip to step 5. 7) Otherwise, skip to step 2. 8) When there are no more interesting points to visit, stop looping.
记住一个点被访问需要一个数组的元素数量相同像素。
Remembering that a point has been visited requires an array with the same number of elements as there are pixels.
推荐答案
这是我一直在努力的一个实现。如果替换颜色太接近原始颜色，它会变得非常慢。它比Firefox更快一点（我没有在任何其他浏览器测试它）。
Here's an implementation that I've been working on. It can get really slow if the replacement color is too close to the original color. It's quite a bit faster in Chrome than Firefox (I haven't tested it in any other browsers).
我还没有做过详尽的测试，所以可能
I also haven't done exhaustive testing yet, so there may be edge cases where it doesn't work.
function getPixel(pixelData, x, y) {
if (x < 0 || y < 0 || x >= pixelData.width || y >= pixelData.height) {
return NaN;
}
var pixels = pixelData.data;
var i = (y * pixelData.width + x) * 4;
return ((pixels[i + 0] & 0xFF) << 24) |
((pixels[i + 1] & 0xFF) << 16) |
((pixels[i + 2] & 0xFF) << 8) |
((pixels[i + 3] & 0xFF) << 0);
}
function setPixel(pixelData, x, y, color) {
var i = (y * pixelData.width + x) * 4;
var pixels = pixelData.data;
pixels[i + 0] = (color >>> 24) & 0xFF;
pixels[i + 1] = (color >>> 16) & 0xFF;
pixels[i + 2] = (color >>> 8) & 0xFF;
pixels[i + 3] = (color >>> 0) & 0xFF;
}
function diff(c1, c2) {
if (isNaN(c1) || isNaN(c2)) {
return Infinity;
}
var dr = ((c1 >>> 24) & 0xFF) - ((c2 >>> 24) & 0xFF);
var dg = ((c1 >>> 16) & 0xFF) - ((c2 >>> 16) & 0xFF);
var db = ((c1 >>> 8) & 0xFF) - ((c2 >>> 8) & 0xFF);
var da = ((c1 >>> 0) & 0xFF) - ((c2 >>> 0) & 0xFF);
return dr*dr + dg*dg + db*db + da*da;
}
function floodFill(canvas, x, y, replacementColor, delta) {
var current, w, e, stack, color, cx, cy;
var context = canvas.getContext("2d");
var pixelData = context.getImageData(0, 0, canvas.width, canvas.height);
var done = [];
for (var i = 0; i < canvas.width; i++) {
done[i] = [];
}
var targetColor = getPixel(pixelData, x, y);
delta *= delta;
stack = [ [x, y] ];
done[x][y] = true;
while ((current = stack.pop())) {
cx = current[0];
cy = current[1];
if (diff(getPixel(pixelData, cx, cy), targetColor) <= delta) {
setPixel(pixelData, cx, cy, replacementColor);
w = e = cx;
while (w > 0 && diff(getPixel(pixelData, w - 1, cy), targetColor) <= delta) {
--w;
if (done[w][cy]) break;
setPixel(pixelData, w, cy, replacementColor);
}
while (e < pixelData.width - 1 && diff(getPixel(pixelData, e + 1, cy), targetColor) <= delta) {
++e;
if (done[e][cy]) break;
setPixel(pixelData, e, cy, replacementColor);
}
for (cx = w; cx <= e; cx++) {
if (cy > 0) {
color = getPixel(pixelData, cx, cy - 1);
if (diff(color, targetColor) <= delta) {
if (!done[cx][cy - 1]) {
stack.push([cx, cy - 1]);
done[cx][cy - 1] = true;
}
}
}
if (cy < canvas.height - 1) {
color = getPixel(pixelData, cx, cy + 1);
if (diff(color, targetColor) <= delta) {
if (!done[cx][cy + 1]) {
stack.push([cx, cy + 1]);
done[cx][cy + 1] = true;
}
}
}
}
}
}
context.putImageData(pixelData, 0, 0, 0, 0, canvas.width, canvas.height);
}
这篇关于如何使用HTML Canvas执行洪水填充？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
