javascript – Draw boxes around shapes on canvas

You can do this naively with a simple flood fill-style algorithm that keeps track of the max/min points of each black area in all 4 directions.

The algorithm may visit every pixel twice and uses linear space. It also uses recursion, so it’ll blow the stack if your black blobs are too large. Refactoring to use an explicit stack would avoid that. In other words, it’s not optimized at all, just a proof of concept.

Here’s the basic algorithm without a canvas. Note that it gives the points only within grid bounds, which would technically put the box on the edges of the shape, but you can add/subtract 1 (or another padding amount) to each corner to move the bounding box outside of the shape as desired.

const findBoundingBoxes = grid => {
  const flood = (i, j, best) => {
    if (i < 0 || j < 0 ||
        i >= grid.length || j >= grid[i].length ||
        !grid[i][j] || visited[i][j]) {
      return;
    }

    visited[i][j] = true;
    best.top = Math.min(best.top, i);
    best.bottom = Math.max(best.bottom, i);
    best.left = Math.min(best.left, j);
    best.right = Math.max(best.right, j);

    for (let di = -1; di < 2; di++) {
      for (let dj = -1; dj < 2; dj++) {
        if (di !== 0 || dj !== 0) {
          flood(i + di, j + dj, best);
        }
      }
    }
  };

  const boxes = [];
  const visited = [...Array(grid.length)]
    .map((_, i) => [...Array(grid[i].length)].fill(false));

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (!grid[i][j] || visited[i][j]) {
        continue;
      }

      const best = {top: i, bottom: i, left: j, right: j};
      flood(i, j, best);
      boxes.push({
        topLeft: {x: best.left, y: best.top},
        topRight: {x: best.right, y: best.top},
        bottomLeft: {x: best.left, y: best.bottom},
        bottomRight: {x: best.right, y: best.bottom},
      });
    }
  }

  return boxes;
};

const grid = [
  "0000000000000",
  "0001100001000",
  "0011110111110",
  "0001100111100",
  "0000000000000",
].map(e => e.split("").map(Number));
console.log(findBoundingBoxes(grid));

Now, on a canvas. I’m converting the image data to a 2d grid for ease of coding, which isn’t performance-conscious.

const findBoundingBoxes = grid => {
  const flood = (i, j, best) => {
    if (i < 0 || j < 0 ||
        i >= grid.length || j >= grid[i].length ||
        !grid[i][j] || visited[i][j]) {
      return;
    }

    visited[i][j] = true;
    best.top = Math.min(best.top, i);
    best.bottom = Math.max(best.bottom, i);
    best.left = Math.min(best.left, j);
    best.right = Math.max(best.right, j);

    for (let di = -1; di < 2; di++) {
      for (let dj = -1; dj < 2; dj++) {
        if (di !== 0 || dj !== 0) {
          flood(i + di, j + dj, best);
        }
      }
    }
  };

  const boxes = [];
  const visited = [...Array(grid.length)]
    .map((_, i) => [...Array(grid[i].length)].fill(false));

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (!grid[i][j] || visited[i][j]) {
        continue;
      }

      const best = {top: i, bottom: i, left: j, right: j};
      flood(i, j, best);
      boxes.push({
        topLeft: {x: best.left, y: best.top},
        topRight: {x: best.right, y: best.top},
        bottomRight: {x: best.right, y: best.bottom},
        bottomLeft: {x: best.left, y: best.bottom},
      });
    }
  }

  return boxes;
};

const canvas = document.createElement("canvas");
canvas.style.border = "1px solid blue";
document.body.appendChild(canvas);
const ctx = canvas.getContext("2d");
const img = new Image();
img.onload = function() {
  const {width: w, height: h} = this;
  canvas.width = w;
  canvas.height = h;
  ctx.drawImage(this, 0, 0, w, h);
  const {data} = ctx.getImageData(0, 0, w, h);
  const grid = [...Array(h)].map((_, i) => 
    [...Array(w)].map((_, j) => data[(i*w+j)*4] < 255 ? 1 : 0)
  );
  const pad = 1;
  ctx.strokeStyle = "red";

  for (const box of findBoundingBoxes(grid)) {
    const w = box.topRight.x - box.topLeft.x;
    const h = box.bottomLeft.y - box.topLeft.y;
    ctx.strokeRect(
      box.topLeft.x - pad + 0.5,
      box.topLeft.y - pad + 0.5,
      w + pad * 2, h + pad * 2
    );
  }
};
img.src = "data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAMgAAADICAIAAAAiOjnJAAABhGlDQ1BJQ0MgcHJvZmlsZQAAKJF9kT1Iw0AcxV9TxSIVB4uIimSoThZERRylikWwUNoKrTqYXPoFTRqSFBdHwbXg4Mdi1cHFWVcHV0EQ/ABxdHJSdJES/5cUWsR4cNyPd/ced+8AoV5mqtkxAaiaZSRjUTGTXRW7XuFHAP0YwZDETD2eWkzDc3zdw8fXuwjP8j735+hRciYDfCLxHNMNi3iDeGbT0jnvE4dYUVKIz4nHDbog8SPXZZffOBccFnhmyEgn54lDxGKhjeU2ZkVDJZ4mDiuqRvlCxmWF8xZntVxlzXvyFwZz2kqK6zSHEcMS4khAhIwqSijDQoRWjRQTSdqPevgHHX+CXDK5SmDkWEAFKiTHD/4Hv7s181OTblIwCnS+2PbHKNC1CzRqtv19bNuNE8D/DFxpLX+lDsx+kl5raeEjoHcbuLhuafIecLkDDDzpkiE5kp+mkM8D72f0TVmg7xboXnN7a+7j9AFIU1fLN8DBITBWoOx1j3cH2nv790yzvx9wDHKmj+oRMgAAAAlwSFlzAAAuIwAALiMBeKU/dgAAAAd0SU1FB+YDCBYgCuMnEn4AAAAZdEVYdENvbW1lbnQAQ3JlYXRlZCB3aXRoIEdJTVBXgQ4XAAAC7klEQVR42u3d0WrkMAxA0Trk/3/ZfS20U5jBUizr3NeFZRmfkZ1smo4555e0ustHILAElsCSwBJYAksCS2AJLAksgSWwJLAElsCSwBJYAksCS2AJLAks7di92z9ojPHqj/wIZKHGDqv1DybIwEoihRdYgaTwAiuQFF6uCmNVhf7N2h1W9Nqz1RFWzqqz1QtW5nqz1QVW/kqzdT6sp9aYrZNhPbu6bHW5KhRYhwwMQ8vEElilRoWhZWIJrFJDwtAysQSWBJbKw9rzQOOYZWIJLAksgSWwJLAElsCSEmDt+RPJfk7axBJYElgqD2u3A40DloklsIoMCePKxBJYRUaFcWViCawiA8O4OnliPbW6VJ2/FeavMVVdzliZK01Vr8N7znpT1fGqMHrVqWoKK3Ttqdoqv0tHZ8FawgspsBbzQgqsZchgAkuuCiWwBJbAksBSiW4fQeFL+jfv/2XeAXC7oQWpfGdgdSSVYMsZC1OwVIisrdCwiTBgYslWKLAElgSWwBJYqteqewRB95vAkomllGEDlvalCZbAUp2dFKymOKLPZx5NPh/cz+cg0s77JpYxZmJpV0a/86CfTKyPvz3vPGzpmwbWYlLqBeuzN2YhBdYCc6+urgWWLe+o3McSWAJLYEltDu8O4yaWVGdiPZL/zDGxqAJLYElgCSwHrH4VeII09J4WUn0n1pzT8oNltMgZS53PWEFHLiPQxFoPgioTa/0Mowos2QolsASWwJLAElgCSwJLYAksCSyBJbAElo9AYKlMXgryR55+XvAZetBvuSfCwMp+w1ufT/twWBu+GbCJrXNgFXq7ZAdbN1ICCyZbIVK9d8OLKnWHRRVYVHX/ktzWQM5YAsu4AksCS2AJLAksgSWwJLAElsCSwBJYAksCS2AJLAksgSWwpMNheX0XWGzJViiwBJbdUNUmFltgsSVnLIFlaIElsKplaIElsGTugmU3BIstsCSwDC2w1PErcVkhgcUWWALL0BJYbNXoG/O8PCbkm47lAAAAAElFTkSuQmCC";

Leave a Comment