Given a contiguous drawing of arbitrary pixels (e.g. on an HTML5 Canvas) is there any algorithm for finding the axis-aligned bounding box that is more efficient than simply looking at every pixel and recording the min/max x/y values?
Just scanline from top left to right and down to get y top,and similar algorithm with different directions for the rest.
Edit by Phrogz:
Here's a pseudo-code implementation. An included optimization ensures that each scan line does not look at pixels covered by an earlier pass:
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
The result (in practice) performs about the same as the brute-force algorithm for a single pixel, and significantly better as the object gets larger.
For fun, here's a visual representation of how this algorithm works:
It doesn't matter in what order you choose to do the sides, you just have to make sure that you take the previous results into account so that you are not double-scanning the corners.