Wie kann ich die Überfüllung mit HTML Canvas durchführen?

Question

Hat jemand einen Flood-Fill-Algorithmus in JavaScript zur Verwendung mit HTML Canvas implementiert?

Meine Anforderungen sind einfach: Flood mit einer einzigen Farbe von einem einzigen Punkt aus, wobei die Grenzfarbe eine Farbe größer als ein bestimmtes Delta der Farbe an dem angegebenen Punkt ist.

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

Update:

Ich schrieb meine eigene Implementierung von Hochwasserfüllung, die folgt. Es ist langsam, aber genau. Ungefähr 37% der Zeit werden in zwei Array-Funktionen auf niedriger Ebene aufgegriffen, die Teil des Prototyp-Frameworks sind. Sie werden von Push und Pop genannt, nehme ich an. Der Großteil der restlichen Zeit wird in der Hauptschleife verbracht.

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, wenn ich das nennen, verwende ich eine benutzerdefinierte Stopfunktion:

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

Wenn jemand eine Möglichkeit, die Leistung dieses Codes zu verbessern, sehen kann, ich es schätzen würde. Die Grundidee ist: 1) Samenfarbe ist die Anfangsfarbe an dem Punkt, um Überschwemmung zu beginnen. 2) Probieren Sie vier benachbarte Punkte aus: oben, rechts, unten und links ein Pixel. 3) Wenn der Punkt außerhalb des Bereichs liegt oder bereits besucht wurde, überspringen Sie ihn. 4) Ansonsten drücken Sie auf den Stapel interessanter Punkte. 5) Pop den nächsten interessanten Punkt vom Stapel. 6) Wenn die Farbe an diesem Punkt eine Stoppfarbe ist (wie in der stopFunction definiert), dann bearbeite diesen Punkt und gehe zu Schritt 5. 7) Ansonsten gehe zu Schritt 2. 8) Wenn es keine interessanteren gibt Punkte zu besuchen, stoppen Schleifen.

Wenn Sie sich erinnern, dass ein Punkt besucht wurde, benötigen Sie ein Array mit der gleichen Anzahl von Elementen wie Pixel.

Answer 1

Ich würde die Zeichenfläche nicht als Bitmap-Bild behandeln.

Stattdessen würde ich eine Sammlung von Mal-Objekten behalten und diese Sammlung ändern. Dann können Sie beispielsweise einen Pfad oder eine Form füllen oder eine neue Form mit den Grenzen der Objekte hinzufügen, die Sie füllen möchten.

Ich kann nicht sehen, wie „normal“ floodFill Sinn in Vektor-Zeichenprogramm macht ..

Answer 2

Hier ist eine Implementierung, die ich auf gearbeitet. Es kann sehr langsam werden, wenn die Ersatzfarbe zu nah an der Originalfarbe ist. In Chrome ist es ein bisschen schneller als in Firefox (ich habe es in keinem anderen Browser getestet).

Ich habe auch noch nicht erschöpfende Tests gemacht, also kann es Kantenfälle geben, wo es nicht funktioniert.

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