floodfill.html

<!doctype html>
<html>
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1, maximum-scale=1">
    <style>
      body {
        background: #ccc;
      }
    </style>
  </head>
  <body>
    <canvas></canvas>
    <script>
      var c = document.querySelector('canvas');
      c.width = 200;
      c.height = 200;
      var ctx = c.getContext('2d');

      ctx.fillStyle = '#fff';
      ctx.fillRect(0, 0, c.width, c.height);
      // draw some stuff
      ctx.strokeRect(10.5,10.5,100,100);
      ctx.strokeRect(50.5,50.5,100,100);

      document.querySelector('canvas').addEventListener('click', function(e) {
        var id = ctx.getImageData(0, 0, c.width, c.height);
        flood(id, e.pageX - c.offsetLeft, e.pageY - c.offsetTop, [255, 0, 0, 255], function() {
          ctx.putImageData(id, 0, 0);
        });
      });


      // All code assumes an ImageData object.
      // ImageData.data is a flat typed array of colors length width * height * 4.
      // colors are of the form [r, g, b, a], values from 0-255.

      function getColor(id, x, y) {
        var offset = (x + y * id.width) * 4;
        return [id.data[offset], id.data[offset+1], id.data[offset+2], id.data[offset+3]];
      }

      function setColor(id, x, y, color) {
        var offset = (x + y * id.width) * 4;
        id.data[offset] = color[0];
        id.data[offset+1] = color[1];
        id.data[offset+2] = color[2];
        id.data[offset+3] = color[3];
      }

      function cmpColor(c1, c2, tolerance) {
        tolerance = tolerance || 0;
        return Math.abs(c1[0] - c2[0]) <= tolerance &&
               Math.abs(c1[1] - c2[1]) <= tolerance &&
               Math.abs(c1[2] - c2[2]) <= tolerance &&
               Math.abs(c1[3] - c2[3]) <= tolerance;
      }

      function flood(imageData, initX, initY, newColor, callback) {
        var len = imageData.data.length;
        var width = imageData.width;
        var w4 = width * 4;
        var position = (initX + initY * width) * 4;
        // used to track where we've been.
        var viewed = {};
        // used instead of recursion.
        var stack = [];
        var initColor = getColor(imageData, initX, initY);

        // add the clicked position to the list of pixels to check.
        stack.push(position);

        // inner function used for painting
        function fill() {
          var iterations = 0;

          // break the paint into chunks to prevent beachballs
          while (stack.length && iterations < 10000) {
            iterations++;
            var current = stack.pop();
            var x = current % w4 / 4;
            var y = current / w4 | 0;

            // mark that we've examined this pixel.
            viewed[current] = true;

            // does the current pixel match the color of the initial pixel?
            var currentColor = getColor(imageData, x, y);
            if (cmpColor(initColor, currentColor)) {
              setColor(imageData, x, y, newColor);
              // if we haven't checked the neighboring pixels, add them to the list to check.
              if ((current - w4) >= 0 && !viewed[current - w4]) {
                stack.push(current - w4);
              }
              if ((current + w4) < len && !viewed[current + w4]) {
                stack.push(current + w4);
              }
              if ((current % w4) - 1 >= 0 && !viewed[current - 4]) {
                stack.push(current - 4);
              }
              if ((current % w4) + 1 < w4 && !viewed[current + 4]) {
                stack.push(current + 4);
              }
            }
          }
          // if we're not done, continue after a timeout.
          if (stack.length) {
            setTimeout(fill, 10);
          } else {
            callback();
          }
        }

        // let's do this.
        fill();
      }

    </script>
  </body>
</html>