计算任意基于像素的图形的边界框

Question

给出任意像素的连续图形（例如在HTML5画布上），有没有一种算法可以找到比简单地looking at every pixel and recording the min/max x/y values更有效的与轴对齐的边界框？

Answer 1

仅从左上角到右下角的扫描线就可以得到y top，其余的类似算法具有不同的方向。

---

Phrogz编辑：

这里是伪代码实现。包含的优化功能可确保每条扫描线不会查看较早通过的像素：

function boundingBox()
  w = getWidth()            # Assuming graphics address goes from [0,w)
  h = getHeight()           # Assuming graphics address goes from [0,h)
  for y=h-1 to 0 by -1      # Iterate from last row upwards
    for x=w-1 to 0 by -1    # Iterate across the entire row
      if pxAt(x,y) then
        maxY=y
        break               # Break out of both loops

  if maxY===undefined then  # No pixels, no bounding box
    return               

  for x=w-1 to 0 by -1      # Iterate from last column to first
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        maxX=x
        break               # Break out of both loops

  for x=0 to maxX           # Iterate from first column to maxX
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        minX=x
        break               # Break out of both loops

  for y=0 to maxY           # Iterate down the rows, up to maxY
    for x=0 to maxX         # Iterate across the row, up to maxX
      if pxAt(x,y) then
        minY=y
        break               # Break out of both loops

  return minX, minY, maxX, maxY

结果（实际上）的效果与单个像素的蛮力算法大致相同，并且随着对象变大，效果明显更好。

演示：http://phrogz.net/tmp/canvas_bounding_box2.html

为了有趣，这是该算法工作原理的直观表示：

img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9SZXR0Si5wbmcifQ==” alt =“在此处输入图像描述”>

选择以何种顺序排列边并不重要，您只需要确保已将先前的结果考虑在内，这样就不会重复扫描角落。

Answer 2

您可能可以使用某种二元搜索，或者在粗网格上进行采样，然后在逐次精细的网格上进行采样。此方法的正确性取决于您的图形中是否允许使用“孔”。

Answer 3

我不喜欢当前的答案。这是我插入OP网站的代码。在Firefox和chrome中速度更快

function contextBoundingBox(ctx,alphaThreshold){
    if (alphaThreshold===undefined) alphaThreshold = 15;
    var w=ctx.canvas.width,h=ctx.canvas.height;
    var data = ctx.getImageData(0,0,w,h).data;

    let minX=w;
    let maxX=0
    let minY=h
    let maxY=0
    for(let y=0; y<h; y++)
    {
        for(let x=0; x<w; x++)
        {
            if (data[y*w*4 + x*4+3])
            {
                minX = Math.min(minX, x);
                maxX = Math.max(maxX, x);
                minY = Math.min(minY, y);
                maxY = Math.max(maxY, y);
                x=maxX
            }
        }
    }

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