计算任意基于像素的绘图的边界框-Java 学习之路

给定任意像素的连续绘制（例如在HTML5 Canvas上）是否存在任何用于查找轴对齐边界框的算法，该边界框比单纯的looking at every pixel and recording the min/max x/y values更有效？

2 回答

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

由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

结果（在实践中）对于单个像素执行与蛮力算法大致相同，并且随着对象变大而显着更好 .