3.0

# Minimum Area Bounding Box

Austin Coates

I find myself drawing bounding boxes around things a lot. I don’t know why I do it so much, but for whatever reason I do, and as of late I wanted to up my bounding box game. In the past, I have simply used the global min and max in both the x and y directions to get the coordinates to form the bounding box; however, this is not always the most elegant solution. For example, when my data follows somewhat of a linear trend, I am left with ample white space not filled by any valuable information

Figure 1: Simple Bounding Box

Figure 2: Minimum Area Bounding Box

This got me thinking, why am I not simply drawing a bounding box around only the data? Sounds great, right? The only problem was I had no idea how to do this. Luckily, there is this thing called the internet and it has vast stores of information and ideas to pull from. I found a very elegant solution by Jesse Buesking on stackoverflow.com which was posted on November 9, 2015. The solution was written in Python which I converted to IDL. My goal in posting this is to show an awesome way to draw a bounding box and also an example of translating between IDL and Python.

```function bounding_box, pts = pts, plot_results = plot_results compile_opt IDL2;Get the x and y coordinatesxs = pts[0,*]ys = pts[1,*] ;Find the bounding pointsTriangulate, xs, ys, triangles, hull, CONNECTIVITY=CONNECTIVITY;order hull points in a [2,n] array     hull_points = [[xs[hull]]##1,[ys[hull]]##1];calculate edge anglesedges = hull_points[*,1:-1] - hull_points[*,0:-2]angles = atan(edges[1,*], edges[0,*])
pi2 = !DPI/2. angles = abs(angles - floor(angles / pi2) * pi2)angles = angles[sort(angles)]angles = angles[UNIQ(angles)];find rotation matrices rotations = transpose([[cos(angles)],[cos(angles-pi2)],[cos(angles+pi2)],[cos(angles)]])rotations = REFORM(rotations, [2,2,n_elements(angles)]) ;apply rotations to the hull rot_points = fltarr( n_elements(hull_points)/2, 2, n_elements(angles))size_rot = size(rotations)
for group = 0 , size_rot[3]-1 do begin     for row = 0 , size_rot[2]-1 do begin    rot_points[*,row,group] = TRANSPOSE(rotations[*,row,group]) # hull_points  endforendfor
;find the bounding pointsmin_x =  min(rot_points[*,0,*],DIMENSION=1, /NAN)max_x =  max(rot_points[*,0,*],DIMENSION=1, /NAN)min_y =  min(rot_points[*,1,*],DIMENSION=1, /NAN)max_y =  max(rot_points[*,1,*],DIMENSION=1, /NAN)
;find the box with the best areaareas = (max_x - min_x) * (max_y - min_y)min_val = min(areas, best_idx)
;return the best boxx1 = max_x[best_idx]x2 = min_x[best_idx]y1 = max_y[best_idx]y2 = min_y[best_idx]r = rotations[*,*,best_idx]
rval = fltarr(2,4)rval[*,0] = TRANSPOSE(TRANSPOSE([x1, y2]) # transpose(r))rval[*,1] = TRANSPOSE(TRANSPOSE([x2, y2]) # transpose(r))rval[*,2] = TRANSPOSE(TRANSPOSE([x2, y1]) # transpose(r))rval[*,3] = TRANSPOSE(TRANSPOSE([x1, y1]) # transpose(r)) ;display results  if KEYWORD_SET(plot_results) then begin  p = SCATTERPLOT(xs,ys, SYM_COLOR='Red', SYM_FILL_COLOR='Red', SYM_FILLED=1,\$    XRANGE=[min(rval[0,*])-1,max(rval[0,*])+1], YRANGE=[min(rval[1,*])-1,max(rval[1,*])+1])
p = POLYGON(rval, /FILL_BACKGROUND, \$   FILL_COLOR="light steel blue", PATTERN_ORIENTATION=45, \$   PATTERN_SPACING=4, /DATA)endifreturn, rvalend

```

Source of original Python code : http://stackoverflow.com/questions/13542855/python-help-to-implement-an-algorithm-to-find-the-minimum-area-rectangle-for-gi/33619018#33619018

MOST RECENT

### Geospatial Answers as a Service | EAS 2020 Panel Discussion

11/18/2020

Join Stuart Blundell (Presagis) as he moderates this panel discussion about Geospatial Answers as a... more »

### Remote Sensing Solutions for Emergency Response

11/10/2020

After a disaster, every second counts. Immediate, effective response is paramount to reducing injuries and... more »