LeetCode的一個演算法幫我解決了工作棘手問題

起因是這樣的，我工作中碰到了一個問題，允許我用一張圖來表達這個問題是什麼。

我所維護的一個圖片編輯器有這麼一個功能，就是我的編輯器提供一些模板，然後使用者會上傳圖片，我需要把使用者的圖片縮放到模板抠出來的填圖框那個大小，從而避免讓使用者自己去手動縮放。因此我們的設計師會給我一個填圖框相對於整個模板的XY和寬高數據，例如這樣。

這樣我們就能夠透過模板本身的寬高，再乘以給定的數據就能計算得出，我要把使用者的圖片縮放到哪個大小及位置，從而讓這個圖片正好適應模板所抠出來的部分。

但問題是我們的模板裡面的填圖框是大小不一，的很難提前去預設一個位置寬高數據，這就需要我去透過模板去運行時解析計算它這個填圖框的x,y,w,h信息。

起初這個問題是很容易解決的，我們只需要找出圖片的所有透明像素（即alpha通道為0），然後向左取最小值，向上取最小值，向右取最大，向下取最大即可：

{
    x: minX,
    y: minY,
    w: maxX - minX,
    h: maxY - minY
}

正當我沾沾自喜時，我們的設計師給我整了個大招出來。

之前那個簡單演算法只能求一個簡單矩形的位置資訊，但現如今有這麼多形態各異、位置不同的透明區域，該如何計算它們各自的x,y,w,h信息呢？於是我翻來覆去，廢寢忘食，苦思冥想。

2000 years later..................................................................

我發現每一個像素點對於我的區別來說就是它是否透明，那我可以用1來表示透明，0表示不透明，那一張圖片實際上可以表達成由1和0組成的二維陣列，那這不就跟LeetCode上面的200. 最大島嶼數量很像嗎？

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

最大島嶼數量和我這個問題有著相似的邏輯，比如循環遍歷每一個1，在每一個1上向它四周擴散，這個擴散的過程會被記錄，如果它碰到了1就繼續這個擴散的過程，如果不是那就立刻停止，直到在上下左右四個方向都沒有碰到1或者超界，就停止這個擴散的過程。

在這個擴散的過程中，我記錄我經過了哪些位置，即這個1在二維陣列中的索引，也意味著透明像素在模板中的相對位置。

每一個1都有這麼一個擴散的過程，不過我們可以快取之前哪些1被遍歷過了，那就不需要重新擴散。

這就是我們解決這個問題的比較形象的思維邏輯，好了接下來可以展示程式碼了。

type IRect = {
  x: number
  y: number
  w: number
  h: number
}

const canvas = document.createElement('canvas')
const ctx = canvas.getContext('2d', { willReadFrequently: true })!

// 判斷像素透明
function isEmptyPixel(
  data: Uint8ClampedArray,
  x: number,
  y: number,
  width: number
): boolean {
  const index = (y * width + x) * 4
  if (data[index + 3] === 0) return true
  return false
}

// 表示擴散過程的函數
function findEmptyArea(
  data: Uint8ClampedArray,
  visited: boolean[],
  startX: number,
  startY: number,
  width: number,
  height: number
  // 這個x,y表示二維陣列索引，也是模板像素點的坐標
): { x: number; y: number }[] {
  // 收集擴散的 1
  const area: { x: number; y: number }[] = []
  // 這個堆疊用來存儲需要經過擴散的 1
  const stack: { x: number; y: number }[] = [{ x: startX, y: startY }]

  // 直到沒有 1 需要擴散了
  while (stack.length > 0) {
    const { x, y } = stack.pop()!

    // 越界判斷
    if (x < 0 || x >= width || y < 0 || y >= height) continue
    // 是否已經訪問過
    if (visited[y * width + x]) continue

    // 標記為已訪問
    visited[y * width + x] = true

    // 是否是透明像素
    if (!isEmptyPixel(data, x, y, width)) continue

    // 收集擴散到的 1
    area.push({ x, y })
    // 擴散到相鄰的 1，並加入堆疊中
    stack.push({ x: x + 1, y })
    stack.push({ x: x - 1, y })
    stack.push({ x, y: y + 1 })
    stack.push({ x, y: y - 1 })
  }

  return area
}

// 將點集轉換為矩形
function pointsToRect(
  points: { x: number; y: number }[],
  width: number,
  height: number
): IRect | null {
  // 如果點集數量小於總像素數的 3.5%，則返回 null, 即忽略那些過於小的區域
  if (points.length / (width * height) < 0.035) return null

  let minX = Infinity
  let minY = Infinity
  let maxX = -Infinity
  let maxY = -Infinity

  for (const point of points) {
    minX = Math.min(minX, point.x)
    minY = Math.min(minY, point.y)
    maxX = Math.max(maxX, point.x)
    maxY = Math.max(maxY, point.y)
  }

  return {
    x: minX,
    y: minY,
    w: maxX - minX + 1,
    h: maxY - minY + 1,
  }
}

export async function autoGrids(url: string) {
  const img = new Image()
  img.src = url
  img.crossOrigin = 'Anonymous'
  return await new Promise<IRect[]>((resolve) => {
    img.onload = () => {
      canvas.width = img.width
      canvas.height = img.height
      ctx.drawImage(img, 0, 0)
      const imageData = ctx.getImageData(0, 0, img.width, img.height)
      // 這個data是rgba的陣列，每個像素點有4個值，分別是r,g,b,a
      const data = imageData.data
      // 這個visited是用來記錄哪些像素點已經訪問過
      const visited = new Array(img.width * img.height).fill(false)
      let emptyRects: IRect[] = []

      // 遍歷每個 "1" 即透明像素點
      for (let y = 0; y < img.height; y++) {
        for (let x = 0; x < img.width; x++) {
          // 如果這個1已經訪問過，則跳過
          // 如果這個像素點是透明像素，即是 "1"，則進行擴散
          if (!visited[y * img.width + x] && isEmptyPixel(data, x, y, img.width)) {
            // 進行擴散
            const area = findEmptyArea(data, visited, x, y, img.width, img.height)
            // 將擴散到的點集轉換為矩形
            const rect = pointsToRect(area, img.width, img.height)
            if (rect) {
              emptyRects.push(rect)
            }
          }
        }
      }
      resolve(emptyRects)
    }
  })
}

原文出處：https://juejin.cn/post/7555329798584025139