Calculate the bounding box of an arbitrary pixel drawing

Question

Given the continuous drawing of arbitrary pixels (for example, on HTML5 canvas), is there any algorithm to find the bounding rectangle along the axis that is more efficient than just looking at each pixel and writing down the min / max x / y values ?

Answer 1

Just scan from top to bottom left and right to get y top, and a similar algorithm with different directions for the rest.

---

Edit by Phrogz:

The pseudo-code implementation is implemented here. The 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 roughly the same as the brute force algorithm for one pixel, and is much better as the object grows.

Demo: http://phrogz.net/tmp/canvas_bounding_box2.html

For fun, here is a visual representation of how this algorithm works:

It doesn't matter in which order you choose the sides, you just need to make sure that you take into account the previous results so that you don't look at the corners twice.

Answer 2

You might be able to use some kind of binary search or pattern on a coarse grid, and then a finer grid. The correctness of this method depends on whether holes are allowed in your drawing.