12870 Rate this article:

Minimum Area Bounding Box

Anonym Thursday, August 18, 2016

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

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

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

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)

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

Please login or register to post comments.

Compressing hyperspectral data using Motion JPEG2000 Upsampling images using a Lagrange polynomial method

NV5 Geospatial Blog

Minimum Area Bounding Box

Please login or register to post comments.