Canvas 黑块计数

问题

给定一个 Canvas，上面随机分布着一些黑块，计算 Canvas 上有多少个独立的黑块。

解答

这个问题可以转化为图的连通分量问题。基本思路是：先获取像素数据，然后使用深度优先搜索（DFS）或并查集来统计连通区域的数量。

实现步骤

1. 使用 getImageData 获取像素数组
2. 创建一个 width * height 的二维数组标记黑色像素
3. 遍历所有像素，对每个未访问的黑色像素进行 DFS

function countBlackBlocks(canvas) {
  const ctx = canvas.getContext('2d');
  const width = canvas.width;
  const height = canvas.height;
  const imageData = ctx.getImageData(0, 0, width, height);
  const pixels = imageData.data;
  
  // 创建标记数组
  const visited = Array.from({ length: height }, () => Array(width).fill(false));
  const isBlack = Array.from({ length: height }, () => Array(width).fill(false));
  
  // 标记黑色像素
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const index = (y * width + x) * 4;
      const r = pixels[index];
      const g = pixels[index + 1];
      const b = pixels[index + 2];
      
      // 判断是否为黑色（可根据实际情况调整阈值）
      if (r < 50 && g < 50 && b < 50) {
        isBlack[y][x] = true;
      }
    }
  }
  
  // DFS 遍历连通区域
  function dfs(x, y) {
    if (x < 0 || x >= width || y < 0 || y >= height) return;
    if (visited[y][x] || !isBlack[y][x]) return;
    
    visited[y][x] = true;
    
    // 遍历四个方向
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
  }
  
  // 统计连通分量
  let count = 0;
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      if (isBlack[y][x] && !visited[y][x]) {
        dfs(x, y);
        count++;
      }
    }
  }
  
  return count;
}

关键点

• 使用 getImageData 获取像素数据，每个像素由 RGBA 四个值组成
• 将问题转化为图的连通分量问题，黑色像素作为节点，相邻黑色像素之间有边
• 使用 DFS 遍历每个连通区域，每次 DFS 完成代表找到一个独立黑块
• 也可以使用并查集算法实现，时间复杂度相同但代码更简洁