Tôi làm cách nào để thực hiện lấp đầy lũ lụt bằng HTML Canvas?

Question

Có ai đã triển khai thuật toán lấp đầy lũ lụt trong javascript để sử dụng với HTML Canvas không?

Yêu cầu của tôi rất đơn giản: lũ với một màu duy nhất bắt đầu từ một điểm duy nhất, trong đó màu biên là bất kỳ màu nào lớn hơn một đồng bằng nhất định của màu tại điểm được chỉ định.

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) { 
    ... 
} 

Cập nhật:

tôi đã viết thực hiện riêng của tôi về điền lũ lụt, mà sau. Nó rất chậm nhưng chính xác. Khoảng 37% thời gian được thực hiện trong hai hàm mảng mức thấp là một phần của khung nguyên mẫu. Họ được gọi là push và pop, tôi đoán vậy. Phần lớn thời gian còn lại được sử dụng trong vòng lặp chính.

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, khi tôi gọi đây, tôi sử dụng một stopFunction tùy chỉnh:

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; 
    }, 

Nếu bất cứ ai có thể nhìn thấy một cách để cải thiện hiệu suất của mã này, tôi sẽ đánh giá cao nó. Ý tưởng cơ bản là: 1) Màu của hạt giống là màu ban đầu tại điểm bắt đầu ngập lụt. 2) Thử bốn điểm liền kề: lên, phải, xuống và sang trái một pixel. 3) Nếu điểm ngoài phạm vi hoặc đã được truy cập, hãy bỏ qua nó. 4) Nếu không, hãy đẩy điểm lên đến đống điểm thú vị. 5) Bật điểm thú vị tiếp theo ra khỏi ngăn xếp. 6) Nếu màu tại thời điểm đó là màu dừng (như được xác định trong stopFunction) thì dừng xử lý điểm đó và chuyển sang bước 5. 7) Nếu không, hãy chuyển đến bước 2. 8) Khi không còn thú vị nữa điểm đến thăm, dừng vòng lặp.

Hãy nhớ rằng một điểm đã được truy cập yêu cầu một mảng có cùng số phần tử vì có pixel.

Answer 1

Tôi sẽ không xử lý canvas dưới dạng hình ảnh bitmap.

Thay vào đó, tôi sẽ giữ một bộ sưu tập các đối tượng vẽ và sửa đổi bộ sưu tập đó. Sau đó, ví dụ bạn có thể điền vào một đường dẫn hoặc hình dạng hoặc thêm một hình dạng mới có ranh giới của các đối tượng bạn đang cố gắng điền vào.

Tôi không thể nhìn thấy như thế nào "bình thường" floodfill có ý nghĩa trong bản vẽ vector ..

Answer 2

Dưới đây là một thực hiện mà tôi đã làm việc trên. Nó có thể rất chậm nếu màu thay thế quá gần với màu gốc. Chrome nhanh hơn một chút so với Firefox (Tôi chưa thử nghiệm nó trong bất kỳ trình duyệt nào khác).

Tôi chưa thực hiện kiểm tra đầy đủ, vì vậy có thể có các trường hợp cạnh không hoạt động.

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); 
}