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

Question

给定连续绘制的任意像素(例如在HTML5 Canvas上)，是否有找到比简单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

有趣的是，以下是该算法工作原理的直观表示:



选择以何种顺序排列边线无关紧要，只需要确保将先前的结果考虑在内即可，这样就不必对角进行两次扫描了。