现在，我尝试使用文章中的洪水填充算法执行洪水填充算法来填充透明PNG图像在洪水填充算法期间如何避免超过最大调用堆栈大小？ https://stackoverflow.com/questions/59833738/how-can-i-avoid-exceeding-the-max-call-stack-size-during-a-flood-fill-algorithm它使用非递归方法和 Uint32Array 来处理颜色堆栈，工作得很好。
然而，这种洪水填充算法留下了未填充的白色（实际上是浅灰色边缘或抗锯齿边缘）。这是我的代码：
var BrushColorString = '#F3CDA6'; // skin color
canvas.addEventListener('mousedown', function(e) {
const rect = canvas.getBoundingClientRect()
CanvasMouseX = e.clientX - rect.left;
CanvasMouseY = e.clientY - rect.top;
if (mode === 'flood-fill')
{
// test flood fill algorithm
paintAt(context, CanvasMouseX,CanvasMouseY,hexToRgb(BrushColorString));
}
});
function paintAt(ContextOutput,startX, startY,curColor) {
//function paintAt(ctx,startX, startY,curColor) {
// read the pixels in the canvas
const width = ContextOutput.canvas.width,
height = ContextOutput.canvas.height,pixels = width*height;
const imageData = ContextOutput.getImageData(0, 0, width, height);
var data1 = imageData.data;
const p32 = new Uint32Array(data1.buffer);
const stack = [startX + (startY * width)]; // add starting pos to stack
const targetColor = p32[stack[0]];
var SpanLeft = true, SpanRight = true; // logic for spanding left right
var leftEdge = false, rightEdge = false;
// proper conversion of color to Uint32Array
const newColor = new Uint32Array((new Uint8ClampedArray([curColor.r,curColor.g, curColor.b, curColor.a])).buffer)[0];
// need proper comparison of target color and new Color
if (targetColor === newColor || targetColor === undefined) { return } // avoid endless loop
while (stack.length){
let idx = stack.pop();
while(idx >= width && p32[idx - width] === targetColor) { idx -= width }; // move to top edge
SpanLeft = SpanRight = false; // not going left right yet
leftEdge = (idx % width) === 0;
rightEdge = ((idx +1) % width) === 0;
while (p32[idx] === targetColor) {
p32[idx] = newColor;
if(!leftEdge) {
if (p32[idx - 1] === targetColor) { // check left
if (!SpanLeft) {
stack.push(idx - 1); // found new column to left
SpanLeft = true; //
} else if (SpanLeft) {
SpanLeft = false;
}
}
}
if(!rightEdge) {
if (p32[idx + 1] === targetColor) {
if (!SpanRight) {
stack.push(idx + 1); // new column to right
SpanRight = true;
}else if (SpanRight) {
SpanRight = false;
}
}
}
idx += width;
}
}
clearCanvas(ContextOutput);
ContextOutput.putImageData(imageData,0, 0);
};
function hexToRgb(hex) {
var result = /^#?([a-f\d]{2})([a-f\d]{2})([a-f\d]{2})$/i.exec(hex);
return result ? {
r: parseInt(result[1], 16),
g: parseInt(result[2], 16),
b: parseInt(result[3], 16),
a: 255
} : null;
};
到目前为止，我已尝试使用以下建议：
如果您对如何处理洪水填充算法的抗锯齿边缘问题有任何想法，请尽快回复。
Updated:
以下是根据建议修改后的 PaintAt 函数代码，其中考虑了容差：
<div id="container"><canvas id="control" >Does Not Support Canvas Element</canvas></div>
<div><label for="tolerance">Tolerance</label>
<input id="tolerance" type="range" min="0" max="255" value="32" step="1" oninput="this.nextElementSibling.value = this.value"><output>32</output></div>
var canvas = document.getElementById("control");
var context = canvas.getContext('2d');
var CanvasMouseX = -1; var CanvasMouseY = -1;
var BrushColorString = '#F3CDA6'; // skin color
canvas.addEventListener('mousedown', function(e) {
const rect = canvas.getBoundingClientRect()
CanvasMouseX = e.clientX - rect.left;
CanvasMouseY = e.clientY - rect.top;
// testing
if (mode === 'flood-fill')
{
// test flood fill algorithm
paintAt(context,CanvasMouseX,CanvasMouseY,
hexToRgb(BrushColorString),tolerance.value);
}
});
function hexToRgb(hex) {
var result = /^#?([a-f\d]{2})([a-f\d]{2})([a-f\d]{2})$/i.exec(hex);
return result ? {
r: parseInt(result[1], 16),
g: parseInt(result[2], 16),
b: parseInt(result[3], 16),
a: 255
} : null;
};
function clearCanvas(ctx) {
ctx.clearRect(0, 0,ctx.canvas.width,ctx.canvas.height);
};
function colorDistance(index, R00,G00,B00,A00, data0)
{
var index1 = index << 2; // multiplyed by 4
const R = R00 - data0[index1 + 0];
const G = G00 - data0[index1 + 1];
const B = B00 - data0[index1 + 2];
const A = A00 - data0[index1 + 3];
return Math.sqrt((R * R) + (B * B) + (G * G) + (A * A));
}
function paintAt(ContextOutput,startX, startY,curColor,tolerance) {
// read the pixels in the canvas
const width = ContextOutput.canvas.width,
height = ContextOutput.canvas.height, pixels = width*height;
const rightEdgeNum = width - 1, bottomEdgeNum = height - 1;
const imageData = ContextOutput.getImageData(0, 0, width, height);
var data1 = imageData.data;
const p32 = new Uint32Array(data1.buffer);
const stack = [startX + (startY * width)]; // add starting pos to stack
const targetColor = p32[stack[0]];
var SpanLeft = true, SpanRight = true; // logic for spanning left right
var leftEdge = false, rightEdge = false, IsBlend = false;
const DistancesArray = new Uint16Array(pixels); // array distance value
var R=-1,G=-1,B=-1,A = -1,idx =0,Distance=0;
var R0 = data1[(4*(startX + (startY * width)))+0],
G0 = data1[(4*(startX + (startY * width)))+1],
B0 = data1[(4*(startX + (startY * width)))+2],
A0 = data1[(4*(startX + (startY * width)))+3];
var CalculatedTolerance = Math.sqrt(tolerance * tolerance * 4);
const BlendR = curColor.r |0, BlendG = curColor.g |0,
BlendB = curColor.b |0, BlendA = curColor.a|0;
// color variable for blending
const newColor = new Uint32Array((new Uint8ClampedArray([BlendR,BlendG,BlendB,BlendA])).buffer)[0];
if (targetColor === newColor || targetColor === undefined) { return }
// avoid endless loop
while (stack.length){
idx = stack.pop();
while (idx >= width &&
colorDistance(idx - width,R0,G0,B0,A0,data1) <= CalculatedTolerance) { idx -= width }; // move to top edge
SpanLeft = SpanRight = false; // not going left right yet
leftEdge = (idx % width) === 0;
rightEdge = ((idx +1) % width) === 0;
while ((Distance = colorDistance(idx,R0,G0,B0,A0,data1)) <= CalculatedTolerance) {
DistancesArray[idx] = (Distance / CalculatedTolerance) * 255 | 0x8000;
p32[idx] = newColor;
if(!leftEdge) {
if (colorDistance(idx - 1,R0,G0,B0,A0,data1) <= CalculatedTolerance) { // check left
if (!SpanLeft) {
stack.push(idx - 1); // found new column to left
SpanLeft = true; //
} else if (SpanLeft) {
SpanLeft = false;
}
}
}
if(!rightEdge) {
if (colorDistance(idx + 1,R0,G0,B0,A0,data1) <= CalculatedTolerance) {
if (!SpanRight) {
stack.push(idx + 1); // new column to right
SpanRight = true;
}else if (SpanRight) {
SpanRight = false;
}
}
}
idx += width;
}
}
idx = 0;
while (idx <= pixels-1) {
Distance = DistancesArray[idx];
if (Distance !== 0) {
if (Distance === 0x8000) {
p32[idx] = newColor;
} else {
IsBlend = false;
const x = idx % width;
const y = idx / width | 0;
if (x >= 1 && DistancesArray[idx - 1] === 0) { IsBlend = true }
else if (x <= rightEdgeNum -1 && DistancesArray[idx + 1] === 0) { IsBlend = true }
else if (y >=1 && DistancesArray[idx - width] === 0) { IsBlend = true }
else if (y <=bottomEdgeNum-1 && DistancesArray[idx + width] === 0) { IsBlend = true }
if (IsBlend) {
// blending at the edge
Distance &= 0xFF;
Distance = Distance / 255;
const invDist = 1 - Distance;
const idx1 = idx << 2;
data1[idx1 + 0] = data1[idx1 + 0] * Distance + BlendR * invDist;
data1[idx1 + 1] = data1[idx1 + 1] * Distance + BlendG * invDist;
data1[idx1 + 2] = data1[idx1 + 2] * Distance + BlendB * invDist;
data1[idx1 + 3] = data1[idx1 + 3] * Distance + BlendA * invDist;
} else {
p32[idx] = newColor;
}
}
}
idx++;
}
// this recursive algorithm works but still not working well due to the issue stack overflow!
clearCanvas(ContextOutput);
ContextOutput.putImageData(imageData,0, 0);
// way to deal with memory leak at the array.
DistancesArray = [];
newColor = [];
p32 = [];
};
However, the results of flood fill have been found wanting as shown in the transition tolerance as shown here:'
当宽容变得太多的时候，我该如何处理这种问题呢？任何替代算法将不胜感激。
我是已接受答案的作者在洪水填充算法期间如何避免超过最大调用堆栈大小？ https://stackoverflow.com/questions/59833738/how-can-i-avoid-exceeding-the-max-call-stack-size-during-a-flood-fill-algorithm and 画布洪水填充未填充到边缘 https://stackoverflow.com/questions/41304168/canvas-flood-fill-not-filling-to-edge
不幸的是没有完美的解决方案。
下面的方法有问题。
有一个更好的解决方案，但它有 1000 多行长，并且仅代码不适合 32K 答案限制。
这个答案演练了如何使用容差和简单的边缘混合来更改函数以减少边缘锯齿。
Note
检测边缘的最简单方法是使用容差并填充填充原点处像素颜色容差内的像素。
这使得填充与锯齿边缘重叠，然后可以检测并混合锯齿边缘，以减少抗锯齿造成的伪影。
问题是，要获得良好的锯齿覆盖，需要很大的容差，这最终会填充您直观上不希望着色的区域。
颜色可以用红、绿、蓝 3 个值来表示。如果用 x、y、z 替换名称，就很容易看出每种颜色在 3D 空间中具有唯一的位置。
更好的是，这个 3D 空间中任意两种颜色之间的距离与感知的颜色差异直接相关。因此，我们可以使用简单的数学来计算差异（毕达哥拉斯）。
由于我们还需要考虑 Alpha 通道，因此我们需要提高一维。每种颜色及其 Alpha 部分在 4D 空间中都有一个独特的点。这些 4D 颜色之间的距离与颜色和透明度的感知差异直接相关。
幸运的是，我们不需要想象 4D 空间，我们所做的就是扩展数学（毕达哥拉斯适用于所有欧几里德维度）。
因此，我们获得了可以添加到洪水填充函数中的函数和准备代码。
var idx = stack[0] << 2; // remove let first line inside while (stack.length){
const r = data1[idx] ;
const g = data1[idx + 1] ;
const b = data1[idx + 2];
const a = data1[idx + 3]
function colorDist(idx) { // returns the spacial distance from the target color of pixel at idx
idx <<= 2;
const R = r - data1[i];
const G = g - data1[i + 1];
const B = b - data1[i + 2];
const A = a - data1[i + 3];
return (R * R + B * B + G * G + A * A) ** 0.5;
}
在函数声明中，我们添加一个参数容差，指定为 0 到 255 的值
函数声明从
function paintAt(contextOutput, startX, startY, curColor) {
To
function paintAt(contextOutput, startX, startY, curColor, tolerance = 0) {
With tolerance作为可选参数。
tolerance0 只填充targetColor
tolerance255 应填充所有像素我们需要将容差从通道值转换为 4D 距离值，以便 255 覆盖 4D 颜色空间中两种颜色之间的最大距离。
将以下行添加到函数顶部paintAt
tolerance = (tolerance * tolerance * 4) ** 0.5; // normalize to 4D RGBA space
我们现在需要更改像素匹配语句以使用容差。任何你有的地方p32[idx] === targetColor或类似的需要替换为colorDist(idx) <= tolerance。内部 while 循环是个例外，因为我们需要使用 4D 颜色距离
while (checkPixel(ind)) {
becomes
// declare variable dist at top of function
while ((dist = colorDist(idx)) <= tolerance) {
为了消除锯齿，我们需要按与颜色距离成比例的量混合填充颜色。
对所有像素执行此操作意味着，如果颜色距离不为 0 且小于容差，远离填充边缘的像素将获得错误的颜色。
我们只想混合位于填充边缘的像素，不包括画布边缘的像素。对于许多像素，当我们遇到它们时，无法知道像素是否位于填充的边缘。我们只能知道何时找到所有填充的像素。
因此，我们必须保留一个数组来保存所有填充像素的颜色距离
在函数的顶部创建一个缓冲区来保存像素颜色距离。
const distances = new Uint16Array(width*height);
然后在内部循环中以及设置像素颜色设置匹配位置距离。
while ((dist = colorDist(idx)) <= tolerance) {
//Must not fill color here do in second pass p32[idx] = newColor;
distances[idx] = (dist / tolerance) * 255 | 0x8000;
为了跟踪哪些像素被填充，我们设置距离值的最高位。这意味着对于要填充的所有像素，距离将保持非零值，对于要忽略的像素，距离将保持零。这是通过| 0x8000
填充的主要部分还没有完成。在开始下一个通道之前，我们让填充完成它的工作。
外循环退出后，我们一次跨过每个像素一个。检查是否需要填写。
如果需要填充，我们提取颜色距离。如果为零，则设置像素颜色p32大批。如果距离不为零，我们将检查其周围的 4 个像素。如果 4 个相邻像素中的任何一个被标记为不填充distances[idx] === 0并且该像素不在画布边界之外，我们知道它是边缘并且需要混合。
// declare at top of function
var blend, dist, rr, gg, bb, aa;
// need fill color's channels for quickest possible access.
const fr = curColor.r | 0;
const fg = curColor.g | 0;
const fb = curColor.b | 0;
const fa = curColor.a | 0;
// after main fill loop.
idx = 0;
const rightEdge = width - 1, bottomEdge = height - 1;
while (idx < width * height){
dist = distances[idx];
if (dist !== 0) {
if (dist === 0x8000) {
p32[idx] = newColor;
} else {
blend = false;
const x = idx % width;
const y = idx / width | 0;
if (x > 0 && distances[idx - 1] === 0) { blend = true }
else if (x < rightEdge && distances[idx + 1] === 0) { blend = true }
else if (y > 0 && distances[idx - width] === 0) { blend = true }
else if (y < bottomEdge && distances[idx + width] === 0) { blend = true }
if (blend) { // pixels is at fill edge an needs to blend
dist &= 0xFF; // remove fill bit
dist = dist / 255; // normalize to range 0-1
const invDist = 1 - dist; // invert distance
// get index in byte array
const idx1 = idx << 2; // same as idx * 4
// simple blend function (not the same as used by 2D API)
data[idx1] = data[idx1 ] * dist + fr * invDist;
data[idx1 + 1] = data[idx1 + 1] * dist + fg * invDist;
data[idx1 + 2] = data[idx1 + 2] * dist + fb * invDist;
data[idx1 + 3] = data[idx1 + 3] * dist + fa * invDist;
} else {
p32[idx] = newColor;
}
}
}
idx++;
}
现在只需将新的像素数组放到画布上即可。
此示例是代码修改版本的基本包装。它是为了确保我没有犯任何算法错误，并强调使用此方法时的质量或质量缺陷。
画布已缩放 2 倍以使工件更加可见。
功能floodFill取代你的paintAt太大，应分为两部分，一部分用于填充通道，另一部分用于边缘检测和混合。
const ctx = canvas.getContext("2d");
var circle = true;
test();
canvas.addEventListener("click", e => {circle = false; test(e)});
toggleFill.addEventListener("click",e => {circle = true; test(e)});
clear.addEventListener("click",()=>ctx.clearRect(0,0,500,500));
function randomCircle() {
ctx.beginPath();
ctx.strokeStyle = "black";
ctx.lineWidth = 4;
const x = Math.random() * 100 | 0;
const y = Math.random() * 100 | 0;
ctx.arc(x, y, Math.random() * 25 + 25, 0 , Math.PI * 2);
ctx.stroke();
return {x,y};
}
function test(e) {
if (circle) {
toggleFill.textContent = "Click canvas to fill";
randomCircle();
} else {
toggleFill.textContent = "Click button add random circle";
const col = {
r: Math.random() * 255 | 0,
g: Math.random() * 255 | 0,
b: Math.random() * 255 | 0,
a: Math.random() * 255 | 0,
};
floodFill(ctx, (event.offsetX - 1) / 2 | 0, (event.offsetY -1) / 2| 0, col, tolerance.value);
}
}
// Original function from SO question https://stackoverflow.com/q/65359146/3877726
function floodFill(ctx, startX, startY, curColor, tolerance = 0) {
var idx, blend, dist, rr, gg, bb, aa, spanLeft = true, spanRight = true, leftEdge = false, rightEdge = false;
const width = ctx.canvas.width, height = ctx.canvas.height, pixels = width*height;
const imageData = ctx.getImageData(0, 0, width, height);
const data = imageData.data;
const p32 = new Uint32Array(data.buffer);
const stack = [startX + (startY * width)];
const targetColor = p32[stack[0]];
const fr = curColor.r | 0;
const fg = curColor.g | 0;
const fb = curColor.b | 0;
const fa = curColor.a | 0;
const newColor = (fa << 24) + (fb << 16) + (fg << 8) + fr;
if (targetColor === newColor || targetColor === undefined) { return }
idx = stack[0] << 2;
const rightE = width - 1, bottomE = height - 1;
const distances = new Uint16Array(width*height);
tolerance = (tolerance * tolerance * 4) ** 0.5;
const r = data[idx] ;
const g = data[idx + 1] ;
const b = data[idx + 2];
const a = data[idx + 3]
function colorDist(idx) {
if (distances[idx]) { return Infinity }
idx <<= 2;
const R = r - data[idx];
const G = g - data[idx + 1];
const B = b - data[idx + 2];
const A = a - data[idx + 3];
return (R * R + B * B + G * G + A * A) ** 0.5;
}
while (stack.length) {
idx = stack.pop();
while (idx >= width && colorDist(idx - width) <= tolerance) { idx -= width }; // move to top edge
spanLeft = spanRight = false; // not going left right yet
leftEdge = (idx % width) === 0;
rightEdge = ((idx + 1) % width) === 0;
while ((dist = colorDist(idx)) <= tolerance) {
distances[idx] = (dist / tolerance) * 255 | 0x8000;
if (!leftEdge) {
if (colorDist(idx - 1) <= tolerance) {
if (!spanLeft) {
stack.push(idx - 1);
spanLeft = true;
} else if (spanLeft) {
spanLeft = false;
}
}
}
if (!rightEdge) {
if (colorDist(idx + 1) <= tolerance) {
if (!spanRight) {
stack.push(idx + 1);
spanRight = true;
}else if (spanRight) {
spanRight = false;
}
}
}
idx += width;
}
}
idx = 0;
while (idx < pixels) {
dist = distances[idx];
if (dist !== 0) {
if (dist === 0x8000) {
p32[idx] = newColor;
} else {
blend = false;
const x = idx % width;
const y = idx / width | 0;
if (x > 0 && distances[idx - 1] === 0) { blend = true }
else if (x < rightE && distances[idx + 1] === 0) { blend = true }
else if (y > 0 && distances[idx - width] === 0) { blend = true }
else if (y < bottomE && distances[idx + width] === 0) { blend = true }
if (blend) {
dist &= 0xFF;
dist = dist / 255;
const invDist = 1 - dist;
const idx1 = idx << 2;
data[idx1] = data[idx1 ] * dist + fr * invDist;
data[idx1 + 1] = data[idx1 + 1] * dist + fg * invDist;
data[idx1 + 2] = data[idx1 + 2] * dist + fb * invDist;
data[idx1 + 3] = data[idx1 + 3] * dist + fa * invDist;
} else {
p32[idx] = newColor;
}
}
}
idx++;
}
ctx.putImageData(imageData,0, 0);
}canvas {
width: 200px;
height: 200px;
border: 1px solid black;
}<label for="tolerance">Tolerance</label>
<input id="tolerance" type="range" min="0" max="255" value="32" step="1"></input>
<button id ="toggleFill" >Click add random circle</button>
<button id ="clear" >Clear</button><br>
<canvas id="canvas" width="100" height="100"></canvas>