Calculate minimum area rectangle for a polygon

I have a need to calculate the minimum area rectangle (smallest possible rectangle) around the polygon.

The only input i have is the number of points in polygon.

soryy for the incomplete information . Yes i have the co-ordinates of the points also

Thanks

From stackoverflow

• Use the rotating calipers algorithm for a convex polygon, or the convex hull otherwise. You will of course need the coordinates of the points in the polygon, not just the number of points.

  Samra : I think it will help me .. more precisely i have to calculate the width and length of polygon !!!

  p00ya : that's not problem: as you apply the algorithm, you calculate the width and length of a bounding box aligned to each edge in turn.

• Obviously, you'll need the coordinates of the points to get the answer. If the rectangle is aligned to the X and Y aces, then the solution is trivial. If you want the smallest possible rectangle, at any angle, then you'll need to do some sort of optimization process.

  Samra : thanks mark for ur comment Yes i need the rectanle at any angle. Could you plz elaborate optimization process

  Mark Bessey : Several people have already mentioned the rotating calipers algorithm. That's basically how it's done. You do the equivalent of the basic min/max bounding box, but with the coordinate system rotated to the angle of each of the sides.

• This is called Minimum Bounding Box, it's most basic algorithm used in OCR packages. You can find an implementation using Rotating Calipers from the OpenCV package. Once you get the source code, check out this file,

  cv/src/cvrotcalipers.cpp
  

  The method you need is cvMinAreaRect2().

  Samra : I am unable to find the this method . Can u give me the precise for this thanks

  ZZ Coder : It's here http://www.google.com/codesearch/p?hl=en&sa=N&cd=1&ct=rc#WMkTvnMDpLM/cv/src/cvrotcalipers.cpp&q=cvMinAreaRect2