Fill an Unknown Asymmetric Polygon with Pixel Manipulation (WebImage) in JS

Question

Recently, I have been trying to create code to fill a polygon of any shape with color. I have gotten as far as being able to fill a shape that has lines of only one border size correctly, though I have found myself unable to do anything more than that. The problem is that the code does not know when to consider a line of pixels greater than that which it expects as a vertical or horizontal border of the shape. I am going through each pixel of the shape from left to right and checking if any of the pixels have any form of color by checking if the alpha value is 0 or not. Once it finds a pixel that does have an alpha value of anything other than 0, it moves forward a single pixel and then uses the even/odd technique to determine whether the point is inside part of the polygon or not (it makes an infinite line to the right and determines if the number of collisions with colored lines is odd, and if it is, the point is inside the polygon). In general, we consider a single, lone pixel to count as a single line, and we consider a horizontal line of more than one pixel to be two lines because of how often horizontal lines will be part of a border or not. Take the following scenario:

Here, the red dot is the point (pixel) we begin testing from. If we did not consider that horizontal line in the middle to be two points (as is shown by the red lines and x's), we would only have two points of intersection and therefore would not fill the pixel despite the fact that we most definitely do want to fill that pixel. As stated earlier, however, this brings up another problem with a different scenario:

In this case, if we do count a horizontal line of more than one pixel to be two separate lines, we end up not filling any areas with borders that are thicker than the expected thickness. For your reference, the function to handle this is as follows:

//imgData is essentially a WebImage object (explained more below) and r, g, and b are the color values for the fill color
function fillWithColor(imgData, r, g, b) {
  //Boolean determining whether we should color the given pixel(s) or not
  var doColor = false;
  //Booleans determining whether the last pixel found in the entire image was colored
  var blackLast = false;
  //Booleans determining whether the last 1 or 2 pixels found after a given pixel were colored
  var foundBlackPrev, foundBlackPrev2 = false;
  //The number of colored pixels found
  var blackCount = 0;
      
  //Loop through the entire canvas
  for(var y = 0; y < imgData.height; y += IMG_SCALE) {
    for(var x = 0; x < imgData.width; x += IMG_SCALE) {
      //Test if given pixel is colored
      if(getAlpha(imgData, x, y) != 0) {
        //If the last pixel was black, begin coloring
        if(!blackLast) {
          blackLast = true;
          doColor = true;
        }
      } else {
        //If the current pixel is not colored, but the last one was, find all colored lines to the right
        if(blackLast){
          for(var i = x; i < imgData.width; i += IMG_SCALE) {
            //If the pixel is colored...
            if(getAlpha(imgData, i, y) != 0) {
              //If no colored pixel was found before, add to the count
              if(!foundBlackPrev){
                blackCount++;
                foundBlackPrev = true;
              } else {
                //Otherwise, at least 2 colored pixels have been found in a row
                foundBlackPrev2 = true;
              }
            } else { 
              //If two or more colored pixels were found in a row, add to the count
              if(foundBlackPrev2) {
                blackCount++;
              }
              //Reset the booleans
              foundBlackPrev2 = foundBlackPrev = false;
            }
          }
        }
            
        //If the count is odd, we start coloring
        if(blackCount & 1) {
          blackCount = 0;
          doColor = true;
        } else {
          //If the last pixel in the entire image was black, we stop coloring
          if(blackLast) {
            doColor = false;
          }
        }
          
        //Reset the boolean
        blackLast = false;
        //If we are to be coloring the pixel, color it
        if(doColor) {
          //Color the pixel
          for(var j = 0; j < IMG_SCALE; j++) {
            for(var k = 0; k < IMG_SCALE; k++) {
              //This is the same as calling setRed, setGreen, setBlue and setAlpha functions from the WebImage API all at once (parameters in order are WebImage object equivalent, x position of pixel, y position of pixel, red value, green value, blue value, and alpha value)
              setRGB(imgData, x + j, y + k, r, g, b, 255);
            }
          }
        }
      }
    }
  }
  //Update the image (essentially the same as removing all elements from the given area and calling add on the image)
  clearCanvas();
  putImageData(imgData, 0, 0, imgData.width, imgData.height);
  //Return the modified data
  return imgData;
}

Where...

imgData is the collection of all of the pixels in the given area (essentially a WebImage object)

IMG_SCALE is the integer value by which the image has been scaled up (which gives us the scale of the pixels as well). In this example, it is equal to 4 because the image is scaled up to 192x256 (from 48x64). This means that every "pixel" you see in the image is actually comprised of a 4x4 block of identically-colored pixels.

So, what I'm really looking for here is a way to determine whether a given colored pixel that comes after another is part of a horizontal border or if it is just another piece comprising the thickness of a vertical border. In addition, if I have the wrong approach to this problem in general, I would greatly appreciate any suggestions as to how to do this more efficiently. Thank you.

Answer 1

I understand the problem and I think you would do better if you would switch your strategy here. We know the following:

• the point of start is inside the shape
• the color should be filled for every pixel inside the shape

So, we could always push the neighbors of the current point into a queue to be processed and be careful to avoid processing the same points twice, this way traversing all the useful pixels and including them into the coloring plan. The function below is untested.

function fillColor(pattern, startingPoint, color, boundaryColor) {
    let visitQueue = [];
    let output = {};
    if (startingPoint.x - 1 >= 0) visitQueue.push({startingPoint.x - 1, startingPoint.y});
    if (startingPoint.x + 1 < pattern.width) visitQueue.push({startingPoint.x + 1, startingPoint.y});
    if (startingPoint.y + 1 < pattern.height) visitQueue.push({startingPoint.x, startingPoint.y + 1});
    if (startingPoint.y - 1 >= 0) visitQueue.push({startingPoint.x, startingPoint.y - 1});
    let visited = {};
    while (visitQueue.length > 0) {
        let point = visitQueue[0];
        visitQueue.shift();
        if ((!visited[point.x]) || (visited[point.x].indexOf(point.y) < 0)) {
            if (!visited[point.x]) visited[point.x] = [];
            visited[point.x].push(point.y);
            if (isBlank(pattern, point)) { //you need to implement isBlank
                if (!output[point.x]) output[point.x] = [];
                output[point.x].push(point.y);
                if (point.x + 1 < pattern.width) visitQueue.push({point.x + 1, point.y});
                if (point.x - 1 >= 0) visitQueue.push({point.x - 1, point.y});
                if (point.y + 1 < pattern.height) visitQueue.push({point.x, point.y + 1});
                if (point.y - 1 >= 0) visitQueue.push({point.x, point.y - 1})
            }
        }
    }
    return output;
}

Answer 2

const ctx = document.querySelector("canvas").getContext("2d");

//ctx.lineWidth(10);//-as you asked we are setting greater border or line width,BUT "LINEWIDTH" IS NOT WORKING IN INBUILT STACKOVERFLOW SNIPPET USE IT IN A FILE I THINK STACKOVERFLOW IS NOT UP-TO-DATE,IN ANY IDE UNCOMENT THIS

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

function getMousePosition(canvas, event) {
  let rect = canvas.getBoundingClientRect();
  let mx = event.clientX - rect.left;
  let my = event.clientY - rect.top;
  console.log("Coordinate x: " + mx, "Coordinate y: " + my);
  floodFill(ctx, mx, my, [155, 0, 255, 255], 128);
}

let canvasElem = document.querySelector("canvas");

canvasElem.addEventListener("mousedown", function(e) {
  getMousePosition(canvasElem, e);
});



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>

This is based on other answers note:"LINEWIDTH" IS NOT WORKING IN INBUILT STACKOVERFLOW SNIPPET USE IT IN A FILE I THINK STACKOVERFLOW IS NOT UP-TO-DATE,

But it works well in simple HTML,JS website

Answer 3

As far as I understood you cannot "consider a horizontal line of more than one pixel to be two lines". I don't think you need to count black pixels the way you do, rather count groups of 1 or more pixels.

I would also tidy the code by avoiding using the "doColor" boolean variable. You could rather move the coloring code to a new function color(x,y) and call it straight away.