任意像素绘制的边界框计算

Question

如果给定任意像素的连续绘制（例如在HTML5画布上），是否有比仅查看每个像素并记录最小/最大x/y值更有效地找到轴对齐边界框的算法？

- Phrogz

---

这个回答解决了你的问题吗？确定绘制到画布中的形状/图形的边界。 - Basj

Answer 1

只需从左上角开始扫描每个扫描线，向右扫描并向下获取y轴高度，对于其余部分使用不同方向的类似算法。

---

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

为了好玩，这里有一个直观的表示该算法工作原理的图示：

       
       
       
       
       

无论你选择以什么顺序处理边界，你只需要确保考虑到之前的结果，这样就不会重复扫描角落。

- adrix89

Answer 2

我不喜欢当前的答案。这是我插入到 OP 网站的代码。在 Firefox 和 Chrome 中速度要快得多。

思路是检查 x 轴上的所有像素，看是否有 Y 轴上的命中。如果有，更新 Y 并增加 X，以便我们可以扫描最大的 X。

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 = y;
                x=maxX
            }
        }
    }

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

- Eric Stotch

Answer 3

你可以尝试使用二分查找，或者在粗略网格上采样，然后逐步细化网格。这种方法的正确性取决于你的图形是否允许出现“空洞”。

- Li-aung Yip

---

如果图形具有任何凹边界部分，则二分搜索很容易失败。 - Phrogz