Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Calculate bounding box of arbitrary pixel-based drawing

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?

like image 632
Phrogz Avatar asked Mar 24 '12 13:03

Phrogz


2 Answers

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.

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

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

        enter image description here
        enter image description here
        enter image description here
        enter image description here
        enter image description here

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.

like image 118
adrix89 Avatar answered Sep 30 '22 02:09

adrix89


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

like image 30
Li-aung Yip Avatar answered Sep 30 '22 02:09

Li-aung Yip