Skip to content

minimum area bounding rectangles

7 messages · Aman Verma, Barry Rowlingson, Murray Richardson

Murray Richardson
# 
Hi R users,

I would like to compute minimum area bounding rectangles for polygon 
features to extract short and long axes and azimuths of the long axes.  
Is this possible in R? I have not been able to find a way (yet).

Thanks in advance for any help.

Murray
Aman Verma
# 
bbox in the sp package is what you are looking for.

-----Original Message-----
From: r-sig-geo-bounces at r-project.org [mailto:r-sig-geo-bounces at r-project.org] On Behalf Of Murray Richardson
Sent: March 15, 2011 12:37 PM
To: r-sig-geo at r-project.org
Subject: [R-sig-Geo] minimum area bounding rectangles

Hi R users,

I would like to compute minimum area bounding rectangles for polygon 
features to extract short and long axes and azimuths of the long axes.  
Is this possible in R? I have not been able to find a way (yet).

Thanks in advance for any help.

Murray

_______________________________________________
R-sig-Geo mailing list
R-sig-Geo at r-project.org
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Murray Richardson
# 
Thanks for your advice Arman.  Unfortunately bbox is just the minimum 
bounding rectangle (i.e. min and max of x and y), not the minimum area 
bounding rectangle.  I need MABR to get the short and long axes info.

I will wait for addition advice from others.

Murray
On 15/03/2011 12:53 PM, Aman Verma wrote:
Barry Rowlingson
# 
On Tue, Mar 15, 2011 at 4:37 PM, Murray Richardson
<murray_richardson at carleton.ca> wrote:
Do you mean you've not found code for it or not found and implemented
an algorithm for it?

 There's a proof that the minimum area bounding rectangle of a convex
polygon will have one side along a side of the polygon, so the
algorithm involves N rotations of the polygon and computation of the
area of the axis-aligned bounding box after rotation. Choose the
rotation that minimises this.

 In R, chull will get you the convex hull, atan2 will get you the
angles, and sines and cosines will get you a rotation matrix. There's
some matlab code here:

http://www.mathworks.com/matlabcentral/fileexchange/13624-minimal-bounding-rectangle

 which might be useful.

Barry
Murray Richardson
# 
Thanks Barry for the great tips.  The MATLAB code will be a huge help - 
should be relatively straightforward to implement in R.

cheers,

Murray
On 15/03/2011 7:20 PM, Barry Rowlingson wrote:
Barry Rowlingson
# 
Shazam:

minbb <- function(pts){

  ch = chull(pts)
  pts=pts[ch,]
  np = nrow(pts)
  pts=rbind(pts,pts[1,])
  minbba = Inf ; bbth = NA; rotmin = NA
  for(i in 1:np){
    th = pi-atan2(pts[i+1,2]-pts[i,2],pts[i+1,1]-pts[i,1])
    prot = rotxy(pts,th)
    bba = diff(range(prot[,1])) * diff(range(prot[,2]))
    if(bba < minbba){
      xyb=cbind(
        c(min(prot[,1]),max(prot[,1]),max(prot[,1]),min(prot[,1])),
        c(min(prot[,2]),min(prot[,2]),max(prot[,2]),max(prot[,2]))
        )
      xyb=rbind(xyb,xyb[1,])
      xyb= rotxy(xyb,-th)

      rotmin=prot
      minbba = bba
      bbth = th
    }
  }
  return(list(minbba=minbba,theta=th,pts=rotmin,box=xyb))

}

rotxy = function(pts,angle){
  co = cos(angle)
  si = sin(angle)
  cbind(co * pts[,1] - si * pts[,2], si * pts[,1] + co * pts[,2])
}

And usage:

 > pts=cbind(runif(60),runif(60))
 > bb=minbb(pts)
 > plot(bb$box,type="l")
 > points(pts)
 > pts2=rotxy(pts,pi/1.6)
 > bb2=minbb(pts2)
 > plot(bb2$box,type="l")
 > points(pts2)
Wrote this myself with a helpful rotate function nabbed from
spatstat. Could be optimised a bit, I reckon.

Barry
Murray Richardson
# 
Wow, what can I say!? Thanks a million!  I will try it out thoroughly 
tomorrow.

Murray
On 15/03/2011 7:47 PM, Barry Rowlingson wrote: