Использовать стек или Почему рекурсия в JavaScript отстой.
Рекурсия - это просто ленивый стек. Он не только ленив, он использует больше памяти и намного медленнее, чем традиционные стеки
Чтобы завершить его (как вы обнаружили) В JavaScript рекурсия рискованна, поскольку стек вызовов очень мал, и вы можете никогда не знаешь, сколько стека вызовов было использовано при вызове вашей функции.
Некоторые bottle шеи, а здесь
Получение данных изображения через getImageData - интенсивная задача для многих устройств , Получение 1 пикселя может занять столько же времени, сколько и получение 65000 пикселей. Вызов getImageData для каждого пикселя - очень плохая идея. Получите все пиксели один раз и получите доступ к пикселям непосредственно из ОЗУ
Используйте Uint32Array, чтобы вы могли обработать пиксель за один шаг, а не проверять каждый канал по очереди.
Пример
Используя простой массив в качестве стека, каждый элемент, помещаемый в стек, является индексом нового пикселя для заполнения. Таким образом, вместо того, чтобы создавать новый контекст выполнения, новую локальную область и связанные с ней переменные, замыкание и многое другое. Одиночное 64-битное число занимает место записи callStack.
См. Демонстрацию для альтернативного метода поиска пикселя заливки
function floodFill(x, y, targetColor, newColor) {
const w = ctx.canvas.width, h = ctx.canvas.height;
const imgData = ctx.getImageData(0, 0, w, h);
const p32 = new Uint32Array(imgData.data.buffer);
const channelMask = 0xFFFFFF; // Masks out Alpha NOTE order of channels is ABGR
const cInvMask = 0xFF000000; // Mask out BGR
const canFill = idx => (p32[idx] & channelMask) === targetColor;
const setPixel = (idx, newColor) => p32[idx] = (p32[idx] & cInvMask) | newColor;
const stack = [x + y * w]; // add starting pos to stack
while (stack.length) {
let idx = stack.pop();
setPixel(idx, newColor);
// for each direction check if that pixel can be filled and if so add it to the stack
canFill(idx + 1) && stack.push(idx + 1); // check right
canFill(idx - 1) && stack.push(idx - 1); // check left
canFill(idx - w) && stack.push(idx - w); // check Up
canFill(idx + w) && stack.push(idx + w); // check down
}
// all done when stack is empty so put pixels back to canvas and return
ctx.putImageData(imgData,0, 0);
}
Использование
Использование функции немного другой. id не используется, а цвета targetColor и newColor должны быть 32-битными словами с обратными red, green, blue, alpha.
Например, если targetColor был желтым = [255, 255, 0], а newColor был синим =[0, 0, 255], затем для каждого из них возвращается RGB и вызывается заливка с
const yellow = 0xFFFF;
const blue = 0xFF0000;
floodFill(x, y, yellow, blue);
Обратите внимание , что я соответствую вашей функции и полностью игнорирую альфа
Неэффективный алгоритм
Обратите внимание , что этот стиль заливки (пометить до 4 соседей) очень неэффективен, так как многие пиксели будут помечены для заполнения и ко времени их выталкивания из стека он уже будет заполнен другим соседом.
Следующий GIF лучше всего иллюстрирует проблему. Заполнение 4 на 3 области зеленым цветом.
- Сначала установите пиксель зеленым,
- Затем pu sh, чтобы сложить, если не зеленый, право, влево, вверх, вниз [иллюстрация красные, оранжевые, голубые, фиолетовые рамки]
- Сдвиньте нижнюю часть и установите зеленый цвет
- Повтор
Когда добавляется место, которое уже находится в стеке, оно вставляется (только для иллюстрации)
Обратите внимание , что, когда все пиксели зеленого цвета, в стеке по-прежнему есть 6 элементов, которые все еще нужно вытолкнуть. По моим оценкам, в среднем вы будете обрабатывать в 1,6 раза больше необходимых пикселей. Для большого изображения 2000sq это 2 миллиона (много) пикселей
Использование стека массивов вместо стека вызовов означает
- Больше никаких переполнений стека вызовов
- Более быстрый код у вашей логики c есть некоторые проблемы. Он по-прежнему использует стек, но ограничивает количество записей, помещаемых в стек, равным количеству уникальных столбцов в области заполнения.
- Включает альфа в тесте заполнения пикселя и цвет записи пикселя , Упрощение кода чтения и записи в пикселях.
- Проверяет края холста, а не заполняет его вне ширины холста (возвращая петлю назад стиль астероидов AKA)
- Считывает целевой цвет с холста вначале x, y pixel
- Заполняет столбцы от самого верхнего пикселя в каждом столбце и разветвляется только влево или вправо, если предыдущий левый или правый пиксель не был целевым цветом. Это уменьшает количество пикселей до pu sh стека на порядки.
Нажмите, чтобы заполнить заливку
function floodFill(x, y, newColor) {
var left, right, leftEdge, rightEdge;
const w = ctx.canvas.width, h = ctx.canvas.height, pixels = w * h;
const imgData = ctx.getImageData(0, 0, w, h);
const p32 = new Uint32Array(imgData.data.buffer);
const stack = [x + y * w]; // add starting pos to stack
const targetColor = p32[stack[0]];
if (targetColor === newColor || targetColor === undefined) { return } // avoid endless loop
while (stack.length) {
let idx = stack.pop();
while(idx >= w && p32[idx - w] === targetColor) { idx -= w }; // move to top edge
right = left = false;
leftEdge = (idx % w) === 0;
rightEdge = ((idx +1) % w) === 0;
while (p32[idx] === targetColor) {
p32[idx] = newColor;
if(!leftEdge) {
if (p32[idx - 1] === targetColor) { // check left
if (!left) {
stack.push(idx - 1); // found new column to left
left = true; //
}
} else if (left) { left = false }
}
if(!rightEdge) {
if (p32[idx + 1] === targetColor) {
if (!right) {
stack.push(idx + 1); // new column to right
right = true;
}
} else if (right) { right = false }
}
idx += w;
}
}
ctx.putImageData(imgData,0, 0);
return;
}
var w = canvas.width;
var h = canvas.height;
const ctx = canvas.getContext("2d");
var i = 400;
const fillCol = 0xFF0000FF
const randI = v => Math.random() * v | 0;
ctx.fillStyle = "#FFF";
ctx.fillRect(0, 0, w, h);
ctx.fillStyle = "#000";
while(i--) {
ctx.fillRect(randI(w), randI(h), 20, 20);
ctx.fillRect(randI(w), randI(h), 50, 20);
ctx.fillRect(randI(w), randI(h), 10, 60);
ctx.fillRect(randI(w), randI(h), 180, 2);
ctx.fillRect(randI(w), randI(h), 2, 182);
ctx.fillRect(randI(w), randI(h), 80, 6);
ctx.fillRect(randI(w), randI(h), 6, 82);
ctx.fillRect(randI(w), randI(h), randI(40), randI(40));
}
i = 400;
ctx.fillStyle = "#888";
while(i--) {
ctx.fillRect(randI(w), randI(h), randI(40), randI(40));
ctx.fillRect(randI(w), randI(h), randI(4), randI(140));
}
var fillIdx = 0;
const fillColors = [0xFFFF0000,0xFFFFFF00,0xFF00FF00,0xFF00FFFF,0xFF0000FF,0xFFFF00FF];
canvas.addEventListener("click",(e) => {
floodFill(e.pageX | 0, e.pageY | 0, fillColors[(fillIdx++) % fillColors.length]);
});
canvas {
position: absolute;
top: 0px;
left: 0px;
}
<canvas id="canvas" width="2048" height="2048">