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

Question

给定任意像素的连续绘制(例如在HTML5 Canvas上)是否有任何算法用于找到轴对齐的边界框,这比仅查看每个像素并记录最小/最大x/y值更有效？

Answer 1

只需扫描线从左上到右,向下到达顶部,类似的算法,其余的方向不同.

由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

为了好玩,这里是这个算法如何工作的直观表示:

       
       
       
       
       

按照您选择的方式执行两侧操作并不重要,您只需确保将先前的结果考虑在内,这样您就不会对角落进行双重扫描.