Чтобы создать заливку, вам нужно иметь возможность посмотреть на пиксели, которые уже есть, и убедиться, что они не того цвета, с которого вы начали, так что что-то вроде этого.
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 проблемы.
Это глубоко рекурсивно.
Таким образом, у вас может закончиться место в стеке
Это медленно.
Понятия не имею, слишком ли он медленный, но JavaScript в браузере в основном однопоточный, поэтому, пока выполняется этот код, браузер зависает. Для большого холста это замороженное время может сделать страницу очень медленной, и если она заморожена слишком долго, браузер спросит, хочет ли пользователь убить страницу.
Решением проблемы нехватки места в стеке является реализация нашего собственного стека. Например, вместо рекурсивного вызова fillPixel мы могли бы сохранить массив позиций, на которые мы хотим смотреть. Мы добавляли 4 позиции в этот массив, а затем извлекали элементы из массива, пока он не стал пустым.
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 секунд, чтобы заполнить пустой холст на моей машине, так что да, он, возможно, слишком медленный, но размещение его в рабочем создает новые проблемы, которые заключаются в том, что результат будет асинхронным, поэтому даже если браузер не зависнет, вы, вероятно, захотите запретить пользователю что-то делать, пока оно не завершится.
Другая проблема заключается в том, что вы увидите, что линии сглажены, и поэтому заливка сплошным цветом закрывает линию, но не полностью до нее. Чтобы исправить это, вы можете изменить colorsMatch на проверку достаточно близко, но тогда у вас возникнет новая проблема: если targetColor и fillColor также достаточно близко, он будет продолжать попытки заполниться. Вы можете решить эту проблему, создав другой массив, один байт или один бит на пиксель, для отслеживания мест, которые вы уже проверили.
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 или что-то в этом роде, или, может быть, вы захотите утяжелить по альфа-каналу. Я не знаю, какова хорошая метрика для сопоставления цветов.
Обновлять
Другой способ ускорить процесс - это, конечно, просто оптимизировать код. Кайидо указал на очевидное ускорение, которое заключается в использовании Uint32Array просмотра пикселей. Таким образом, ища пиксель и устанавливая пиксель, остается только одно 32-битное значение для чтения или записи. Одно это изменение делает его примерно в 4 раза быстрее. Однако для заполнения холста размером 4096x4096 пикселей по-прежнему требуется 4 секунды. Может быть другая оптимизация, например, вместо вызова getPixels сделать это встроенным, но не вставляйте новый пиксель в наш список пикселей, чтобы проверить, находятся ли они вне диапазона. Это может быть 10% ускорение (без понятия), но не сделает его достаточно быстрым, чтобы быть интерактивной.
Существуют и другие ускорения, такие как проверка по строке за раз, поскольку строки удобны для кеширования, и вы можете вычислить смещение для строки один раз и использовать его при проверке всей строки, где, как и сейчас, для каждого пикселя мы должны вычислять смещение несколько раз.
Это усложнит алгоритмы, поэтому лучше оставить их на ваше усмотрение.
person
gman
schedule
31.10.2018
