18

Aug

2016

### Minimum Area Bounding Box

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.

functionbounding_box, pts = pts, plot_results = plot_results

compile_optIDL2;Get the x and y coordinates

xs = pts[

0,*]ys = pts[

1,*]

;Find the bounding points

Triangulate, xs, ys, triangles, hull, CONNECTIVITY=CONNECTIVITY

;order hull points in a [2,n] array

hull_points = [[xs[hull]]##

1,[ys[hull]]##1];calculate edge angles

edges = 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)

forgroup =0, size_rot[3]-1dobegin

forrow =0, size_rot[2]-1dobeginrot_points[*,row,group] =

TRANSPOSE(rotations[*,row,group]) # hull_points

endfor

endfor;find the bounding points

min_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 area

areas = (max_x - min_x) * (max_y - min_y)min_val =

min(areas, best_idx);return the best box

x1 = 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

ifKEYWORD_SET(plot_results)thenbeginp =

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)

endif

return, rval

end

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

Categories: IDL Blog | IDL Data Point